fork download
copy 
  1. #include <iostream>
  2. #include <numeric>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. int factorial(unsigned int n)
  8. {
  9.     int f = 1;
  10.     while (n) f *= n--;
  11.     return f;
  12. }
  13.  
  14. int power(int m, unsigned int n)
  15. {
  16.     int p = 1;
  17.     while (n--) p *= m;
  18.     return p;
  19. }
  20.  
  21. vector<int> ithDuplicatedPermutation(int n, int m, int i)
  22. {
  23.     vector<int> c(n);
  24.     fill(c.begin(), c.end(), m);
  25.  
  26.     int N = n * m;
  27.     vector<int> a(N);
  28.  
  29.     int P = factorial(N) / power(factorial(m), n);
  30.  
  31.     for (int j = 0; j < N; j++) {
  32.         for (int k = 0; k < n; k++) {
  33.             if (!c[k]) continue;
  34.             int p = P * c[k] / (N - j);
  35.             if (i <= p) {
  36.                 a[j] = k + 1;
  37.                 c[k]--;
  38.                 P = p;
  39.                 break;
  40.             }
  41.             i -= p;
  42.         }
  43.     }
  44.  
  45.     return a;
  46. }
  47.  
  48. template <typename T> ostream &operator<<(ostream &os, const vector<T> &v)
  49. {
  50.     cout << "[";
  51.     for (auto &x : v) os << (&x == &v[0] ? "" : ", ") << x;
  52.     cout << "]";
  53.     return os;
  54. }
  55.  
  56. int main(void)
  57. {
  58.     for (int n : {1, 2, 3, 123456, 234567, 369600}) {
  59.         cout << "入力: " << n << endl;
  60.         cout << "出力: " << ithDuplicatedPermutation(4, 3, n) << endl << endl;
  61.     }
  62.  
  63.     return 0;
  64. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
入力: 1
出力: [1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4]

入力: 2
出力: [1, 1, 1, 2, 2, 2, 3, 3, 4, 3, 4, 4]

入力: 3
出力: [1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 3, 4]

入力: 123456
出力: [2, 2, 2, 3, 3, 1, 4, 3, 4, 1, 1, 4]

入力: 234567
出力: [3, 2, 4, 4, 2, 4, 3, 3, 1, 1, 1, 2]

入力: 369600
出力: [4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1]
https://ideone.com/90BpGt
language:
C++14 (gcc 8.3)
created:
35 days ago
visibility:
secret

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!