枚举所有可能性与数组递减值

我想写一个递归方法来枚举任意长度的数组的所有可能的值，其元素可以全部下降到一个。更正式地说，给定一个数组A，元素A_1，A_2，...，A_N和数组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)

，但我似乎无法得到正确的价值观，我无法获取数据结构来填充。例如[3 3]只生产有三个节点或结果的树：

[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

因为我这样做是想通过的问题，我很好奇如何：

蟒蛇itertools可能作出这样的谈论这个家庭的问题
这可能
任何链接如何更有效地去想我的做法

任何想法赞赏。

来源

2016-06-28 bonhoffer

基本上对于每一列你都有一组“允许”值。通过从这些集合中选取一个值并将其放入相关列中，可以生成一个有效的“相关”数组。你只需要尝试所有的可能性。

递归地，您需要减小问题。您可以递归就在这里数组的长度：

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

来源

2016-06-28 21:57:16

哇 - 好的 - 谢谢 – bonhoffer

您正在寻找的功能/工具被称为“笛卡尔积”，该功能已在许多地方实现，包括itertools。

itertools.product（* iterables [重复]）

这也可能是有用的：link

实现自己的最终目标，你需要的是所谓的 “辞书” 排序。我不确定是否有易于使用的工具可用，因为我不确定它是否已解决问题（取决于许多任意的排序规则）。但是，您可以查看Python文档以开始使用，因为他们有关于词典输出的一些hints。

来源

2016-06-28 21:24:13 sirgogo

感谢。我会研究一下。 – bonhoffer

我不确定下降的元素是如何笛卡儿的产品。你能解释一下吗？ – bonhoffer

嗯，我认为首先你会使用笛卡尔产品来快速生成所有的可能性。然后，根据您的喜好，您将开始整理列。根据您如何调用笛卡尔产品，列表可能已被排序。 – sirgogo

枚举所有可能性与数组递减值

回答

相关问题