Resolviendo rompecabezas en Python

permutation combinations

Question

Tengo un rompecabezas y quiero resolverlo usando Python.

Rompecabezas:

Un comerciante tiene un peso de 40 kg que utilizó en su tienda. Una vez, cayó de sus manos y se rompió en 4 pedazos. Pero sorprendentemente, ahora puede pesar cualquier peso entre 1 kg y 40 kg con la combinación de estas 4 piezas.

Entonces la pregunta es, ¿cuáles son los pesos de esas 4 piezas?

Ahora quería resolver esto en Python.

La única restricción que obtuve del rompecabezas es que la suma de 4 piezas es 40. Con eso podría filtrar todo el conjunto de 4 valores cuya suma es 40.

import itertools as it

weight = 40
full = range(1,41)
comb = [x for x in it.combinations(full,4) if sum(x)==40]

length of comb = 297

Ahora necesito verificar cada conjunto de valores en comb y probar todas las combinaciones de operaciones.

Por ejemplo, si (a,b,c,d) es el primer conjunto de valores en el comb , debo verificar a,b,c,d,a+b,ab, .................a+b+cd,a-b+c+d........ y así sucesivamente.

Intenté mucho, pero estoy atascado en esta etapa, es decir, cómo comprobar todas estas combinaciones de cálculos para cada conjunto de 4 valores.

Pregunta:

1) Creo que necesito obtener una lista de todas las combinaciones posibles de [a,b,c,d] and [+,-] .

2) ¿Alguien tiene una mejor idea y me dice cómo avanzar desde aquí?

Además, quiero hacerlo completamente sin la ayuda de ninguna biblioteca externa, necesito usar solo las bibliotecas estándar de python.

EDITAR : Lo siento por la información tardía. Su respuesta es (1,3,9,27), que encontré hace unos años. He comprobado y verificado la respuesta.

EDITAR: En la actualidad, la respuesta de fraxel funciona perfectamente con un time = 0.16 ms . Un enfoque mejor y más rápido siempre es bienvenido.

Saludos

ARCA

Answer 1

Aquí hay una solución de itertoles de fuerza bruta:

import itertools as it

def merchant_puzzle(weight, pieces):
    full = range(1, weight+1)
    all_nums = set(full)
    comb = [x for x in it.combinations(full, pieces) if sum(x)==weight]
    funcs = (lambda x: 0, lambda x: x, lambda x: -x)
    for c in comb:
        sums = set()
        for fmap in it.product(funcs, repeat=pieces):
            s = sum(f(x) for x, f in zip(c, fmap))
            if s > 0:
                sums.add(s)
                if sums == all_nums:
                    return c

>>> merchant_puzzle(40, 4)
(1, 3, 9, 27)

Para obtener una explicación de cómo funciona, consulte la respuesta que dio Avaris , esta es una implementación del mismo algoritmo.

Answer 2

Bruto me obligó a salir de la segunda parte.

No hagas clic en esto si no quieres ver la respuesta. Obviamente, si hubiera sido mejor en permutaciones, esto habría requerido mucho menos cortar / pegar buscar / reemplazar:

http://pastebin.com/4y2bHCVr

Answer 3

Con pesos [2, 5, 15, 18] también puede medir todos los objetos entre 1 y 40 kg, aunque algunos de ellos deberán medirse indirectamente. Por ejemplo, para medir un objeto con un peso de 39 kg, primero lo compararía con 40 kg y la balanza se colgaría del lado de 40 kg (porque 39 <40), pero luego, si retira el peso de 2 kg, se colgará del otro lado (porque 39> 38) y así puede concluir el peso de los objetos 39kg.

Más interesante, con pesos [2, 5, 15, 45] puede medir todos los objetos hasta 67 kg.

Answer 4

Estás cerca, muy cerca :).

Ya que este es un rompecabezas que quieres resolver, solo daré punteros. Para esta parte:

Por ejemplo, si (a, b, c, d) es el primer conjunto de valores en peine, necesito verificar a, b, c, d, a + b, ab, ............ ..... a + b + cd, a-b + c + d ........ y así sucesivamente.

Considere esto: cada peso puede ser puesto en una escala, la otra o ninguna. Entonces, para el caso de a , esto se puede representar como [a, -a, 0] . Lo mismo con los otros tres. Ahora necesita todas las combinaciones posibles con estas 3 posibilidades para cada peso (sugerencia: itertools.product ). Entonces, una posible medición de un emparejamiento (digamos: (a, -b, c, 0) ) es simplemente la suma de estos ( a-b+c+0 ).

Todo lo que queda es solo comprobar si podría "medir" todos los pesos requeridos. set podría ser útil aquí.

PD: Como se indicó en los comentarios, para el caso general, puede que no sea necesario que estas ponderaciones divididas sean distintas (para este problema es). Usted podría reconsiderar itertools.combinations .

Answer 5

No conozco la sintaxis de Python, pero quizás puedas decodificar este código de Scala; comenzar con el segundo for-loop:

def setTo40 (a: Int, b: Int, c: Int, d: Int) = {

val vec = for (
  fa <- List (0, 1, -1);
  fb <- List (0, 1, -1);
  fc <- List (0, 1, -1);
  fd <- List (0, 1, -1);
  prod = fa * a + fb * b + fc * c + fd * d;
  if (prod > 0)
  ) yield (prod)

  vec.toSet
}

for (a <- (1 to 9);
  b <- (a to 14);
  c <- (b to 20);
  d = 40-(a+b+c)
  if (d > 0)) { 
    if (setTo40 (a, b, c, d).size > 39)
      println (a + " " + b + " " + c + " " + d)
  }

Answer 6

Si alguien no quiere importar una biblioteca para importar combos / perms, esto generará todas las estrategias posibles de 4 movimientos ...

# generates permutations of repeated values
def permutationsWithRepeats(n, v):
    perms = []
    value = [0] * n
    N = n - 1
    i = n - 1

    while i > -1:
        perms.append(list(value))

        if value[N] < v:
            value[N] += 1
        else:
            while (i > -1) and (value[i] == v):
                value[i] = 0
                i -= 1

            if i > -1:
                value[i] += 1
                i = N

    return perms

# generates the all possible permutations of 4 ternary moves
def strategy():
    move = [''-'', ''0'', ''+'']
    perms = permutationsWithRepeats(4, 2)

    for i in range(len(perms)):
        s = ''''

        for j in range(4):
            s += move[perms[i][j]]

        print s

# execute
strategy()

Answer 7

Respuesta anterior:

Sabemos que a*A + b*B + c*C + d*D = x para todas las x entre 0 y 40, y a, b, c, d se limitan a -1, 0, 1 . Claramente A + B + C + D = 40 . El siguiente caso es x = 39 , por lo que claramente el movimiento más pequeño es eliminar un elemento (es el único movimiento posible que podría resultar en un balance exitoso contra 39):

A + B + C = 39 , entonces D = 1 , por necesidad.

siguiente:

A + B + C - D = 38

siguiente:

A + B + D = 37 , entonces C = 3

entonces:

A + B = 36

entonces:

A + B - D = 35

A + B - C + D = 34

A + B - C = 33

A + B - C - D = 32

A + C + D = 31 , entonces A = 9

Por lo tanto B = 27

Así que los pesos son 1, 3, 9, 27

Realmente esto puede deducirse inmediatamente del hecho de que todos deben ser múltiplos de 3.

Actualización interesante:

Así que aquí hay un código de Python para encontrar un conjunto mínimo de pesos para cualquier peso caído que abarque el espacio:

def find_weights(W):
    weights = []
    i = 0
    while sum(weights) < W:
        weights.append(3 ** i)
        i += 1
    weights.pop()
    weights.append(W - sum(weights))
    return weights

print find_weights(40)
#output:
[1, 3, 9, 27]

Para ilustrar mejor esta explicación, uno puede considerar el problema como el número mínimo de ponderaciones para abarcar el espacio numérico [0, 40] . Es evidente que el número de cosas que puede hacer con cada peso es trinario / ternario (agregar peso, eliminar peso, poner peso en el otro lado). Entonces, si escribimos nuestros pesos (desconocidos) (A, B, C, D) en orden descendente, nuestros movimientos se pueden resumir como:

    ABCD:   Ternary:
40: ++++     0000
39: +++0     0001
38: +++-     0002
37: ++0+     0010
36: ++00     0011
35: ++0-     0012
34: ++-+     0020
33: ++-0     0021
32: ++--     0022
31: +0++     0100
etc.

He puesto el conteo ternario del 0 al 9 al lado, para ilustrar que estamos efectivamente en un sistema de números trinarios (base 3). Nuestra solución siempre puede ser escrita como:

3**0 + 3**1 +3**2 +...+ 3**N >= Weight

Para el mínimo N que esto es verdad. La solución mínima SIEMPRE será de esta forma.

Además, podemos resolver fácilmente el problema para grandes pesos y encontrar el número mínimo de piezas para abarcar el espacio:

Un hombre deja caer un peso conocido W, se rompe en pedazos. Sus nuevos pesos le permiten pesar cualquier peso hasta W. ¿Cuántos pesos hay y cuáles son?

#what if the dropped weight was a million Kg:
print find_weights(1000000)
#output:
[1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 202839]

Trate de usar permutaciones para un gran peso y un número desconocido de piezas!