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.     for (int j = 0; j < N; j++) {
  30.         int P1 = factorial(N - j - 1), P2 = 1;
  31.         for (int k = 0; k < n; k++) P2 *= factorial(c[k]);
  32.         for (int k = 0; k < n; k++) {
  33.             if (!c[k]) continue;
  34.             int p = P1 / (P2 / c[k]);
  35.             if (i <= p) {
  36.                 a[j] = k + 1;
  37.                 c[k]--;
  38.                 break;
  39.             }
  40.             i -= p;
  41.         }
  42.     }
  43.  
  44.     return a;
  45. }
  46.  
  47. template <typename T> ostream &operator<<(ostream &os, const vector<T> &v)
  48. {
  49.     cout << "[";
  50.     for (auto &x : v) os << (&x == &v[0] ? "" : ", ") << x;
  51.     cout << "]";
  52.     return os;
  53. }
  54.  
  55. int main(void)
  56. {
  57.     for (int n : {1, 2, 3, 123456, 234567, 369600}) {
  58.         cout << "入力: " << n << endl;
  59.         cout << "出力: " << ithDuplicatedPermutation(4, 3, n) << endl << endl;
  60.     }
  61.  
  62.     return 0;
  63. }
Success #stdin #stdout 0.01s 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/uH8dpO
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!