How does one generate a list of size N of all possibilities using a dictionary of size D? Say that we have a list of size $N$ to fill with elements of a dictionary of size $D$. So we would have in total $D^N$ elements/possibilities.

It makes sense to me how to write an algorithm for this when the number of possible slots to fill $N$ is fixed. For example if $N = 2$:

A %array of size (D x D x D) = D^3
for i1=1:3
    for i2=1:3
        for i3=1:3
            A[i1,i2,i3] = (i1,i2,i3)


however, I was having some issue generalize such algorithm because it wasn't clear to me how to extend this chain of for loops for general N. Someone have an idea how to do this?



I think the recursive solution is:

V %dictionary of size D
N %number of slots
def combos(n)
    if n==1:
        return V
    answers = []
    for combo in combos(n-1):
        for word in V:
                answers.append(combo+word)
    return answers
The answer is elementary: recursion!

The underlying observation is that if you can create lists of size $N-1$, you can easily create lists of size $N$ by just appending any one of the $D$ values to every $N-1$ long list.

In pseudo code:

def all_possibilities(n, D) {
  if ( n == 0 ) {
    return [[]]
  }
  else {
    smaller = all_possibilities(n-1,D)
    return smaller.map { l =&gt; 
        D.map { 
          d =&gt; l ++ [d] 
        }
      }.flatten
  }
}


You can prove this correct by induction over $N$.