用降序枚举数组中的所有可能性

Question

我正在尝试编写一种递归方法来枚举任意长度数组的所有可能值，其元素都可以降为一个。更正式地说，给定一个包含元素 A_1、A_2、...、A_N 的数组 A 和包含 B_1、B_2... 的数组 B 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

因为我这样做是为了思考问题，所以我很好奇如何：

python itertools 可能使这成为可能
讨论这一系列问题的任何链接
如何更有效地思考我的方法

任何想法表示赞赏。

Answer 1

您正在寻找的功能/工具称为 "Cartesian Product"，它已在许多地方实现，包括 itertools。

itertools.product(*iterables[ 重复])

这也可能有用：link

要达到你的最终目的，你需要的就是所谓的"lexicographical"排序。我不确定是否有易于使用的工具可用，因为我不确定它是否已解决（取决于许多任意排序规则）。但是，您可以查看 Python 文档开始，因为它们有一些 hints 关于字典输出的内容。

Answer 2

基本上每一列都有一组 'allowed' 值。通过从每个集合中选择一个值并将其放入相关列中，您可以生成一个有效的 "related" 数组。你只需要尝试所有的可能性。

递归地，你需要把问题变小。您可以在此处递归数组长度：

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

用降序枚举数组中的所有可能性

Enumerate all possibilities in array with descending values

python

recursion

array-algorithms