KenKen Puzzle Addenden: REDUX A (korrigiert) nicht-rekursiven Algorithmus

Question

Diese Frage bezieht sich auf die Teile der KenKen Latin-Square-Rätsel, die Sie bitten, alle möglichen Kombinationen von ncells Zahlen zu finden, mit Werten x, so dass 1 <= x <= maxwert und x (1) + ... + x ( ncells) = targetsum. einige der vielversprechendsten Antworten getestet zu haben, werde ich die Antwort-Preis an Lennart Regebro zu vergeben, denn:

1. seine Routine ist so schnell wie mein (+ -5%) und

2. Er wies darauf hin, dass meine ursprüngliche Routine irgendwo einen Fehler hatte, was mich zu sehen, was es wirklich tun wollte. Danke, Lennart.

chrispy beigetragen einen Algorithmus, der auf Lennart Äquivalent scheint, aber 5 Stunden später, sooo, zuerst an den Draht wird es.

Eine Bemerkung: Alex Martelli nackte Knochen rekursiven Algorithmus ist ein Beispiel für jede mögliche Kombination zu machen und sie alle auf einem Sieb und Sehen zu werfen, die durch die Löcher gehen. Dieser Ansatz nimmt 20+ mal länger als Lennart oder Mine. (Aufbocken Eingang MAX_VAL = 100, n_cells = 5, target_sum = 250 und auf meiner Box ist es 18 Sekunden gegen 8+ Min.) Moral:. Nicht jede mögliche Kombination zu erzeugen ist gut

Eine weitere Bemerkung: Lennart und meine Routinen erzeugen die gleichen Antworten in der gleichen Reihenfolge . Sind sie in der Tat der gleiche Algorithmus aus verschiedenen Winkeln gesehen? Ich weiß es nicht.

Etwas fällt mir. Wenn Sie die Antworten sortieren, beginnend etwa mit (8,8,2,1,1) und endend mit (4,4,4,4,4) (was man bekommt mit MAX_VAL = 8, n_cells = 5, target_sum = 20), bildet die Reihe Art „langsamsten descent“, wobei die ersten, die „heißen“ und das letzte ist „kalt“ und die größtmögliche Anzahl von Stufen dazwischen zu sein. Ist dies im Zusammenhang mit „Informations Entropie“? Was ist die richtige Metrik es sucht sie? Gibt es einen Algorithmus, der die Kombinationen in absteigender (oder aufsteigend) Reihenfolge der Wärme producs? (Dies funktioniert nicht, soweit ich sehen kann, obwohl es in der Nähe über kurze Strecken ist, auf normalisierte std suchen. Dev).

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)

Answer 1

Zunächst einmal würde ich Variablennamen verwenden, die etwas bedeuten, so dass der Code verständlich wird. Dann, nachdem ich das Problem verstanden, es ist eindeutig ein rekursive Problem, als wenn Sie eine Nummer gewählt haben, die Frage der möglichen Werte für den Rest der Quadrate zu finden sind genau das gleiche Problem, aber mit unterschiedlichen Werten in.

Also habe ich es so tun würde:

from __future__ import division
from math import ceil

def make_combos(max_val,target_sum,n_cells):
    combos = []
    # The highest possible value of the next cell is whatever is 
    # largest of the max_val, or the target_sum minus the number 
    # of remaining cells (as you can't enter 0).
    highest = min(max_val, target_sum - n_cells + 1)
    # The lowest is the lowest number you can have that will add upp to 
    # target_sum if you multiply it with n_cells.
    lowest = int(ceil(target_sum/n_cells))
    for x in range(highest, lowest-1, -1):
        if n_cells == 1: # This is the last cell, no more recursion.
            combos.append((x,))
            break
        # Recurse to get the next cell:
        # Set the max to x (or we'll get duplicates like
        # (6,3,2,1) and (6,2,3,1), which is pointless.
        # Reduce the target_sum with x to keep the sum correct.
        # Reduce the number of cells with 1.
        for combo in make_combos(x, target_sum-x, n_cells-1):
            combos.append((x,)+combo)
    return combos

if __name__ == '__main__':
    import pprint
    # And by using pprint the output gets easier to read
    pprint.pprint(make_combos( 6,12,4))

ich auch feststellen, dass Ihre Lösung noch buggy zu sein scheint. Für die Werte max_val=8, target_sum=20 and n_cells=5 Ihr Code nicht die Lösung (8,6,4,1,1,) findet, als Beispiel. Ich bin mir nicht sicher, ob das bedeutet, dass ich eine Regel in dieser verpasst haben oder nicht, aber als ich die Regeln verstehen, dass sollte eine gültige Option sein.

Hier ist eine Version Generator, spart ein paar Zeilen, und Speicher, wenn die Werte wirklich groß sind, aber als Rekursion können Generatoren schwierig zu „get“.

from __future__ import division
from math import ceil

def make_combos(max_val,target_sum,n_cells):
    highest = min(max_val, target_sum - n_cells + 1)
    lowest = int(ceil(target_sum/n_cells))
    for x in xrange(highest, lowest-1, -1):
        if n_cells == 1:
            yield (x,)
            break
        for combo in make_combos(x, target_sum-x, n_cells-1):
            yield (x,)+combo

if __name__ == '__main__':
    import pprint
    pprint.pprint(list(make_combos( 6,12,4)))

Answer 2

Ihr Algorithmus scheint auf den ersten Blick ziemlich gut, und ich glaube nicht, OO oder eine andere Sprache würde den Code verbessern. Ich kann nicht sagen, ob Rekursion geholfen hätte, aber ich bewundere den nicht-rekursive Ansatz. Ich wette, es schwieriger zu bekommen war zu arbeiten und es ist schwieriger zu lesen, aber es ist wahrscheinlich, effizientes und es ist auf jeden Fall ziemlich clever. Um ehrlich zu sein, ich habe nicht den Algorithmus im Detail analysieren, aber es sieht aus wie etwas, das eine lange Zeit dauerte zu bekommen richtig funktioniert. Ich wette, es gab viele off-by-1 Fehler und seltsame Rand Fällen Sie durch denken hatte, nicht wahr?

Da alle, im Grunde alles, was ich versuchte, war ziemlich hoch, Ihr Code zu tun, so gut ich konnte durch den zahlreichen C-isms mit mehr idiomatischen Python-isms ersetzen. Oft, was eine Schleife in C benötigt, kann in einer Zeile in Python getan werden. Auch habe ich versucht, Dinge zu benennen Python-Namenskonventionen besser zu folgen und die Kommentare etwas aufgeräumt. Hoffe, dass ich beleidige Sie nicht mit irgendwelchen meiner Änderungen. Sie können das, was Sie wollen und den Rest lassen. : -)

Hier sind die Noten, die ich nahm, wie ich gearbeitet:

• Changed den Code, den tmp zu einem Bündel von 1en in dem mehr idiomatischen tmp = [1] * n_cells initialisiert.
• Changed for Schleife, die tmp_sum zu idiomatischem sum(tmp) fasst.
• ersetzt dann alle Schleifen mit einem tmp = <list> + <list> Einzeiler.
• Verschoben raise doneException init_tmp_new_ceiling und bekam von der succeeded Flagge los zu werden.
• Die Prüfung in init_tmp_new_ceiling scheint eigentlich überflüssig. Entfernen sie verließen die nur raises waren in make_combos_n_cells, also habe ich nur solche auf normalen Renditen und fiel doneException ganz.
• Normalized Mischung aus 4 Räumen und 8 Räume für Einbuchtung.
• Entfernt unnötige Klammern um Ihre if Bedingungen.
• tmp[p2] - tmp[p1] == 0 ist die gleiche wie tmp[p2] == tmp[p1].
• Changed while True: if new_ceiling_flag: break while not new_ceiling_flag.
• Sie brauchen keine Variablen auf 0 an der Spitze Ihrer Funktionen zu initialisieren.
• Entfernt combos Liste und geänderte Funktion yield seine Tupel wie sie erzeugt werden.
• Umbenannt tmp combo.
• Umbenannt new_ceiling_flag ceiling_changed.

Und hier ist der Code zum Nachlesen:

def initial_combo(ceiling=5, target_sum=13, num_cells=4):
    """
    Returns a list of possible addends, probably to be modified further.
    Starts a new combo list, then, starting from left, fills items to ceiling
    or intermediate between 1 and ceiling or just 1.  E.g.:
    Given ceiling = 5, target_sum = 13, num_cells = 4: creates [5,5,2,1].
    """
    num_full_cells = (target_sum - num_cells) // (ceiling - 1)

    combo = [ceiling] * num_full_cells \
          + [1]       * (num_cells - num_full_cells)

    if num_cells > num_full_cells:
        combo[num_full_cells] += target_sum - sum(combo)

    return combo

def all_combos(ceiling, target_sum, num_cells):
    # p0   points at the rightmost item and moves left under some conditions
    # p1   starts out at rightmost items and steps left
    # p2   starts out immediately to the left of p1 and steps left as p1 does
    #      So, combo[p2] and combo[p1] always point at a pair of adjacent items.
    # d    combo[p2] - combo[p1]; immediate difference
    # cd   combo[p2] - combo[p0]; cumulative difference

    # The ceiling decreases by 1 each iteration.
    while True:
        combo = initial_combo(ceiling, target_sum, num_cells)
        yield tuple(combo)

        ceiling_changed = False

        # Generate all of the remaining combos with this ceiling.
        while not ceiling_changed:
            p2, p1, p0 = -2, -1, -1

            while combo[p2] == combo[p1] and abs(p2) <= num_cells:
                # 3,3,3,3
                if abs(p2) == num_cells:
                    return

                p2 -= 1
                p1 -= 1
                p0 -= 1

            cd = 0

            # slide_ptrs_left loop
            while abs(p2) <= num_cells:
                d   = combo[p2] - combo[p1]
                cd += d

                # 5,5,3,3 or 5,5,4,3
                if cd > 1:
                    if abs(p2) < num_cells:
                        # 5,5,3,3 --> 5,4,4,3
                        if d > 1:
                            combo[p2] -= 1
                            combo[p1] += 1
                        # d == 1; 5,5,4,3 --> 5,4,4,4
                        else:
                            combo[p2] -= 1
                            combo[p0] += 1

                        yield tuple(combo)

                    # abs(p2) == num_cells; 5,4,4,3
                    else:
                        ceiling -= 1
                        ceiling_changed = True

                    # Resume at make_combo_same_ceiling while
                    # and follow branch.
                    break

                # 4,3,3,3 or 4,4,3,3
                elif cd == 1:
                    if abs(p2) == num_cells:
                        return

                    p1 -= 1
                    p2 -= 1

if __name__ == '__main__':
    print list(all_combos(ceiling=6, target_sum=12, num_cells=4))

Answer 3

Hier ist die einfachste rekursive Lösung, die ich mir vorstellen kann „, um alle möglichen Kombinationen von n Zahlen mit Werten x zu finden, so dass 1 <= x <= MAX_VAL und x (1) + ... + x (n) = Ziel “. Ich bin es von Grund auf neu zu entwickeln. Hier ist eine Version ohne Optimierung überhaupt, nur der Einfachheit halber:

def apcnx(n, max_val, target, xsofar=(), sumsofar=0):
  if n==0:
    if sumsofar==target:
      yield xsofar
    return

  if xsofar:
    minx = xsofar[-1] - 1
  else:
    minx = 0

  for x in xrange(minx, max_val):
    for xposs in apcnx(n-1, max_val, target, xsofar + (x+1,), sumsofar+x+1):
      yield xposs

for xs in apcnx(4, 6, 12):
  print xs

Der Basisfall n==0 (wo wir keine mehr Zahlen ergeben können) entweder das Tupel ergibt so weit, wenn er die Bedingung erfüllt, oder nichts, dann beendet (Rückkehr).

Wenn wir angeblich sind mehr Tupel erhalten, als wir bisher gebaut haben, die if/else stellt sicher, dass wir nur nicht abnehmende Tupeln ergeben, um Wiederholungen zu vermeiden (haben Sie „Kombination“ sagen statt „Permutation“).

Die for versuchen, alle Möglichkeiten für „diesen“ Artikel und Schleife über was auch immer die nächstniedrigeren Down-Ebene der Rekursion noch in der Lage ist, zu erhalten.

Der Ausgang ich sehe, ist:

(1, 1, 4, 6)
(1, 1, 5, 5)
(1, 2, 3, 6)
(1, 2, 4, 5)
(1, 3, 3, 5)
(1, 3, 4, 4)
(2, 2, 2, 6)
(2, 2, 3, 5)
(2, 2, 4, 4)
(2, 3, 3, 4)
(3, 3, 3, 3)

was richtig scheint.

Es gibt eine Unmenge von möglichen Optimierungen, aber denken Sie daran:

  

Zuerst es funktioniert, dann macht es schnell

ich mit Kent Beck entsprechen richtig „in aller Kürze Python“ in dieses Zitat zuzuschreiben, und er sagt mir, er habe es von seinem Vater, deren Aufgabe es war eigentlich in keinem Zusammenhang mit der Programmierung; -).

In diesem Fall scheint es mir, dass die entscheidende Frage ist Verständnis , was los ist, und jede Optimierung könnte stören, so dass ich alles für „einfach und verständlich“ going; bei Bedarf können wir, sein !, optimieren die Socken aus es, sobald der OP bestätigt sie können verstehen, was in diesem schiere vor sich geht, nicht optimierte Version!

Answer 4

Es tut uns Leid zu sagen, Ihr Code ist eine Art lange und nicht besonders lesbar. Wenn Sie versuchen, es irgendwie zusammenfassen, vielleicht kann jemand helfen, es zu schreiben deutlicher.

Was das Problem selbst, mein erster Gedanke wäre Rekursion zu verwenden. (Soviel ich weiß, Sie tun das bereits. Leider wieder für meine Unfähigkeit, den Code zu lesen.) Denken Sie an einen Weg, dass man das Problem auf eine kleinere einfachere Version des gleichen Problems zu reduzieren, wiederholt, bis Sie eine haben trivialer Fall mit einer sehr einfachen Antwort.

etwas konkreter sein, müssen Sie diese drei Parameter, MAX_VAL, target_sum und n_cells. Können Sie setzen eine dieser Nummern auf einen bestimmten Wert, um Ihnen ein äußerst einfaches Problem erfordert keinen Gedanken überhaupt zu geben? Sobald Sie, dass, können Sie die etwas härtere Version des Problems auf die bereits reduzieren ein gelöst?

EDIT: Hier ist mein Code. Ich mag es nicht, wie es funktioniert Deduplizierung. Ich bin sicher, es gibt einen weiteren Pythonic Weg. Auch ist es nicht zulässt, die gleiche Zahl zweimal in einer Kombination verwendet wird. Um dieses Verhalten rückgängig zu machen, nehmen Sie nur die Linie if n not in numlist: aus. Ich bin mir nicht sicher, ob dies völlig richtig ist, aber es scheint zu funktionieren und ist (IMHO) besser lesbar. Man könnte leicht hinzufügen memoization und das wäre es wahrscheinlich einiges beschleunigen.

def get_combos(max_val, target, n_cells):
    if target <= 0:
        return []
    if n_cells is 1:
        if target > max_val:
            return []
        else:
            return [[target]]
    else:
        combos = []
        for n in range(1, max_val+1, 1):
            for numlist in get_combos(max_val, target-n, n_cells-1):
                if n not in numlist:
                    combos.append(numlist + [n])
        return combos

def deduplicate(combos):
    for numlist in combos:
        numlist.sort()
    answer = [tuple(numlist) for numlist in combos]
    return set(answer)

def kenken(max_val, target, n_cells):
    return deduplicate(get_combos(max_val, target, n_cells))

Answer 5

Zunächst einmal ich Python lerne ich so diese Lösung nicht groß sein, aber das ist nur ein Versuch, diese zu lösen. Ich habe versucht, es rekursiv zu lösen und ich denke, eine rekursive Lösung für diese Art von Problem wäre ideal, obwohl die rekursive Lösung nicht diese könnte sein:

def GetFactors(maxVal, noOfCells, targetSum):
    l = []
    while(maxVal != 0):
        remCells = noOfCells - 1
        if(remCells > 2):
            retList = GetFactors(maxVal, remCells, targetSum - maxVal)
            #Append the returned List to the original List
            #But first, add the maxVal to the start of every elem of returned list.
            for i in retList:
                i.insert(0, maxVal)
            l.extend(retList)

        else:
            remTotal = targetSum - maxVal
            for i in range(1, remTotal/2 + 1):
                itemToInsert = remTotal - i;
                if (i > maxVal or itemToInsert > maxVal):
                    continue
                l.append([maxVal, i, remTotal - i])
        maxVal -= 1
    return l



if __name__ == "__main__":
    l = GetFactors(5, 5, 15)
    print l

Answer 6

Hier ist eine einfache Lösung in C / C ++:

const int max = 6;
int sol[N_CELLS];

void enum_solutions(int target, int n, int min) {
  if (target == 0 && n == 0)
    report_solution(); /* sol[0]..sol[N_CELLS-1] is a solution */
  if (target <= 0 || n == 0) return; /* nothing further to explore */
  sol[n - 1] = min; /* remember */
  for (int i = min; i <= max; i++)
    enum_solutions(target - i, n - 1, i);
}

enum_solutions(12, 4, 1);

Answer 7

Ein wenig offtopic, aber immer noch bei der Programmierung kenken helfen könnte.

Ich habe gute Ergebnisse mit DLX algorhitm zur Lösung Killer Sudoku (sehr simmilar als KenKen es Käfige, aber nur Summen). Es dauerte weniger als zweite für die meisten Probleme, und es wurde in MATLAB-Sprache implementiert.

Referenz dieses Forum http://www.setbb.com/phpbb/viewtopic. php? t = 1274 & highlight = & mforum = sudoku

Killer Sudoku "Blick auf wikipedia, kippt Beitrag Hyper-Link" damt Spammer

Answer 8

Hier ist eine naive, aber prägnant, Lösung mit Generatoren:

def descending(v):
  """Decide if a square contains values in descending order"""
  return list(reversed(v)) == sorted(v)

def latinSquares(max_val, target_sum, n_cells):
  """Return all descending n_cells-dimensional squares,
     no cell larger than max_val, sum equal to target_sum."""
  possibilities = itertools.product(range(1,max_val+1),repeat=n_cells)
  for square in possibilities:
    if descending(square) and sum(square) == target_sum:
      yield square

ich diesen Code könnte durch direkte Aufzählen der Liste der absteigenden Netze optimiert, aber ich finde itertools.product viel klarer für einen First-Pass-Lösung. Schließlich ruft die Funktion:

for m in latinSquares(6, 12, 4):
  print m

Answer 9

Und hier ist eine andere rekursive, Generator-basierte Lösung, aber diesmal einige einfache mathematische mit Bereiche bei jedem Schritt zu berechnen, zu vermeiden unnötige Rekursion:

def latinSquares(max_val, target_sum, n_cells):
  if n_cells == 1:
    assert(max_val >= target_sum >= 1)
    return ((target_sum,),)
  else:
    lower_bound = max(-(-target_sum / n_cells), 1)
    upper_bound = min(max_val, target_sum - n_cells + 1)
    assert(lower_bound <= upper_bound)
    return ((v,) + w for v in xrange(upper_bound, lower_bound - 1, -1)
                     for w in latinSquares(v, target_sum - v, n_cells - 1))

Dieser Code wird mit einem AssertionError fehlschlagen, wenn Sie die Parameter liefern, die unmöglich zu erfüllen; Dies ist ein Nebeneffekt meines „Korrektheit Kriteriums“, dass wir nie eine unnötige Rekursion tun. Wenn Sie nicht, dass die Nebenwirkung wollen, entfernen Sie die Behauptungen.

Beachten Sie die Verwendung von - (- x / y) nach der Teilung aufrunden. Es kann ein weiteren pythonic Weg sein, das zu schreiben. Beachten Sie auch, verwende ich Generator Ausdrücke statt Ausbeute.

for m in latinSquares(6,12,4):
  print m