我试图编写一个递归方法来枚举任意长度的数组的所有可能值,其元素都可以下降到1。更正式地说,给定一个数组A,其中包含元素A_1, A_2,…数组B与B_1,B_2…B_N。A_i和B_i之间存在关系,其中i介于1和N之间,任意元素A_i介于1和B_i之间。对于这样一组数组,我想找到A_i的所有可能状态。
例如,数组[1 2 3]有以下六种可能的状态:
[1 1 1]
[1 2 1]
[1 1 2]
[1 1 3]
[1 2 2]
[1 2 3]
[1 2]将产生[1 1]和[1 2],等等
我在python中尝试了一个解决方案,例如:
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)
,但我似乎不能得到正确的值,我不能得到数据结构填充。例如[33]只生成一个有三个节点的树,或者结果:
[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
既然我这样做是为了思考问题,我很好奇如何:
- python itertools可能会使这成为可能
- 任何关于这类问题的链接
- 如何更有效地思考我的方法
你正在寻找的函数/工具被称为"笛卡尔积",它已经在许多地方实现了,包括itertools。
出现itertools。产品(* iterable(重复)
这也可能有用:link
为了达到最终目标,你需要的是所谓的"字典法"排序。我不确定是否有易于使用的工具,因为我不确定这是一个已解决的问题(取决于许多任意排序规则)。但是,您可以查看Python文档来开始,因为它们有一些关于字典输出的提示。
基本上每个列都有一组'允许'的值。通过从这些集合中选择一个值并将其放入相关列中,可以生成一个有效的"相关"数组。你只需要尝试所有的可能性。
递归地,你需要使问题更小。你可以对数组长度进行递归:
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
你可以用itertools达到同样的效果,没有显式递归:
def enumerate2(v):
from itertools import product
return product(*(range(1, e+1) for e in v))