bonhoffer bonhoffer - 1 year ago 58
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

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