[Solved]: Enumerating all n-tuples over a finite domain

Problem Detail: 

I would like to create an algorithm which takes in an integer n and returns an array whose entries give all n-tuples of nonnegative integers each of which is at most n, so like

• A[n][0] = [0,0,0,...,0],
• A[n][1] = [1,0,0,...,0], ...,
• A[n][n^(n+1)]=[n,n,n,...,n],

that kind of thing.

If n is small, I can manually create n-many for loops to do this, but in general I would like to allow n to be large. Is there an easy workaround? Any help would be appreciated.

Asked By : Cass

Answered By : D.W.

Use recursion. Something like this:

def f(l, k):     if l==0:         yield []     else:         for i in range(k):             for L in f(l-1, k):                 yield [i]+L 

Here f(l, k) produces all lists of length l all of whose entries are in the range 0..k-1. The idea is that if you have all lists of length l-1 (the output of f(l-1, k)) you can use that to generate all lists of length l, by using a for-loop.

If you're not familiar with that Python syntax, try this variant:

def f(l, k):     if l==0:         return [[]]     t = []      for i in range(k):         for i in f(l-1, k):             t.append([i]+l)     return t 

Note that [i] is a list containing a single element, i, and + is the list concatenation operator, so [i]+l is a list obtained by prepending the element i to the front of list l.

Best Answer from StackOverflow

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

 Ask a Question

 Download Related Notes/Documents