Python: Recursion to count up an array of size n

Question

I am struggling about a recursion problem, which should not be too hard, but for some reason I don't come up with a solution.

I have an array of size "n" and I want to count up each element from 0 to n in a way that I get each possible combination.

n = 3
[0,0,0]
[0,0,1]
[0,1,0]
[1,0,0]
[...  ]
[3,3,3]

Can anyone help?

Welcome to Stack Overflow! It looks like you want us to write some code for you. While many users are willing to produce code for a coder in distress, they usually only help when the poster has already tried to solve the problem on their own. A good way to demonstrate this effort is to include the code you've written so far, example input (if there is any), the expected output, and the output you actually get (console output, stack traces, compiler errors - whatever is applicable). The more detail you provide, the more answers you are likely to receive. — Martijn Pieters
– Martijn Pieters, Commented Dec 11, 2012 at 17:24
@NedBatchelder: How? The homework tag is not to be used anymore. Questions, even those about homework, need to stand on their own without being too localized or requiring us to pussyfoot around the solution. — Martijn Pieters
– Martijn Pieters, Commented Dec 11, 2012 at 17:25

NPE · Accepted Answer · 2012-12-11 17:32:37Z

3

If you have to code it up yourself, and have to use recursion:

def gen(n, l, prefix=()):
  if l == 0:
    print prefix
  else:
    for i in range(n):
      gen(n, l - 1, prefix + (i,))

gen(4, 3)

edited Dec 11, 2012 at 17:32

answered Dec 11, 2012 at 17:28

NPE

503k114 gold badges970 silver badges1k bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Trollbrot Over a year ago

I guess I will go with the itertools solution, but thanks good to see what I was trying to come up with.

Ned Batchelder · Accepted Answer · 2012-12-11 17:29:58Z

1

No need for (explicit) recursion:

import itertools
for comb in itertools.product(range(4), repeat=3):
    print comb

produces:

(0, 0, 0)
(0, 0, 1)
(0, 0, 2)
(0, 0, 3)
(0, 1, 0)
(0, 1, 1)
...
(3, 3, 2)
(3, 3, 3)

answered Dec 11, 2012 at 17:29

Ned Batchelder

378k77 gold badges583 silver badges675 bronze badges

1 Comment

Trollbrot Over a year ago

Thanks a lot, did not know about the function.

recursive · Accepted Answer · 2012-12-11 17:29:04Z

0

Here's one way to do it that makes the procedure very explicit:

def combinations(n, elements = None):
    if elements == 0: return [[]]

    if not elements: elements = n

    result = []
    for v in range(n + 1):
        for subcombination in combinations(n, elements - 1):
            result.append([v] + subcombination)

    return result

There are more pythonic ways to do it that might have better performance, including comprehensions or generators, but it sounds like you're looking for an explicit implementation.

answered Dec 11, 2012 at 17:29

recursive

86.5k36 gold badges155 silver badges246 bronze badges

Collectives™ on Stack Overflow

Python: Recursion to count up an array of size n

3 Answers 3

1 Comment

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related