Jak mogę obliczyć N-tą kombinację tylko na podstawie jej indeksu. Powinny być kombinacje (n + k-1)! / (K! (N-1)!) Z powtórzeniami.

with n=2, k=5 you 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}

Zatem funkcja black_magic_function (3) powinna wygenerować {0,0,1,1,1}.

Będzie to przejście na moduł cieniujący GPU, więc chcę, aby każda grupa robocza / wątek była w stanie określić swój podzbiór permutacji bez konieczności globalnego przechowywania sekwencji.

with n=3, k=5 you 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}

Algorytm generowania można zobaczyć jakoMBnext_multicombination whttp://www.martinbroadhurst.com/combinatorial-algorithms.html

Aktualizacja:

Pomyślałem więc, że zastąpię współczynnik dwumianowy w trójkącie paskalami(n+k-1)!/(k!(n-1)!) aby zobaczyć, jak to wygląda.

(* Mathematica code to display pascal and 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

Porównywanie zn=3,k=5 wyjście konsoli na początku tego posta: trzecia przekątna{3,6,10,15,21,28,36} podaje indeks każdego punktu przewrócenia{0,0,0,1,1} -> {0,0,1,1,1} -> {0,1,1,1,1}itd. Przekątna po lewej stronie wydaje się pokazywać, ile wartości zawiera poprzedni blok (diagonal[2][i] == diagonal[3][i] - diagonal[3][i-1])). A jeśli przeczytasz 5-ty rząd piramidy poziomo, uzyskasz maksymalną liczbę kombinacji dla zwiększenia wartości N w(n+k-1)!/(k!(n-1)!) gdzieK=5.

Prawdopodobnie istnieje sposób na wykorzystanie tych informacji do określenia dokładnej kombinacji dla dowolnego indeksu, bez wyliczania całego zestawu, ale nie jestem pewien, czy muszę iść tak daleko. Pierwotny problem polegał na rozłożeniu pełnej przestrzeni kombi na równe podzbiory, które mogą być generowane lokalnie i równolegle przez GPU. Tak więc powyższy trójkąt daje nam indeks początkowy każdego bloku, którego kombinacja może być trywialnie wyprowadzona, a wszystkie jego kolejne elementy są wyliczane stopniowo. Daje nam także rozmiar bloku i ile mamy wszystkich kombinacji. Więc teraz staje się problemem pakowania, jak dopasować nierównomierne rozmiary bloków do grup o równym obciążeniu pracą w X ilości wątków.