Algoritmo para generar todas las permutaciones únicas de particiones enteras de longitud fija?

Question

Estoy buscando un algoritmo que genere todas las permutaciones de particiones de longitud fija de un entero. El orden no importa.

Por ejemplo, para n = 4 y la longitud L = 3:

[(0, 2, 2), (2, 0, 2), (2, 2, 0), 
(2, 1, 1), (1, 2, 1), (1, 1, 2), 
(0, 1, 3), (0, 3, 1), (3, 0, 1), (3, 1, 0), (1, 3, 0), (1, 0, 3), 
(0, 0, 4), (4, 0, 0), (0, 4, 0)] 

I bumbled sobre con particiones enteros + permutaciones para particiones cuya longitud es menor que L; pero que era demasiado lento porque tengo la misma partición varias veces (porque [0, 0, 1] puede ser una permutación de [0, 0, 1] ;-)

Cualquier ayuda apreciada, y no, esto no es tarea - interés personal :-)

Answer 1

Bien. Primero, olvídese de las permutaciones y solo genere las particiones de longitud L (como lo sugiere @Svein Bringsli). Tenga en cuenta que para cada partición, puede imponer un orden en los elementos, como>. Ahora solo "cuente", manteniendo su orden. Para n = 4, k = 3:

(4, 0, 0) 
(3, 1, 0) 
(2, 2, 0) 
(2, 1, 1) 

Entonces, ¿cómo implementar esto? Parece que: al restar 1 de la posición i y agregarlo a la siguiente posición mantiene nuestro orden, resta 1 de la posición i, agrega 1 a la posición i + 1, y avanza a la siguiente posición. Si estamos en la última posición, retrocede.

He aquí una pequeña serpiente pitón, que hace precisamente eso:

def partition_helper(l, i, result): 
    if i == len(l) - 1: 
     return 
    while l[i] - 1 >= l[i + 1] + 1: 
     l[i]  -= 1 
     l[i + 1] += 1 
     result.append(list(l)) 
     partition_helper(l, i + 1, result) 

def partition(n, k): 
    l = [n] + [0] * (k - 1) 
    result = [list(l)] 
    partition_helper(l, 0, result) 
    return result 

Ahora usted tiene una lista de listas (en realidad una lista de conjuntos múltiples), y la generación de todas las permutaciones de cada conjunto múltiple de la lista que le da a su solución. No voy a entrar en eso, hay un algoritmo recursivo que básicamente dice que, para cada posición, elija cada elemento único en el conjunto múltiple y anexe las permutaciones del conjunto múltiple resultante de eliminar ese elemento del conjunto múltiple.

Answer 2

Teniendo en cuenta que esta pregunta fuera de interés, es probable que estar interesado una respuesta authorative! Se puede encontrar en "7.2.1.2 - Generación de todas las permutaciones de" Knuth de El Arte de la Programación de Computadoras (subvolume 4A).

También, 3 algoritmos concretos pueden encontrarse here.

Answer 3

Como he mencionado anteriormente, no pude conseguir @ código de rlibby a trabajar para mis necesidades, y necesitaba código donde n = l, por lo que sólo un subconjunto de sus necesidades. Aquí está mi código a continuación, en C#. Sé que no es una respuesta perfecta a la pregunta anterior, pero creo que solo tendrías que modificar el primer método para hacerlo funcionar con diferentes valores de l; Básicamente, agregue el mismo código que @rlibby, haciendo la matriz de longitud l en vez de longitud n.

public static List<int[]> GetPartitionPermutations(int n) 
{ 
    int[] l = new int[n]; 

    var results = new List<int[]>(); 

    GeneratePermutations(l, n, n, 0, results); 
    return results; 
} 

private static void GeneratePermutations(int[] l, int n, int nMax, int i, List<int[]> results) 
{ 
    if (n == 0) 
    { 
     for (; i < l.Length; ++i) 
     { 
      l[i] = 0; 
     } 
     results.Add(l.ToArray()); 
     return; 
    } 

    for (int cnt = Math.Min(nMax, n); cnt > 0; --cnt) 
    { 
     l[i] = cnt; 
     GeneratePermutations(l, (n - cnt), cnt, i + 1, results); 
    } 
} 

Answer 4

Como se ha señalado por @pbarranis, el código por @rlibby no incluye todas las listas cuando n es igual ak. Debajo está el código de Python que incluye todas las listas. Este código no es recursivo, lo que puede ser más eficiente con respecto al uso de la memoria.

def successor(n, l): 
    idx = [j for j in range(len(l)) if l[j] < l[0]-1] 
    if not idx: 
    return False 

    i = idx[0] 
    l[1:i+1] = [l[i]+1]*(len(l[1:i+1])) 
    l[0] = n - sum(l[1:]) 
    return True 

def partitions(n, k): 
    l = [0]*k 
    l[0] = n 
    results = [] 
    results.append(list(l)) 
    while successor(n, l): 
    results.append(list(l)) 
    return results 

Las listas se crean con el fin colexicographic (algoritmo y más Descripción here).

Answer 5

Un montón de búsqueda dirigido a esta pregunta.Aquí es una respuesta que incluye las permutaciones:

#!/usr/bin/python 
from itertools import combinations_with_replacement as cr 
def all_partitions(n, k): 
    """ 
    Return all possible combinations that add up to n 
    i.e. divide n objects in k DISTINCT boxes in all possible ways 
    """ 
    all_part = [] 
    for div in cr(range(n+1), k-1): 
     counts = [div[0]] 
     for i in range(1, k-1): 
      counts.append(div[i] - div[i-1]) 
     counts.append(n-div[-1]) 
     all_part.append(counts) 
    return all_part 

Por ejemplo, all_part (4, 3) como se le preguntó por OP da:

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

Answer 6

He encontrado que el uso de una función recursiva no era bueno para mayor longitudes y enteros porque mastica demasiada RAM, y el uso de un generador/función reanudable (que 'cede' valores) era demasiado lento y requería una gran biblioteca para hacerlo multiplataforma.

Así que aquí es un no-recursivo solución en C++ que produce las particiones en fin ordenados (que es ideal para las permutaciones también). He descubierto que es 10 veces más rápido que las soluciones recursivas aparentemente inteligentes y concisas que probé para longitudes de partición de 4 o más, pero para longitudes de 1-3 el rendimiento no es necesariamente mejor (y no me importa el corto longitudes porque son rápidos con cualquier enfoque).

// Inputs 
unsigned short myInt = 10; 
unsigned short len = 3; 

// Partition variables. 
vector<unsigned short> partition(len); 
unsigned short last = len - 1; 
unsigned short penult = last - 1; 
short cur = penult; // Can dip into negative value when len is 1 or 2. Can be changed to unsigned if len is always >=3. 
unsigned short sum = 0; 

// Prefill partition with 0. 
fill(partition.begin(), partition.end(), 0); 

do { 
    // Calculate remainder. 
    partition[last] = max(0, myInt - sum); // Would only need "myInt - sum" if partition vector contains signed ints. 

    /* 
    * 
    * DO SOMETHING WITH "partition" HERE. 
    * 
    */ 

    if (partition[cur + 1] <= partition[cur] + 1) { 
     do { 
      cur--; 
     } while (
      cur > 0 && 
      accumulate(partition.cbegin(), partition.cbegin() + cur, 0) + (len - cur) * (partition[cur] + 1) > myInt 
     ); 

     // Escape if seeked behind too far. 
     // I think this if-statement is only useful when len is 1 or 2, can probably be removed if len is always >=3. 
     if (cur < 0) { 
      break; 
     } 

     // Increment the new cur position. 
     sum++; 
     partition[cur]++; 

     // The value in each position must be at least as large as the 
     // value in the previous position.    
     for (unsigned short i = cur + 1; i < last; ++i) { 
      sum = sum - partition[i] + partition[i - 1]; 
      partition[i] = partition[i - 1]; 
     } 

     // Reset cur for next time. 
     cur = penult; 
    } 
    else { 
     sum++; 
     partition[penult]++; 
    } 

} while (myInt - sum >= partition[penult]); 

donde he contado hacer algo con "partición" AQUÍ. es donde realmente consumiría el valor. (En la última iteración del código continuará ejecutando el resto del bucle pero encontrado que esto es mejor que el constante control de condiciones de salida - está optimizado para operaciones de mayor envergadura)

0,0,10 
0,1,9 
0,2,8 
0,3,7 
0,4,6 
0,5,5 
1,1,8 
1,2,7 
1,3,6 
1,4,5 
2,2,6 
2,3,5 
2,4,4 
3,3,4 

Oh I' he usado "corto sin firmar" porque sé que mi longitud y número entero no excederán ciertos límites; cámbialo si no es adecuado para ti :) Revisa los comentarios; una variable allí (cur) tuvo que estar firmada para manejar longitudes de 1 o 2 y hay una instrucción if correspondiente que va con eso, y también he notado en un comentario que si su vector de partición tiene entradas firmadas hay otra línea eso se puede simplificar

para obtener todas las composiciones, en C++ que usarían esta estrategia de permutación sencilla que afortunadamente no produce ningún duplicado:

do { 
    // Your code goes here. 
} while (next_permutation(partition.begin(), partition.end())); 

Nido que en el hacer algo con "partición" AQUÍ lugar, y eres bueno para ir.

Una alternativa para encontrar las composiciones (basado en el código de Java aquí https://www.nayuki.io/page/next-lexicographical-permutation-algorithm) es la siguiente. He encontrado que funciona mejor que next_permutation().

// Process lexicographic permutations of partition (compositions). 
composition = partition; 
do { 

    // Your code goes here. 

    // Find longest non-increasing suffix 
    i = last; 
    while (i > 0 && composition[i - 1] >= composition[i]) { 
     --i; 
    } 
    // Now i is the head index of the suffix 

    // Are we at the last permutation already? 
    if (i <= 0) { 
     break; 
    } 

    // Let array[i - 1] be the pivot 
    // Find rightmost element that exceeds the pivot 
    j = last; 
    while (composition[j] <= composition[i - 1]) 
     --j; 
    // Now the value array[j] will become the new pivot 
    // Assertion: j >= i 

    // Swap the pivot with j 
    temp = composition[i - 1]; 
    composition[i - 1] = composition[j]; 
    composition[j] = temp; 

    // Reverse the suffix 
    j = last; 
    while (i < j) { 
     temp = composition[i]; 
     composition[i] = composition[j]; 
     composition[j] = temp; 
     ++i; 
     --j; 
    } 
} while (true); 

Se dará cuenta de algunas variables no declaradas allí, sólo los declaró anteriormente en el código antes de que todos sus bucles do-: i, j, pos y temp (unsignedshorts), y composition (mismo tipo y duración como partition). Puede reutilizar la declaración de i para su uso en un for-loop en el fragmento de código de particiones. También tenga en cuenta variables como last que se supone que este código está anidado dentro del código de particiones dado anteriormente.

Nuevamente "Tu código va aquí" es donde consumes la composición para tus propios fines.

Como referencia, aquí están mis encabezados.

#include <vector> // for std::vector 
#include <numeric> // for std::accumulate 
#include <algorithm> // for std::next_permutation and std::max 
using namespace std; 

A pesar del aumento masivo de la velocidad por medio de estos enfoques, para cualquier número entero considerables y longitudes de partición esto todavía le hará enojado con su CPU :)