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