fork download
copy 
  1. #include <iostream>
  2. #include <numeric>
  3. #include <vector>
  4.  
  5. int pCount(int n, int m, int myMax) {
  6.  
  7.     if (myMax * m < n) return 0;
  8.     if (myMax * m == n) return 1;
  9.  
  10.     if (m < 2) return m;
  11.     if (n < m) return 0;
  12.     if (n <= m + 1) return 1;
  13.  
  14.     int niter = n / m;
  15.     int count = 0;
  16.  
  17.     for (; niter--; n -= m, --myMax) {
  18.         count += pCount(n - 1, m - 1, myMax);
  19.     }
  20.  
  21.     return count;
  22. }
  23.  
  24. std::vector<int> unRank(int n, int m, int myMax, int nth) {
  25.  
  26.     std::vector<int> z(m, 0);
  27.     int count = 0;
  28.     int j = 0;
  29.  
  30.     for (int i = 0; i < z.size(); ++i) {
  31.         int temp = pCount(n - 1, m - 1, myMax);
  32.  
  33.         for (int r = n - m, k = myMax - 1;
  34.              (count + temp) < nth && r > 0 && k; r -= m, --k) {
  35.  
  36.             count += temp;
  37.             n = r;
  38.             myMax = k;
  39.             ++j;
  40.             temp = pCount(n - 1, m - 1, myMax);
  41.         }
  42.  
  43.         --m;
  44.         --n;
  45.         z[i] = j;
  46.     }
  47.  
  48.     return z;
  49. }
  50.  
  51. int main() {
  52. 	int max = 10;
  53. 	int min = 3;
  54. 	int N = 7;
  55. 	int sum = 42;
  56.  
  57.     int m = N;
  58.     int n = sum - m * (min - 1);
  59.     int myMax = max - min + 1;
  60.     int totalNum = pCount(n, m, myMax);
  61.  
  62.     std::vector<int> v(max - min + 1);
  63.     std::iota(v.begin(), v.end(), min);
  64.  
  65.     // Get the first 10 partitions
  66.     for (int index = 1; index <= 10; ++index) {
  67. 	    std::vector<int> z = unRank(n, m, myMax, index);
  68. 	    std::cout << index << ": ";
  69.  
  70. 	    for (int i = 0; i < m; ++i)
  71. 	        std::cout << v[z[i]] << " ";
  72.  
  73. 	    std::cout << "\n";
  74. 	}
  75.  
  76. 	std::cout << ".\n.\n.\n";
  77.  
  78. 	// Get the last 10 partitions
  79. 	for (int index = totalNum - 9; index <= totalNum; ++index) {
  80. 	    std::vector<int> z = unRank(n, m, myMax, index);
  81. 	    std::cout << index << ": ";
  82.  
  83. 	    for (int i = 0; i < m; ++i)
  84. 	        std::cout << v[z[i]] << " ";
  85.  
  86. 	    std::cout << "\n";
  87. 	}
  88.  
  89.     std::cout << std::endl;
  90.     return 0;
  91. }
Success #stdin #stdout 0s 4520KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1: 3 3 3 3 10 10 10 
2: 3 3 3 4 9 10 10 
3: 3 3 3 5 8 10 10 
4: 3 3 3 5 9 9 10 
5: 3 3 3 6 7 10 10 
6: 3 3 3 6 8 9 10 
7: 3 3 3 6 9 9 9 
8: 3 3 3 7 7 9 10 
9: 3 3 3 7 8 8 10 
10: 3 3 3 7 8 9 9 
.
.
.
146: 5 5 5 5 6 7 9 
147: 5 5 5 5 6 8 8 
148: 5 5 5 5 7 7 8 
149: 5 5 5 6 6 6 9 
150: 5 5 5 6 6 7 8 
151: 5 5 5 6 7 7 7 
152: 5 5 6 6 6 6 8 
153: 5 5 6 6 6 7 7 
154: 5 6 6 6 6 6 7 
155: 6 6 6 6 6 6 6
https://ideone.com/2xNze8
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!