Генерация матрицы всех возможных результатов для броска n кубиков (игнорируя порядок)

Question

В тех случаях, когда порядок имеет значение, довольно просто сгенерировать матрицу всех возможных результатов.Один из способов сделать это - использовать expand.grid, как показано здесь .

Что, если это не так?

Если я прав, число возможных комбинаций равно (S+N-1)!/S!(N-1)!, где S - количество кубиков, каждая из которых имеет N сторон, пронумерованных от 1 до N. (Это отличается от хорошо известной формулы комбинаций, потому чтоодин и тот же номер может появиться на нескольких кубиках).Например, при броске четырех шестигранных кубиков N = 6 и S = ​​4, поэтому число возможных комбинаций равно (4 + 6-1)! / 4! (6-1)!= 9! / 4! X5!= 126. Как я могу сгенерировать матрицу из этих 126 возможных результатов?

Спасибо.

Answer 1

Вот код, который gd047 и Marek были достаточно любезны, чтобы предоставить.

S <- 6 
N <- 4 
n <- choose(S+N-1,N) 
outcomes <- t(combn(S+N-1,N,sort)) - matrix(rep(c(0:(N-1)),each=n),nrow=n)

Примечание: это оптимально в том смысле, что он не пытается генерировать все, а затем выбрасывать дубликаты. It actually generates only those that are required.

Объяснение того, почему это работает:

Возможные числа на кости - от 1 до N.

Предположим, вам дана возможная комбинация чисел игральных костей: x ₁ , x ₂ , ..., x _S , где S - число кости.

Поскольку порядок не имеет значения, мы можем предположить, что

x ₁ & le; x ₂ & le; ..., & le; х _S .

Теперь рассмотрим последовательность x ₁ , x ₂ + 1, x ₃ + 2, ..., x _S + S-1.

(Например: 1,1,1 становится 1,1 + 1,1 + 2 = 1,2,3).

Эта новая последовательность имеет номера от 1 до N + S-1, и все числа различны.

Это отображение вашей последовательности костей на новую, которую мы создали, 1-1 и легко обратимо.

Таким образом, чтобы сгенерировать возможную комбинацию S кубиков с номерами от 1 до N, все, что вам нужно сделать, это сгенерировать все N + S-1. Выберите S комбинаций из S чисел из 1, 2, ..., N + S. -1. Учитывая такую ​​комбинацию, вы сортируете ее, вычитаете 0 из наименьшего, 1 из второго наименьшего и т. Д., Чтобы получить комбинацию чисел для ваших костей для S, пронумерованных от 1 до N.

Например, скажем, N = 6 и S = ​​3.

Вы генерируете комбо из 3 чисел от 1 до 6 + 3-1 = 8, то есть 3 числа от 1,2, ..., 8.

Скажем, вы получаете 3,6,7. Это переводится как 3, 6-1, 7-2 = 3,5,5.

Если вы получили 1,2,8. Это будет переводить на 1,1,6.

Кстати, это отображение также подтверждает вашу формулу.

Answer 2

Как правило, вам нужно заказать каждый исход из оригинала expand.grid, а затем unique их, например, с помощью apply:

X <- expand.grid(1:6,1:6,1:6,1:6)
dim(unique(t(apply(X,1,sort))))
#[1] 126   4

Но вы можете быть хитрым и выбрать подмножество всех упорядоченных результатов:

X <- expand.grid(1:6,1:6,1:6,1:6)
dim(subset(X, Var1>=Var2 & Var2>=Var3 & Var3>=Var4))
# [1] 126   4

Вторая версия намного быстрее.