4

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

アイテム A、B、C、D の w=[1,2,3,4] とします。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] が max_weight 4 を超えないベストな組み合わせです

私の質問は

  1. 必要な順列を生成するアルゴリズムは何ですか? または、順列を生成できる提案はありますか?
  2. 要素数は 10000 まで可能で、枝の累積重みが max_weight を超えると計算が停止するため、計算前にすべての順列を最初に生成する必要はありません。(1) のアルゴリズムは、どのようにその場で順列を生成できますか?
4

2 に答える 2

4

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]
于 2013-06-30T07:05:00.400 に答える
0

手動で、次のようにすることができます（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]]
于 2013-06-30T07:35:10.153 に答える