この質問は、1 <= x <= maxval および x(1) + ... + x(ncells) =目標合計。いくつかのより有望な回答をテストしたので、回答賞を Lennart Regebro に授与します。理由は次のとおりです。
彼のルーティンは私のものと同じくらい速い (+-5%)。
彼は、私の元のルーチンのどこかにバグがあることを指摘しました。ありがとう、レナート。
chrispy は、Lennart のものと同等と思われるアルゴリズムを提供しましたが、5 時間後、すっごく、最初にネットワークに到達しました。
備考: Alex Martelli の必要最小限の再帰アルゴリズムは、考えられるすべての組み合わせを作成し、それらすべてをふるいにかけ、どれが穴を通過するかを確認する例です。このアプローチは、Lennart や私のアプローチよりも 20 倍以上時間がかかります。(入力を max_val = 100、n_cells = 5、target_sum = 250 に上げます。私のボックスでは 18 秒対 8+ 分です。) 道徳: 考えられるすべての組み合わせを生成しないのは良いことです。
別の注意: Lennart のルーチンと私のルーチンは、同じ順序で同じ回答を生成します。実際、それらは異なる角度から見た同じアルゴリズムですか? 知らない。
何かが思い浮かびます。たとえば、(8,8,2,1,1) で始まり (4,4,4,4,4) で終わるように回答を並べ替えると (max_val=8, n_cells=5, target_sum で得られるもの) =20)、シリーズは一種の「最も遅い降下」を形成し、最初のものは「ホット」で、最後のものは「コールド」であり、その間に可能な最大数のステージがあります. これは「情報エントロピー」に関連していますか？それを見るための適切な指標は何ですか？熱の降順 (または昇順) で組み合わせを生成するアルゴリズムはありますか? (これは、正規化された std.dev を見ると、短いストレッチで近いですが、私が見る限りではありません。)
Python ルーチンは次のとおりです。
#!/usr/bin/env python
#filename: makeAddCombos.07.py -- stripped for StackOverflow
def initialize_combo( max_val, n_cells, target_sum):
"""returns combo
Starting from left, fills combo to max_val or an intermediate value from 1 up.
E.g.: Given max_val = 5, n_cells=4, target_sum = 11, creates [5,4,1,1].
"""
combo = []
#Put 1 in each cell.
combo += [1] * n_cells
need = target_sum - sum(combo)
#Fill as many cells as possible to max_val.
n_full_cells = need //(max_val - 1)
top_up = max_val - 1
for i in range( n_full_cells): combo[i] += top_up
need = target_sum - sum(combo)
# Then add the rest to next item.
if need > 0:
combo[n_full_cells] += need
return combo
#def initialize_combo()
def scrunch_left( combo):
"""returns (new_combo,done)
done Boolean; if True, ignore new_combo, all done;
if Falso, new_combo is valid.
Starts a new combo list. Scanning from right to left, looks for first
element at least 2 greater than right-end element.
If one is found, decrements it, then scrunches all available counts on its
right up against its right-hand side. Returns the modified combo.
If none found, (that is, either no step or single step of 1), process
done.
"""
new_combo = []
right_end = combo[-1]
length = len(combo)
c_range = range(length-1, -1, -1)
found_step_gt_1 = False
for index in c_range:
value = combo[index]
if (value - right_end) > 1:
found_step_gt_1 = True
break
if not found_step_gt_1:
return ( new_combo,True)
if index > 0:
new_combo += combo[:index]
ceil = combo[index] - 1
new_combo += [ceil]
new_combo += [1] * ((length - 1) - index)
need = sum(combo[index:]) - sum(new_combo[index:])
fill_height = ceil - 1
ndivf = need // fill_height
nmodf = need % fill_height
if ndivf > 0:
for j in range(index + 1, index + ndivf + 1):
new_combo[j] += fill_height
if nmodf > 0:
new_combo[index + ndivf + 1] += nmodf
return (new_combo, False)
#def scrunch_left()
def make_combos_n_cells_ge_two( combos, max_val, n_cells, target_sum):
"""
Build combos, list of tuples of 2 or more addends.
"""
combo = initialize_combo( max_val, n_cells, target_sum)
combos.append( tuple( combo))
while True:
(combo, done) = scrunch_left( combo)
if done:
break
else:
combos.append( tuple( combo))
return combos
#def make_combos_n_cells_ge_two()
if __name__ == '__main__':
combos = []
max_val = 8
n_cells = 5
target_sum = 20
if n_cells == 1: combos.append( (target_sum,))
else:
combos = make_combos_n_cells_ge_two( combos, max_val, n_cells, target_sum)
import pprint
pprint.pprint( combos)