bonhoffer - 1 year ago 58

Python Question

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
- any links that talk about this family of problems
- how to more efficiently think about my approach

Any thoughts appreciated.

Answer Source

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))
```