1
$\begingroup$

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
$\endgroup$
1

2 Answers 2

2
$\begingroup$

There is no need to use recursion. You can use high-school addition instead. Here is pseudocode that generates all answers in lexicographic order.

Initialize A[0] = ... = A[n-1] = 0
Repeat
  Output A
  i = n
  Repeat
    i = i - 1
    A[i] = (A[i] + 1) mod D
  Until A[i] ≠ 0 Or i = 0
Until A[i] = 0

This algorithm thinks of the contents of A as a number in base D, which it repeatedly increments. Incrementing A proceeds as follows. We first increment the rightmost digit. If it increments to D, we change it back to 0, and then move one digit to the left. We continue this way until some digit increments to a non-zero number, or until we reach the end of the number.

$\endgroup$
2
$\begingroup$

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 => 
        D.map { 
          d => l ++ [d] 
        }
      }.flatten
  }
}

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

$\endgroup$
3
  • $\begingroup$ just when I updated my question with a potential sol. I forgot to write the base case in mine. $\endgroup$ Aug 21, 2015 at 20:46
  • $\begingroup$ is that written on pseudo-mathematica? Not sure what ur functions are suppose to be doing...flatten? hmm... $\endgroup$ Aug 21, 2015 at 20:48
  • $\begingroup$ @Pinocchio More like pseudo-Ruby, I guess. map is clear? flatten takes a list of lists and makes it a lists, so e.g. [[1,2,3],[4,5,6]].flatten gives [1,2,3,4,5,6]. If course, here we have a list of list of lists which is flattened to a list of lists. $\endgroup$
    – Raphael
    Aug 21, 2015 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.