combinatorics - Calculate Nth multiset combination (with repetition) based only on index -

how can calculate nth combo based on it's index. there should (n+k-1)!/(k!(n-1)!) combinations repetitions.

with n=2, k=5 get:  0|{0,0,0,0,0} 1|{0,0,0,0,1} 2|{0,0,0,1,1} 3|{0,0,1,1,1} 4|{0,1,1,1,1} 5|{1,1,1,1,1} 

so black_magic_function(3) should produce {0,0,1,1,1}.

this going gpu shader, want each work-group/thread able figure out subset of permutations without having store sequence globally.

with n=3, k=5 get: i=0, {0,0,0,0,0} i=1, {0,0,0,0,1} i=2, {0,0,0,0,2} i=3, {0,0,0,1,1} i=4, {0,0,0,1,2} i=5, {0,0,0,2,2} i=6, {0,0,1,1,1} i=7, {0,0,1,1,2} i=8, {0,0,1,2,2} i=9, {0,0,2,2,2} i=10, {0,1,1,1,1} i=11, {0,1,1,1,2} i=12, {0,1,1,2,2} i=13, {0,1,2,2,2} i=14, {0,2,2,2,2} i=15, {1,1,1,1,1} i=16, {1,1,1,1,2} i=17, {1,1,1,2,2} i=18, {1,1,2,2,2} i=19, {1,2,2,2,2} i=20, {2,2,2,2,2} 

the algorithm generating can seen mbnext_multicombination @ http://www.martinbroadhurst.com/combinatorial-algorithms.html

update:

so thought i'd replace binomial coefficient in pascals triangle (n+k-1)!/(k!(n-1)!) see how looks.

(* mathematica code display pascal , other triangle *) t1 = table[binomial[n, k], {n, 0, 8}, {k, 0, n}]; t2 = table[(n + k - 1)!/(k! (n - 1)!), {n, 0, 8}, {k, 0, n}]; (*display*) {row[#, "\t"]} & /@ t1 // grid {row[#, "\t"]} & /@ t2 // grid 

t1:

                1               1   1             1   2   1           1   3   3   1         1   4   6   4   1       1   5   10  10  5   1     1   6   15  20  15  6   1   1   7   21  35  35  21  7   1 1   8   28  56  70  56  28  8   1 

t2:

           indeterminate                1   1              1   2   3            1   3   6   10          1   4   10  20   35        1   5   15  35   70   126      1   6   21  56  126   252  462    1   7   28  84  210   462  924   1716 1   8   36  120  330   792  1716  3432  6435 

comparing n=3,k=5 console output @ start of post: third diagonal {3,6,10,15,21,28,36} gives index of each roll-over point {0,0,0,1,1} -> {0,0,1,1,1} -> {0,1,1,1,1}, etc. , diagonal left of seems show how many values contained in previous block (diagonal[2][i] == diagonal[3][i] - diagonal[3][i-1])). , if read 5th row of pyramid horizontally max amount of combinations increasing values of n in (n+k-1)!/(k!(n-1)!) k=5.

there way use information determine exact combo arbitrary index, without enumerating whole set, i'm not sure if need go far. original problem decompose full combo space equal subsets, can generated locally, , worked on in parallel gpu. triangle above gives starting index of every block, of combo can trivially derived, , successive elements incrementally enumerated. gives block size, , how many total combinations have. becomes packing problem of how fit unevenly sized blocks groups of equal work load across x amount of threads.

see example at: https://en.wikipedia.org/wiki/combinatorial_number_system#finding_the_k-combination_for_a_given_number

just replace binomial coefficient (n+k-1)!/(k!(n-1)!).

---

assuming n=3,k=5, let's want calculate 19th combination (id=19).

 id=0, {0,0,0,0,0}  id=1, {0,0,0,0,1}  id=2, {0,0,0,0,2}  ...  id=16, {1,1,1,1,2}  id=17, {1,1,1,2,2}  id=18, {1,1,2,2,2}  id=19, {1,2,2,2,2}  id=20, {2,2,2,2,2} 

the result we're looking {1,2,2,2,2}.

examining our 't2' triangle: n=3,k=5 points 21, being 5th number (top bottom) of third diagonal (left right).

            indeterminate                 1   1               1   2   3             1   3   6   10           1   4   10  20   35         1   5   15  35   70   126       1   6   21  56  126   252  462     1   7   28  84  210   462  924   1716  1   8   36  120  330   792  1716  3432  6435 

we need find largest number in row (horizontally, not diagonally) not exceed our id=19 value. moving left 21 arrive @ 6 (this operation performed largest function below). since 6 2nd number in row corresponds n==2 (or g[2,5] == 6 code below).

now we've found 5th number in combination, move floor in pyramid, k-1=4. subtract 6 encountered below id, id=19-6=13. repeating entire process find 5 (n==2 again) largest number less 13 in row.

next: 13-5=8, largest 4 in row (n==2 yet again).

next: 8-4=4, largest 3 in row (n==2 1 more time).

next: 4-3=1, largest 1 in row (n==1)

so collecting indices @ each stage {1,2,2,2,2}

---

the following mathematica code job:

g[n_, k_] := (n + k - 1)!/(k! (n - 1)!)  largest[i_, nn_, kk_] := with[     {x = g[nn, kk]},      if[x > i, largest[i, nn-1, kk], {nn,x}] ]  id2combo[id_, n_, 0]  := {} id2combo[id_, n_, k_] := module[     {val, offset},      {val, offset} = largest[id, n, k];     append[id2combo[id-offset, n, k-1], val] ] 

---

update: order combinations being generated mbnext_multicombination wasn't matching id2combo, don't think lexicographic. function below generates them in same order id2combo , matches order of mathematica's sort[]function on list of lists.

void next_combo(unsigned int *ar, unsigned int n, unsigned int k) {     unsigned int i, lowest_i;      (i=lowest_i=0; < k; ++i)         lowest_i = (ar[i] < ar[lowest_i]) ? : lowest_i;      ++ar[lowest_i];      = (ar[lowest_i] >= n)          ? 0           // 0 -> combinations have been exhausted, reset first combination.         : lowest_i+1; // _ -> base incremented. digits right of zero.      (; i<k; ++i)         ar[i] = 0;   }