World's most popular travel blog for travel bloggers.

[Answers] How does one generate a list of size N of all possibilities using a dictionary of size D?

, , No Comments
Problem Detail: 

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 
Asked By : Pinocchio

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/45460

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback