Resolviendo rompecabezas en Python
permutation combinations (7)
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
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.
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:
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.
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 .
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)
}
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()
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!