Diese Frage bezieht sich auf die Teile der KenKen-Rätsel zum lateinischen Quadrat, bei denen es darum geht, alle möglichen Kombinationen von nZellen-Zahlen mit Werten x zu finden, so dass 1 <= x <= maxval und x(1) + ... + x(nZellen) = Zielsumme. Nachdem ich einige der vielversprechendsten Antworten getestet habe, werde ich den Lösungspreis an Lennart Regebro vergeben, weil:
-
seine Routine ist genauso schnell wie meine (+-5%), und
-
Er wies mich darauf hin, dass meine ursprüngliche Routine irgendwo einen Fehler aufwies, was mich dazu veranlasste, herauszufinden, was sie wirklich zu tun versuchte. Danke, Lennart.
chrispy hat einen Algorithmus beigesteuert, der dem von Lennart gleichwertig zu sein scheint, aber 5 Stunden später, sooo, wer zuerst da ist, bekommt ihn.
Eine Bemerkung: Alex Martellis einfacher rekursiver Algorithmus ist ein Beispiel dafür, dass man alle möglichen Kombinationen durch ein Sieb wirft und dann schaut, welche durch die Löcher passen. Dieser Ansatz dauert 20+ mal länger als der von Lennart oder mir. (Erhöhen Sie die Eingabe auf max_val = 100, n_cells = 5, target_sum = 250 und auf meinem Rechner dauert es 18 Sekunden gegenüber 8+ Minuten). Moral: Nicht jede mögliche Kombination zu generieren ist gut.
Eine weitere Bemerkung: Die Routinen von Lennart und mir erzeugen die gleichen Antworten in der gleichen Reihenfolge . Ist es tatsächlich derselbe Algorithmus, wenn man ihn aus verschiedenen Blickwinkeln betrachtet? Ich weiß es nicht.
Da fällt mir etwas ein. Wenn man die Antworten sortiert, z. B. beginnend mit (8,8,2,1,1) und endend mit (4,4,4,4,4) (was man mit max_val=8, n_cells=5, target_sum=20 erhält), bildet die Reihe eine Art "langsamsten Abstieg", wobei die ersten "heiß" und die letzten "kalt" sind und die größtmögliche Anzahl von Stufen dazwischen liegen. Hat dies mit der "informationellen Entropie" zu tun? Was ist die richtige Metrik, um dies zu betrachten? Gibt es einen Algorithmus, der die Kombinationen in absteigender (oder aufsteigender) Reihenfolge der Wärme erzeugt? (Dieser Algorithmus tut das nicht, soweit ich sehen kann, obwohl er über kurze Strecken nahe dran ist, wenn man die normalisierte Standardabweichung betrachtet).
Hier ist die Python-Routine:
#!/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)
