# Enumerating all n-tuples over a finite domain

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.

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 L 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.

• I do not understand this answer at all. What do you mean l in f(l-1,k)? Does [i]+1 even make sense? – Cass Apr 2 '15 at 2:07
• I don't think necessarily yield was what was confusing me. Perhaps I'm too novice to even understand the answer (I wrote something about being a novice initially, but it was deleted by the mods), but there are just several things that confuse me about even the new code. I will explain my confusion in the next comment. – Cass Apr 2 '15 at 2:38
• First, neither code runs without error in Sage, which understands Python (or at least has for me up until now). The first code runs if I change l=0, to l==0. Even with this fix, if I then enter f(2,5), it returns []. Second, I don't understand how l in f(l-1,k) makes sense. In my mind, f(l,k) should be LISTS of length l in integers 0 to k-1. But l is the length, so how can it be both a list and the length of the list? – Cass Apr 2 '15 at 2:56
• Okay, I got a running piece of code that does what I want it to based on your ideas. I edited your post with some syntactical corrections. I will now accept the answer. Thanks for your help. – Cass Apr 2 '15 at 4:00
• Perfect. Thanks much for your patience with all of the bugs in the code and for fixing the additional errors in the code, @Cass. I've approved your edit. – D.W. Apr 2 '15 at 5:39