3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I do not understand this answer at all. What do you mean l in f(l-1,k)? Does [i]+1 even make sense? $\endgroup$ – Cass Apr 2 '15 at 2:07
  • $\begingroup$ 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. $\endgroup$ – Cass Apr 2 '15 at 2:38
  • $\begingroup$ 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? $\endgroup$ – Cass Apr 2 '15 at 2:56
  • $\begingroup$ 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. $\endgroup$ – Cass Apr 2 '15 at 4:00
  • $\begingroup$ 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. $\endgroup$ – D.W. Apr 2 '15 at 5:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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