CODEWITHSUNDEEP
pythonrecursion
Trollbrot
Trollbrot

Reputation: 1351

Python: Recursion to count up an array of size n

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?

Upvotes: 0

Views: 388

Answers (3)

NPE
NPE

Reputation: 500367

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)

Upvotes: 3

Ned Batchelder
Ned Batchelder

Reputation: 375594

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)

Upvotes: 1

recursive
recursive

Reputation: 86084

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.

Upvotes: 0

Related Questions