El rompecabezas KenKen agrega:REDUX A (corregido) algoritmo no recursivo

Question

Esta pregunta se relaciona con aquellas partes de los rompecabezas KenKen Latin Square que le piden que encuentre todas las combinaciones posibles de números ncells con valores x tales que 1 <= x <= maxval y x(1) +...+ x(ncells) = suma objetivo.Habiendo probado varias de las respuestas más prometedoras, le otorgaré el premio a Lennart Regebro porque:

1. su rutina es tan rápida como la mía (+-5%), y

2. Señaló que mi rutina original tenía un error en alguna parte, lo que me llevó a ver qué intentaba hacer realmente.Gracias, Lennart.

Chrispy contribuyó con un algoritmo que parece equivalente al de Lennart, pero 5 horas después, el primero en llegar al cable lo recibe.

Un comentario:El algoritmo recursivo básico de Alex Martelli es un ejemplo de cómo hacer todas las combinaciones posibles y tirarlas todas a un colador y ver cuáles pasan por los agujeros.Este enfoque lleva más de 20 veces más que el de Lennart o el mío.(Suba la entrada a max_val = 100, n_cells = 5, target_sum = 250 y en mi caja son 18 segundos vs.8+ minutos.) Moraleja:No generar todas las combinaciones posibles es bueno.

Otro comentario:Las rutinas de Lennart y las mías generan las mismas respuestas en el mismo orden.¿Son realmente el mismo algoritmo visto desde diferentes ángulos?No sé.

Se me ocurre algo.Si ordenas las respuestas, comenzando, digamos, con (8,8,2,1,1) y terminando con (4,4,4,4,4) (lo que obtienes con max_val=8, n_cells=5, target_sum =20), la serie forma una especie de "descenso más lento", siendo las primeras "calientes" y las últimas "frías" y el mayor número posible de etapas intermedias.¿Está esto relacionado con la "entropía informativa"?¿Cuál es la métrica adecuada para verlo?¿Existe un algoritmo que produzca combinaciones en orden descendente (o ascendente) de calor?(Este no lo hace, por lo que puedo ver, aunque está cerca en tramos cortos, mirando la norma normalizada.desarrollador)

Aquí está la rutina de 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)

Answer 1

En primer lugar, me gustaría utilizar nombres de variables que significan algo, por lo que el código obtiene comprensible. Entonces, después de que yo entendía el problema, está claro que es un problema recurrente, ya que una vez que haya elegido un número, la cuestión de la búsqueda de los posibles valores para el resto de las plazas son exactamente el mismo problema, pero con diferentes valores de.

Así que lo haría así:

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))

También noto que su solución aún parece buggy. Para los valores max_val=8, target_sum=20 and n_cells=5 su código no encuentra la solución (8,6,4,1,1,), como un ejemplo. No estoy seguro de si eso significa que he perdido una regla en esto o no, pero como entiendo las reglas que debería ser una opción válida.

Aquí hay una versión utilizando generadores, se ahorra un par de líneas, y la memoria si los valores son muy grandes, pero a medida que la recursividad, generadores puede ser difícil de "obtener".

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

Su algoritmo parece bastante bueno a primera vista, y no creo que OO u otro lenguaje mejoren el código.No puedo decir si la recursividad hubiera ayudado, pero admiro el enfoque no recursivo.Apuesto a que fue más difícil ponerse a trabajar y es más difícil de leer, pero probablemente sea más eficiente y definitivamente bastante inteligente.Para ser honesto, no analicé el algoritmo en detalle, pero ciertamente parece algo que tardó mucho en funcionar correctamente.Apuesto a que hubo muchos errores de uno por uno y casos extremos extraños en los que tuviste que pensar, ¿eh?

Teniendo en cuenta todo eso, básicamente todo lo que intenté hacer fue embellecer su código lo mejor que pude reemplazando los numerosos C-ismos con Python-ismos más idiomáticos.Muchas veces lo que requiere un bucle en C se puede hacer en una línea en Python.También intenté cambiar el nombre de las cosas para seguir mejor las convenciones de nomenclatura de Python y limpié un poco los comentarios.Espero no ofenderte con ninguno de mis cambios.Puedes coger lo que quieras y dejar el resto.:-)

Aquí están las notas que tomé mientras trabajaba:

• Cambió el código que inicializa. tmp a un montón de 1 a los más idiomáticos tmp = [1] * n_cells.
• Cambió for bucle que resume tmp_sum a idiomático sum(tmp).
• Luego reemplazó todos los bucles con un tmp = <list> + <list> un trazador de líneas.
• Movido raise doneException a init_tmp_new_ceiling y se deshizo del succeeded bandera.
• el check-in init_tmp_new_ceiling En realidad parece innecesario.Quitándolo, lo único raiseLos que quedaban estaban en make_combos_n_cells, así que simplemente los cambié a devoluciones regulares y los eliminé. doneException enteramente.
• Mezcla normalizada de 4 espacios y 8 espacios para sangría.
• Se eliminaron paréntesis innecesarios alrededor de su if condiciones.
• tmp[p2] - tmp[p1] == 0 es lo mismo que tmp[p2] == tmp[p1].
• Cambió while True: if new_ceiling_flag: break a while not new_ceiling_flag.
• No necesita inicializar las variables a 0 en la parte superior de sus funciones.
• Remoto combos lista y función cambiada a yield sus tuplas a medida que se generan.
• Renombrado tmp a combo.
• Renombrado new_ceiling_flag a ceiling_changed.

Y aquí está el código para su lectura:

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

Aquí está la solución recursiva más simple que puedo pensar para "encontrar todas las combinaciones posibles de n números con valores de x tal que 1 <= x <= MAX_VAL y X (1) + ... + x (n) = objetivo ". Estoy desarrollando desde cero. Aquí hay una versión sin ninguna optimización en absoluto, sólo por simplicidad:

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

El caso base n==0 (donde no podemos dió ningún más números) o bien dar la tupla hasta ahora si satisface la condición, o nada, entonces termina (devuelve).

Si se supone que debemos producir más que las tuplas que hemos construido hasta ahora, el if/else se asegura de que sólo rendimos tuplas no decreciente, para evitar la repetición (que hizo decir "combinación" en lugar de "permutación") .

El for intenta todas las posibilidades de "este" elemento y bucles sobre cualquiera que sea el siguiente nivel inferior hacia abajo de la recursividad es todavía capaz de producir.

La salida que veo es:

(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)

que parece correcta.

Hay bazillion posibles optimizaciones, pero, recuerde:

  

En primer lugar hacer que funcione, a continuación, que sea rápido

Me correspondió con Kent Beck atribuir correctamente esta cita en "Python en una cáscara de nuez", y él me dice que lo recibió de su padre, cuyo trabajo era en realidad no relacionado con la programación; -).

En este caso, me parece que la cuestión clave es comprensión lo que está pasando, y cualquier optimización podría interferir, así que estoy saliendo todos por "simple y comprensible"; podemos, si es necesario !, optimizar los calcetines de que una vez que el OP confirma que puede entender lo que está pasando en este pura, la versión sin optimizar!

Answer 4

Lo sentimos decir, su código es una especie de larga y no muy legible. Si se puede tratar de resumir de alguna manera, tal vez alguien puede ayudar a escribir con más claridad.

En cuanto al propio problema, lo primero que pensé sería el uso de la recursividad. (Por lo que sé, que ya está haciendo eso. Lo siento de nuevo por mi incapacidad para leer el código.) Piense en una forma que puede reducir el problema a una versión más pequeña más fácil del mismo problema, en varias ocasiones, hasta que haya una caso trivial con una respuesta muy simple.

Para ser un poco más concreto, tiene estos tres parámetros, MAX_VAL, target_sum y n_cells. Se puede configurar uno de esos números a algún valor en particular, con el fin de darle un problema extremadamente simple que requiere ningún pensamiento en absoluto? Una vez conseguido eso, se puede reducir la versión ligeramente más duro del problema a la ya resuelto uno?

EDIT: Aquí está mi código. No me gusta la forma en que lo hace de de-duplicación. Estoy seguro de que hay una manera más Pythonic. Además, no permite utilizando el mismo número dos veces en una combinación. Para deshacer este comportamiento, puedes sacar la línea if n not in numlist:. No estoy seguro si esto es completamente correcto, pero parece que funciona y es (en mi humilde opinión) más legible. Desde aquí se puede añadir memoization y que probablemente acelerarlo un poco.

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

En primer lugar, estoy aprendiendo Python a mí mismo lo que esta solución no va a ser grande, pero esto es sólo un intento de solucionar esto. He tratado de resolver de forma recursiva y creo que una solución recursiva sería ideal para este tipo de problema a pesar de que la solución recursiva podría no ser ésta:

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

Aquí una solución simple en 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

Un poco offtopic, pero aún podría ayudar a kenken programación.

Me dieron buenos resultados usando DLX algorhitm para resolver Killer Sudoku (muy de parecida como KenKen tiene jaulas, pero sólo sumas). En menos de segundos para la mayoría de los problemas y se implementa en lenguaje MATLAB.

Referencia de este foro http://www.setbb.com/phpbb/viewtopic. php? t = 1274 y destacar = & mforum = sudoku

sudoku killer "Mirar en Wikipedia, no puede enlace posterior hiper" spammers DAMT

Answer 8

Este es un ingenuo, pero sucinta, solución utilizando generadores:

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

Podría haber optimizado el código directamente enumerando la lista de redes descendente, pero me parece mucho más claro itertools.product de una solución de primer paso. Por último, llamar a la función:

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

Answer 9

Y aquí es otra solución recursiva, basado en el generador, pero esta vez usando un poco de matemática simple calcular rangos en cada paso, evitar la repetición innecesaria:

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))

Este código fallará con un AssertionError si proporciona parámetros que son imposibles de satisfacer; este es un efecto secundario de mi "criterio de corrección" que no hacemos una recursividad innecesaria. Si no desea que los efectos secundarios, eliminar las afirmaciones.

Observe el uso de - (- x / y) para redondear después de la división. Puede haber una manera más Pythonic escribir eso. Tenga en cuenta también estoy usando expresiones generadoras vez de rendimiento.

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