¿Cómo puedo reducir un número?

Question

Estoy tratando de trabajar en un programa y creo que me ha golpeado un problema de matemáticas (si es no, por favor hágamelo saber, lo siento). Básicamente lo que estoy haciendo es tomar un número y el uso de un universo de números y estoy tratando de averiguar cómo los combos de trabajo (creo que esta es una forma de la teoría de los números).

Por ejemplo, para una suma de 10 y el uso de un universo de [4, 2, 1], tengo (estoy mostrando cómo percibo el desglose):

2 * 4 +  1 * 2 +  0 * 1 = 4 + 4 + 2
2 * 4 +  0 * 2 +  2 * 1 = 4 + 4 + 1 + 1
1 * 4 +  3 * 2 +  0 * 1 = 4 + 2 + 2 + 2
1 * 4 +  2 * 2 +  2 * 1 = 4 + 2 + 2 + 1 + 1
1 * 4 +  1 * 2 +  4 * 1 = 4 + 2 + 1 + 1 + 1 + 1
1 * 4 +  0 * 2 +  6 * 1 = 4 + 1 + 1 + 1 + 1 + 1 + 1
0 * 4 +  5 * 2 +  0 * 1 = 2 + 2 + 2 + 2 + 2
0 * 4 +  4 * 2 +  2 * 1 = 2 + 2 + 2 + 2 + 1 + 1
0 * 4 +  3 * 2 +  4 * 1 = 2 + 2 + 2 + 1 + 1 + 1 + 1
0 * 4 +  2 * 2 +  6 * 1 = 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1
0 * 4 +  1 * 2 +  8 * 1 = 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
0 * 4 +  0 * 2 + 10 * 1 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

Así como los números se hacen más grandes, estoy teniendo problemas de escala (si tengo una suma de 1000 con 30 variables, tarda una eternidad). Por lo que mirar el problema como tengo encima, pensé que podría romper el basado en los resultados. Así que lo que hago es tomar el universo de la lista [4,2,1] y vaya a la lista y ver cómo muchos de los números anteriores necesario para hacer de ese número. He aquí un ejemplo:

2 [[1, 1]]
4 [[2, 2]]
4 [[2, 2]]

Lo que significa es 1+1=2, 2+2=4, así que puedo usar esa tabla para romper el primer resultado más alto (4+4+2... miro la tabla y ver que 2 = 1+1 con el fin de reemplazar el que, a continuación, volver a la primera mejor resultado y, a continuación, la búsqueda de la ruptura de la segunda serie, etc.). No estoy seguro, pero creo que esto puede escalar porque puedo dividir el cálculo de búsquedas y separados de CPU/sistemas/clusters/etc..

Probablemente hay muchos defectos lógicos, pero el que me di cuenta de que ahora es ¿qué pasa si el número es un número primo o no se puede descomponer en el último número más alto? Decir que mi universo cambia de [4,2,1] a [4,3,2,1]... porque el mayor partido aún 4+4+2 3 recibirá perdido totalmente como una solución.

Entonces, me pregunto cómo puedo matemáticamente de acuerdo con los números primos (tengo una función de la identificación de ellos)? También lo es la lógica correcta si tengo los números que no se dividen limpiamente en cada uno de los otros? (universo de [6,4,2,1] rompe también). En el pasado yo bruta obligado a este (intente de todo hasta que lo consigue) el problema es, si no puedo descomponer el problema en pequeños problemas de matemáticas que me pueden escala. Creo que esto se puede hacer porque puedo escala (en una escala pequeña :-), pero tratar con números específicos son el problema (primer y supongo que los números que son el opuesto de la suma o impar).

Lo siento por la pregunta larga y otra vez, lo siento si este no es el apropiado para esta P/A, pero cualquier sugerencia o consejo útil.

Answer 1

Voy a utilizar la declaración del problema como user3296 dio: "Escribir un programa de ordenador que, dado un entero positivo $n$ y una lista de enteros positivos $S = \{m_1, m_2, \ldots, m_k\}$ como entrada, produce una lista de todas las forma de escribir el número de $n$ como una suma de elementos de $S$."

El truco para resolver muchos de los problemas de este tipo es para romper cada caso hacia abajo exactamente en los casos más pequeños. Para este problema en particular, podemos dividir cada problema que implica un universo en varios problemas que involucran el siguiente más pequeño universo, y que en varios problemas que involucran el siguiente más pequeño universo, y así sucesivamente, hasta que el universo está vacío. Con un vacío del universo, sólo hay un número que podemos hacer: 0.

Más formalmente, para resolver este problema, se utiliza la recursividad en $S$. Consideran que el primer elemento de $S$, $m_1$, y asumir que el problema ya ha sido resuelto por $\{m_2, m_3, \ldots, m_k\}$. Si $n \ge m_1$, entonces se puede utilizar una vez. Si o no $n \ge m_1$, podemos ignorar $m_1$ y pasar al siguiente elemento del universo.

En pseudocódigo, nuestra función recursiva se parece a esto:

findSums(n, S) (if S is not empty):
    Start with an empty list, L, of sums.
    Is n greater than or equal to m1?
        If so, add all elements of findSums(n - m1, S) to L,
        and then put "m1 +" in front of each element of L.
    Add all elements of findSums(n, S \ m1) to L.
    We are done.  Return L.

findSums(n, emptyset) (if n is not 0):
    Return the empty list.
    (There is no way to add elements of the empty set
    to get something positive.)

findSums(0, emptyset):
    Return the list containing only the empty sum.

En Haskell:

findSums n (s:ss) =
    (if n >= s then map (s:) (findSums (n-s) (s:ss)) else [])
    ++ sums n ss

findSums 0 [] = [[]]

findSums _ [] = []

Answer 2

Ah, aquí vamos: este es el problema de enumerar el número de maneras de hacer el cambio. Este problema ha sido discutido antes en este sitio y en un buen libro de texto, pero vamos a especializarse para su problema.

Considere la posibilidad de un país, Perdido-soulia, donde la unidad de moneda es el Lostie. El existente monedas del reino disponer de los valores de 1 Lostie, 2 Losties, y 4 Losties. Usted está preguntando ¿de cuántas maneras distintas puede tener 10 Losties en las monedas del reino.

Una manera de resolver esto hace que el uso del concepto de funciones de generación; específicamente, considere la posibilidad de la generación de la función

$$\frac1{(1-a x)(1-b x^2)(1-c x^4)}$$

where $a,b,c$ each correspond to the number of each denomination. To solve your problem of representing 10 Losties in coins, we expand the generating function as a Maclaurin series, and take the coefficient of $x^{10}$. For this case, the required coefficient is

$$a^{10}+a^8 b+a^6 b^2+a^6 c+a^4 b^3+a^4 b c+a^2 b^4+a^2 b^2 c+a^2 c^2+b^5+b^3 c+b c^2$$

We count twelve terms in this result, corresponding to your twelve ways of representing 10 Losties in terms of Lostie coins. Each term can be interpreted as a particular partition of 10; for instance, the term $a^4 bc$ corresponds to having 4 1-Lostie coins, 1 2-Lostie coin, and 1 4-Lostie coin, which totals to 10 Losties. (The exponents of the $a,b,c$ correspond to the counts of each coin.)

We can generalize. If for instance Lost-soulia decides to release a brand spanking new 3 Lostie coin, you just need to change your generating function to

$$\frac1{(1-a x)(1-b x^2)(1-c x^4)(1-d x^3)}$$

where $d$ corresponds to the count of 3-Lostie coins.The coefficient of $x^{10}$ in the series expansion is

$$\begin{split}a^{10}+a^8 b+a^7 d+a^6 b^2+a^6 c+a^5 b d+a^4 b^3+a^4 b c+a^4 d^2+a^3 b^2 d+a^3 c d+a^2 b^4+\\ a^2 b^2 c+a^2 b d^2+a^2 c^2+a b^3 d+a b c d+a d^3+b^5+b^3 c+b^2 d^2+b c^2+c d^2\end{split}$$

which has 23 terms, so you have 23 ways of having 10 Losties in coins. The $abcd$ term for instance corresponds to partitioning 10 as $1+2+4+3$, and $ab^3 d$ corresponds to partitioning 10 as $1+2+2+2+3$.

---

Me dio un corto Mathematica de rutina para el cambio-problema de hacer en los comentarios, pero esa versión tiene un bug (intente MakeChange[8, {2, 7}]). Aquí es una versión más robusta de que la rutina:

MakeChange[n_Integer?Positive, v_?VectorQ] := Module[{l = Length[v], x}, 
   Exponent[#, Array[C, l]] & /@ 
    Flatten[{Expand[
        SeriesCoefficient[1/Apply[Times, 1 - Array[C, l] x^v], 
          {x, 0, n}]] /. Plus -> List}]] /;
VectorQ[v, (IntegerQ[#] && Positive[#]) &]

---

Mucho más tarde: resulta que la funcionalidad de MakeChange[] ya está hecho por las funciones intrínsecas IntegerPartitions[] y FrobeniusSolve[]. Aún así, creo que la rutina es una buena ilustración de la generación de funciones...

Hay métodos más eficientes para resolver el problema de Frobenius, usando los métodos de la teoría de grafos y programación entera, usted puede buscar en la web para documentos de debate sobre estos métodos para generar y contar entero particiones.