bonhoffer - 1 year ago 83
Python Question

# Enumerate all possibilities in array with descending values

I'm trying to write a recursive approach to enumerate all possible values of an array of arbitrary length whose elements can all descend to one. More formally, given an array A with the elements, A_1, A_2,...,A_N and array B with B_1,B_2...B_N. There is a relationship between A_i and B_i, where i is between 1 and N and any element A_i lies between 1 and B_i. For such a set of arrays, I want to find all possible states for A_i.

For example, the array [1 2 3] has the following six possible states:

``` [1 1 1] [1 2 1] [1 1 2] [1 1 3] [1 2 2] [1 2 3] ```

[1 2] would produce [1 1] and [1 2], etc

I've tried a solution in python such as:

``````b = [1, 3, 3]
n = len(b)

a = []
k = 0
r = 0

print b
print '------'

def f(i, k, a, r):
k += 1
if i == n-1:
return False
for j in range(1, b[i+1]+1):
r += 1
print "i: %d b[i]: %d k: %d new: %d r: %d" % (i, b[i], k, j, r)
f(i+1, k, a, r)

f(0, k, a, r)
``````

but I can't seem to get the right values and I can't get the data-structure to populate. For example [3 3] only produces a tree with three nodes or the result:

``````[3, 3]
------
i: 0 b[i]: 3 k: 1 new: 1 r: 1
i: 0 b[i]: 3 k: 1 new: 2 r: 2
i: 0 b[i]: 3 k: 1 new: 3 r: 3
``````

Since I'm doing this to think through problems, I'm curious how:

• the python itertools might make this possible

• how to more efficiently think about my approach

Any thoughts appreciated.

Basically for every column you have a set of 'allowed' values. By picking a value from each of these sets and putting it in a relevant column you generate a valid "related" array. You just need to try all the possibilities.

Recursively, you need to make problem smaller. You may recurse on array length here:

``````def enumerate(v):
if len(v) == 0:
yield v
else:
for i in range(1, v[0] + 1):
for rest in enumerate(v[1:]):
yield [i] + rest
``````

And you can have same effect with itertools, with no explicit recurrence:

``````def enumerate2(v):
from itertools import product
return product(*(range(1, e+1) for e in v))
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download