fork(1) download
copy 
  1. #include <iostream>
  2. #include <numeric>
  3. #include <vector>
  4. #include <random>
  5. #include <algorithm>
  6.  
  7. int pCount(int n, int m, int myMax) {
  8.  
  9.     if (myMax * m < n) return 0;
  10.     if (myMax * m == n) return 1;
  11.  
  12.     if (m < 2) return m;
  13.     if (n < m) return 0;
  14.     if (n <= m + 1) return 1;
  15.  
  16.     int niter = n / m;
  17.     int count = 0;
  18.  
  19.     for (; niter--; n -= m, --myMax) {
  20.         count += pCount(n - 1, m - 1, myMax);
  21.     }
  22.  
  23.     return count;
  24. }
  25.  
  26. std::vector<int> unRank(int n, int m, int myMax, int nth) {
  27.  
  28.     std::vector<int> z(m, 0);
  29.     int count = 0;
  30.     int j = 0;
  31.  
  32.     for (int i = 0; i < z.size(); ++i) {
  33.         int temp = pCount(n - 1, m - 1, myMax);
  34.  
  35.         for (int r = n - m, k = myMax - 1;
  36.              (count + temp) < nth && r > 0 && k; r -= m, --k) {
  37.  
  38.             count += temp;
  39.             n = r;
  40.             myMax = k;
  41.             ++j;
  42.             temp = pCount(n - 1, m - 1, myMax);
  43.         }
  44.  
  45.         --m;
  46.         --n;
  47.         z[i] = j;
  48.     }
  49.  
  50.     return z;
  51. }
  52.  
  53. int main() {
  54. 	int max = 10;
  55. 	int min = 3;
  56. 	int N = 7;
  57. 	int sum = 42;
  58.  
  59.     int m = N;
  60.     int n = sum - m * (min - 1);
  61.     int myMax = max - min + 1;
  62.     int totalNum = pCount(n, m, myMax);
  63.  
  64.     std::vector<int> v(max - min + 1);
  65.     std::iota(v.begin(), v.end(), min);
  66.  
  67.     std::vector<int> indexVec(totalNum);
  68.     std::random_device rd;
  69.     std::mt19937 gen(rd());
  70.     std::iota(indexVec.begin(), indexVec.end(), 1);
  71.     std::shuffle(indexVec.begin(), indexVec.end(), gen);
  72.  
  73.     // random-sample without replacement
  74.     std::vector<int> randVec(indexVec.begin(), indexVec.begin() + 20);
  75.  
  76.     for (auto index: randVec) {
  77. 	    std::vector<int> z = unRank(n, m, myMax, index);
  78. 	    std::cout << index << ": ";
  79.  
  80. 	    for (int i = 0; i < m; ++i)
  81. 	        std::cout << v[z[i]] << " ";
  82.  
  83. 	    std::cout << "\n";
  84. 	}
  85.  
  86.     std::cout << std::endl;
  87.     return 0;
  88. }
Success #stdin #stdout 0s 4500KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
42: 3 3 6 7 7 8 8 
123: 4 4 6 6 6 7 9 
2: 3 3 3 4 9 10 10 
125: 4 4 6 6 7 7 8 
104: 4 4 4 6 6 8 10 
74: 3 4 6 7 7 7 8 
47: 3 4 4 5 6 10 10 
146: 5 5 5 5 6 7 9 
70: 3 4 6 6 6 7 10 
134: 4 5 5 6 6 7 9 
136: 4 5 5 6 7 7 8 
81: 3 5 5 5 8 8 8 
122: 4 4 6 6 6 6 10 
112: 4 4 5 5 6 8 10 
147: 5 5 5 5 6 8 8 
142: 4 6 6 6 6 7 7 
37: 3 3 6 6 6 9 9 
67: 3 4 5 6 8 8 8 
45: 3 4 4 4 8 9 10 
44: 3 4 4 4 7 10 10
https://ideone.com/0MdGVF
language:
C++ (gcc 8.3)
created:
3 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!