Algoritmo para dividir la suma entre cubos en todas las formas exclusivas

Question

El Problema

Necesito un algoritmo que hace esto:

Encontrar todas las maneras únicas de partición de una determinada suma de los cubos de los' sin importarle el fin de

Espero haber sido claro razonablemente coherente en la expresión de mí mismo. Yo no he puesto en el código, ya que el algoritmo no está desarrollado aún por Hacer.

Ejemplo

Por la suma de 5 y 3 cubos, lo que el algoritmo debe de retorno es:

[5, 0, 0]
[4, 1, 0]
[3, 2, 0]
[3, 1, 1] [2, 2, 1]

Descargo de responsabilidad

Lo siento si esta pregunta podría ser una víctima, pero no sé exactamente lo que este tipo de problemas son llamados. Aún así, he buscado en Google y Matemáticas.SE usar todas las palabras que yo podía pensar, pero solo encontraron resultados para la distribución en la mayoría incluso forma, no todas las formas únicas.

Solución

OK, así que he jugado un poco y se le ocurrió una solución. Ya no me quieren robar el impresionante chicos de aquí que eran más rápidos que yo, de su representante, no estoy aceptando mi propia respuesta, pero ponerlo aquí. Es en Python, que es prácticamente como en pseudocódigo con un compilador.

Mi primer intento funcionado, pero estaba terriblemente ineficiente:

def intPart(buckets, balls):
    return uniqify(_intPart(buckets, balls))

def _intPart(buckets, balls):
    solutions = []

    # base case
    if buckets == 1:
        return [[balls]]

    # recursive strategy
    for i in range(balls + 1):
        for sol in _intPart(buckets - 1, balls - i):
            cur = [i]
            cur.extend(sol)
            solutions.append(cur)

    return solutions

def uniqify(seq):
    seen = set()
    sort = [list(reversed(sorted(elem))) for elem in seq]
    return [elem for elem in sort if str(elem) not in seen and not seen.add(str(elem))]

Aquí está mi reelaborado solución. Se evita completamente la necesidad de "uniquify' por el seguimiento de las bolas en el anterior el cubo utilizando la max_ variable. Este tipo de listas y se impide que los incautos.

def intPart(buckets, balls, max_ = None):
    # init vars
    sols = []
    if max_ is None:
        max_ = balls
    min_ = max(0, balls - max_)

    # assert stuff
    assert buckets >= 1
    assert balls >= 0

    # base cases
    if (buckets == 1):
        if balls <= max_:
            sols.append([balls])
    elif balls == 0:
        sol = [0] * buckets
        sols.append(sol)

    # recursive strategy
    else:
        for there in range(min_, balls + 1):
            here = balls - there
            ways = intPart(buckets - 1, there, here)
            for way in ways:
                sol = [here]
                sol.extend(way)
                sols.append(sol)

    return sols

Answer 1

Este es Perl, pero el algoritmo es sencillo y debe ser fácil de implementar en cualquier idioma:

#!/usr/bin/perl

 sub parte {
 mi ($n, $b, $min) = @_;
$min = 0 unless defined $min;

 # caso base
 si ($b == 0) {
 if ($n == 0) { return ( [] ) }
 else { return () }
}

 mi @particiones;
 para mi $first ($min .. $n) {
 mi @sub_partitions = parte ($n - $, $b-1, $);
 para mi $sp (@sub_partitions) {
 push @particiones, [$first, @$sp];
}
}
 return @particiones;
}

La función part recibe dos argumentos: $n$ es el número total de granos que desee (5 en el ejemplo) y $b$ es el número de cubos (3 en el ejemplo). También se obtiene un auxiliar argumento, $min$, que es el más pequeño permitido cubo de valor. Este defecto es 0 si no se suministra.

La función es recursiva, como usted sugiere. En el caso base no cubos, $b=0$. Si no hay frijoles para poner en los depósitos ($n=0$ también), entonces esto puede ser satisfecho en exactamente un camino, por una matriz vacía de cubos []. De lo contrario, no hay solución porque no son los frijoles a la izquierda, pero no los cubos para ponerlos en.

Si $b>0$, entonces la función de acumular una lista de las posibles particiones de $n$ frijoles en $b$ de los cubos en la matriz @partitions. Esto se hará mediante la selección de la cantidad de granos de ir en el primer segmento ($first$), de forma recursiva a asignar el resto de los frijoles en $b-1$ cubos, y el montaje de los dos en una solución completa, que se añadirá a @partitions. Esto es sólo lo que se sugiere en la pregunta.

El número de los granos en el primer cubo debe tener al menos $min$, y en la mayoría de las $n$, el número total de granos.

A continuación, la función se llama a sí mismo de forma recursiva: hay $n-first$ frijoles para asignar a $b-1$ baldes, pero ningún cubo puede tener menos de $first$ frijoles. Esta última parte es la única parte complicada: se asegura que el número de granos nunca disminuye de cada uno de ellos a la siguiente, y así que cada uno generado partición es único. (Sin esta restricción, [1,2,2], [2,1,2]y [2,2,1] serían diferentes soluciones. Con esta restricción, sólo [1,2,2] es generado.)

La llamada recursiva devuelve un número de particiones de $n-first$ frijoles en $b-1$ cubos. $first$ se anexa a cada uno de estos (que [$first, @$sp], lo que hace que una sola matriz de $first y el contenido de $sp) y la resultante de las particiones de $n$ frijoles en $b$ cubos se insertan en @partitions. Cuando esto se ha hecho para cada uno de los valores admisibles de $first$, el @partitions lista es devuelto.

Para probar el ejemplo, yo hice:

 para mi $p ( parte(5, 3) ) {
 print "@$p\n";
}

Que imprimió:

0 0 5
0 1 4
0 2 3
1 1 3
1 2 2

Para obtener las particiones con el elemento más grande primero, cambie [$first, @$sp] a [@$sp, $first].

Algunos menores de optimización son posibles. Por ejemplo, si $n < b\cdot min$, entonces uno puede detener la recursividad de inmediato, de regreso no soluciones.

Answer 2

La manera más fácil para el programa de este manual es probablemente un enfoque recursivo. Definir una función

Part(n, m, max)

que distribuirá n elementos entre m cajas, poniendo en la mayoría de los max en cada cuadro. El código para Part se divide en dos casos. Si m = 1 , a continuación, devuelva una lista vacía si n > max y regresar [[n]] lo contrario. Si m > 1 , a continuación, para cada una de las $0 \leq i \leq n$ anteponer i sobre el principio de los resultados de Part(n - i, m - 1, i) y devolver toda la colección.

La respuesta que queremos es dado por Part(n, m, n).

Answer 3

Quiero comentar sobre la respuesta de Perl, pero no tengo suficientes puntos. Aquí está la misma respuesta en Python:

 def partition(n, b, minimum=0):
    if b == 1:
        if n == 0:
            return [[]]
        else:
            return [[n]]

    partitions = []
    for i in range(minimum, n):
        sub_partitions = partition(n - i, b - 1, i)
        for sub_partition in sub_partitions:
            partitions.append([i] + sub_partition)
    return partitions
 

Answer 4

En Mathematica:

 IntegerPartitions[5, 3]