使用特定规则在Python中生成排列

Question

假设 a=[A, B, C, D]，每个元素都有一个权重 w，如果选择则设置为 1，否则为 0。我想按以下顺序生成排列。

1,1,1,1
1,1,1,0
1,1,0,1
1,1,0,0
1,0,1,1
1,0,1,0
1,0,0,1
1,0,0,0

0,1,1,1
0,1,1,0
0,1,0,1
0,1,0,0
0,0,1,1
0,0,1,0
0,0,0,1
0,0,0,0

让我们使用w=[1,2,3,4]代表物品A、B、C、D ... 并且max_weight=4。对于每个排列，如果累计重量超过了max_weight，则停止该排列的计算并转移到下一个排列。例如：

1,1,1    --> 6 > 4, exceeded, stop, move to next
1,1,1    --> 6 > 4, exceeded, stop, move to next  
1,1,0,1  --> 7 > 4  finished, move to next  
1,1,0,0  --> 3      finished, move to next  
1,0,1,1  --> 8 > 4, finished, move to next
1,0,1,0  --> 4      finished, move to next  
1,0,0,1  --> 5 > 4  finished, move to next  
1,0,0,0  --> 1      finished, move to next  
etc calculation continue

到目前为止，[1,0,1,0] 是最佳组合，没有超过最大重量 4

我的问题是：

1. 生成所需排列的算法是什么？或者有什么建议可以生成排列？
2. 由于元素数量可能高达 10000，并且如果分支的累积重量超过 max_weight，则计算会停止，因此在计算之前不必先生成所有排列。如何使第一步中的算法即时生成排列？

- twfx

---

你是否保存了所有的排列组合？ - Achrome

不，只有当前最佳的排列（不超过max_weight）将被存储。因此，基于生成的顺序，[1,1,0,0] 将被存储，然后稍后用 [1,0,1,0] 替换它等。 - twfx

@twfx：你想用这个做什么？ - Blender

是的，我正在尝试实现迭代深度优先分支限界算法来解决背包问题。但是我卡在如何按照指定排列遍历树这一点上。 - twfx

对于第一个问题，请注意您正在以二进制形式从2^n - 1到0生成数字。 - bbayles

Answer 1

使用 itertools.product函数生成排列。

from itertools import *

w = [1,2,3,4]
max_weight = 4
for selection in product([1,0], repeat=len(w)):
    accum = sum(compress(w, selection))
    if accum > 4:
        print '{}  --> {} > {}, exceeded, stop, move to next'.format(selection, accum, max_weight)
    else:
        print '{}  --> {}    , finished, move to next'.format(selection, accum)

使用itertools.compress来通过选择过滤权重。

>>> from itertools import *
>>> compress([1,2,3,4], [1,0,1,1])
<itertools.compress object at 0x00000000027A07F0>
>>> list(compress([1,2,3,4], [1,0,1,1]))
[1, 3, 4]

- falsetru

Answer 2

手动实现的话，你可以这样做（不过我推荐使用 itertools）：

t = [1,0]
max = 4
ans = [[i,j,k,l] for i in t for j in t for k in t for l in t if i*1+j*2+k*3+l*4 <= max]
#[[1, 1, 0, 0],
# [1, 0, 1, 0],
# [1, 0, 0, 0],
# [0, 1, 0, 0],
# [0, 0, 1, 0],
# [0, 0, 0, 1],
# [0, 0, 0, 0]]

- Saullo G. P. Castro