Generate a matrix of all possible outcomes for thr

Question

In cases where order does matter, it's rather easy to generate the matrix of all possible outcomes. One way for doing this is using expand.grid as shown here.

What if it doesn't?

If I'm right, the number of possible combinations is (S+N-1)!/S!(N-1)!, where S is the number of dice, each with N sides numbered 1 through N. (It is different from the well known combinations formula because it is possible for the same number to appear on more than one dice). For example, when throwing four six-sided dice, N=6 and S=4, so the number of possible combinations is (4+6-1)!/4!(6-1)! = 9!/4!x5! = 126. How can I generate a matrix of these 126 possible outcomes?

Thank you.

Answer 1

Generaly you need to order each outcome from original expand.grid and then unique them, for example using apply:

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

But you can be tricky and choose subset of all outcomes that are ordered:

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

Second version is much faster.

Answer 2

Here is code which gd047 and Marek were kind enough to provide.

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)

Note: this is optimal in the sense that it does not try to generate all and then throw away the dupes. It actually generates only those that are required.

An explanation of why it works:

The possible numbers on the dice are 1 to N.

Suppose you are given a possible combination of the dice numbers: x₁ , x₂ , ..., x_S where S is the number of dice.

Since the order does not matter, we can assume that

x₁ ≤ x₂ ≤ ..., ≤ x_S.

Now consider the sequence x₁, x₂ + 1, x₃ + 2, ..., x_S + S-1.

(Eg: 1,1,1 becomes 1,1+1,1+2 = 1,2,3).

This new sequence has numbers from 1 to N+S-1 and all numbers are distinct.

This mapping from your dice sequence to new one we created is 1-1 and easily reversible.

Thus to generate a possible combination of S dice with numbers 1 to N, all you need to do is to generate all N+S-1 Choose S combinations of S numbers from 1, 2, ..., N+S-1. Given such a combination, you sort it, subtract 0 from the smallest, 1 from the second smallest and so on to get your dice number combination for S dice numbered 1 to N.

For instance, say N = 6 and S = 3.

You generate a combo of 3 numbers from 1 to 6+3-1 = 8, i.e 3 numbers from 1,2,...,8.

Say you get 3,6,7. This translates to 3, 6-1, 7-2 = 3,5,5.

If you got 1,2,8. This would translate to 1,1,6.

Incidentally, this mapping also proves the formula you have.