Generowanie wszystkich permutacji kulek N w grupach M

Question

Chcę wygenerować zestaw permutacji kulek n w pojemnikach m. Poniższy zestaw zagnieżdżonych list generuje te permutacje.

n <- 3 
m <- 4 
v <- rep(0,m) 
for (i in n:0){ 
    for (j in (n-sum(i)):0){ 
    for (k in (n-sum(i,j)):0){ 
     for (l in (n - sum(i,j,k)):0){ 
     v <- c(i,j,k,l) 
     print(v) 
     if (sum(v) == n){ break } 
     } 
    } 
    } 
} 

która drukuje rozwiązanie:

[1] 3 0 0 0 
[1] 2 1 0 0 
[1] 2 0 1 0 
[1] 2 0 0 1 
[1] 1 2 0 0 
[1] 1 1 1 0 
[1] 1 1 0 1 
[1] 1 0 2 0 
[1] 1 0 1 1 
[1] 1 0 0 2 
[1] 0 3 0 0 
[1] 0 2 1 0 
[1] 0 2 0 1 
[1] 0 1 2 0 
[1] 0 1 1 1 
[1] 0 1 0 2 
[1] 0 0 3 0 
[1] 0 0 2 1 
[1] 0 0 1 2 
[1] 0 0 0 3 

Łączna liczba permutacji będzie choose(n+m-1,m-1), a porządek permutacji nie ma dla mnie znaczenia. Ale trudno mi zrobić z tego funkcję, która może przyjąć dowolną liczbę pojemników. (Nie zepsuje to dobrze moimi próbami, jest to po prostu zbieranina zagnieżdżonych pętli.) Więc jeśli ktoś bardziej sumienny ode mnie mógłby przetłumaczyć zagnieżdżone pętle w funkcję, byłbym wdzięczny.

Jeśli dostępna jest już funkcja do przeprowadzenia tego typu permutacji (lub innego algorytmu do zastosowania), byłbym wdzięczny za informację o tym. Wolałbym podejście, które nie generuje zbędnych permutacji (tutaj, które nie sumują się do n), a następnie je odrzuca, ale w przypadku małych problemów, takich jak to, rozwiązanie, które to robi byłoby do zaakceptowania.

Answer 1

library(partitions) 
compositions(3,4) 

# [1,] 3 2 1 0 2 1 0 1 0 0 2 1 0 1 0 0 1 0 0 0 
# [2,] 0 1 2 3 0 1 2 0 1 0 0 1 2 0 1 0 0 1 0 0 
# [3,] 0 0 0 0 1 1 1 2 2 3 0 0 0 1 1 2 0 0 1 0 
# [4,] 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 3 

Answer 2

Poniżej przedstawiono nieco inną, ale równoważną odpowiedź za pomocą bardziej ogólny pakiet iterpc

m = 4; n = 3 
library(iterpc) 
I = iterpc(m, n, replace=T) 
getall(I) 

Wyjście jest takie numery bin dla n kul.

 [,1] [,2] [,3] 
[1,] 1 1 1 
[2,] 1 1 2 
.... 
.... 
[18,] 3 3 4 
[19,] 3 4 4 
[20,] 4 4 4 

Pierwsza linia oznacza, że ​​3 kulki są z pojemnika 1, podczas gdy ostatnia linia oznacza, że ​​3 kulki są z kosza 4.

można łatwo wytworzyć pożądany rezultat poprzez zliczanie liczby 1, 2, 3 i 4. Możesz także użyć iteratora, aby wygenerować wynik sekwencyjnie.

count <- function(x){ 
    as.numeric(table(factor(x, levels=1:m))) 
} 
I = iterpc(m, n, replace=T) 


> count(getnext(I)) 
[1] 3 0 0 0 
> count(getnext(I)) 
[1] 2 1 0 0 
> count(getnext(I)) 
[1] 2 0 1 0 
> count(getnext(I)) 
[1] 2 0 0 1