Algoritmo per generare tutte le permutazioni univoche delle partizioni integer a lunghezza fissa?

Question

Sto cercando un algoritmo che generi tutte le permutazioni di partizioni a lunghezza fissa di un intero. L'ordine non ha importanza.

Ad esempio, per n = 4 e lunghezza 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 merito con divisori interi + permutazioni per divisori cui lunghezza è minore di L; ma che era troppo lento perché ho avuto nella stessa partizione più volte (perché [0, 0, 1] può essere una permutazione di [0, 0, 1] ;-)

Qualsiasi aiuto apprezzato, e no, questo non è compito - interesse personale :-)

Answer 1

Ok. Per prima cosa, dimentica le permutazioni e genera solo le partizioni di lunghezza L (come suggerito da @Svein Bringsli). Nota che per ogni partizione, puoi imporre un ordinamento sugli elementi, come>. Ora basta "contare", mantenendo il tuo ordine. Per n = 4, k = 3:

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

Quindi, come implementarlo? Sembra che mentre sottraendo 1 dalla posizione i e aggiungendolo alla posizione successiva si mantenga il nostro ordine, sottrarre 1 dalla posizione i, aggiungere 1 alla posizione i + 1 e passare alla posizione successiva. Se siamo nell'ultima posizione, fai un passo indietro.

Ecco un piccolo pitone, che fa proprio questo:

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 

Ora avete una lista di liste (in realtà un elenco di multinsiemi), e la generazione di tutte le permutazioni di ogni multinsieme della lista ti dà la soluzione. Non voglio addentrarmi in questo, c'è un algoritmo ricorsivo che sostanzialmente dice, per ogni posizione, scegliere ciascun elemento unico nel multiset e aggiungere le permutazioni del multiset risultanti dalla rimozione di quell'elemento dal multiset.

Answer 2

Dato che lo chiedi per interesse, probabilmente ti interesserebbe una risposta autoritaria! Può essere trovato in "7.2.1.2 - Generazione di tutte le permutazioni" di Knuth's The Art of Computer Programming (subvolume 4A).

Inoltre, è possibile trovare 3 algoritmi concreti here.

Answer 3

Come ho detto sopra, non ho potuto ottenere il codice di @ rlibby per funzionare per i miei bisogni, e avevo bisogno del codice dove n = l, quindi solo un sottoinsieme delle tue necessità. Ecco il mio codice qui sotto, in C#. So che non è perfettamente una risposta alla domanda di cui sopra, ma credo che dovresti solo modificare il primo metodo per farlo funzionare con valori diversi di l; in pratica aggiungo lo stesso codice @rlibby, rendendo l'array di lunghezza l invece della lunghezza 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

Come notato da @pbarranis, il codice da @rlibby non include tutte le liste quando n uguale k. Di seguito è riportato il codice Python che include tutti gli elenchi. Questo codice è non ricorsivo, che può essere più efficiente rispetto all'utilizzo della 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 

Gli elenchi vengono creati in ordine colexicographic (algoritmo e descrizione più here).

Answer 5

Molte ricerche hanno portato a questa domanda.Ecco una risposta che include le permutazioni:

#!/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 

Per esempio, all_part (4, 3) come richiesto dalla OP dà:

[[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

Ho trovato che l'uso di una funzione ricorsiva non era buono per i più grandi lunghezze e numeri interi perché mastica troppa RAM e l'uso di una funzione di generatore/riassunzione (che produce "valori") era troppo lento e richiedeva una libreria di grandi dimensioni per renderlo multipiattaforma.

quindi ecco una non ricorsiva soluzione in C++ che produce le partizioni in modo ordinato (che è l'ideale per permutazioni troppo). Ho trovato che questo è oltre 10 volte più veloce di soluzioni ricorsive apparentemente intelligenti e concise che ho provato per lunghezze di partizione di 4 o più, ma per lunghezze di 1-3 la performance non è necessariamente migliore (e non mi interessa di breve lunghezze perché sono veloci con entrambi gli approcci).

// 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]); 

Dove ho scritto fare qualcosa con "partizione" QUI. è dove si consumerebbe effettivamente il valore. (Su l'ultima iterazione del codice continuerà ad eseguire il resto del circuito, ma ho trovato questo per essere migliore di sempre controllando per condizioni di uscita - è ottimizzato per le operazioni più grandi)

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 io' ho usato "unsigned short" perché so che la mia lunghezza e il numero intero non supereranno determinati limiti, cambiatelo se non è adatto a te :) Controlla i commenti; una variabile lì (cur) doveva essere firmata per gestire lunghezze di 1 o 2 e c'è una corrispondente if-statement che va con quella, e ho anche notato in un commento che se il tuo vettore di partizione ha firmato c'è un'altra linea che può essere semplificato.

Per ottenere tutte le composizioni, in C++ vorrei utilizzare questa semplice strategia di permutazione che per fortuna non produce alcun duplicati:

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

Nest che nel fare qualcosa con "partizione" QUI posto, e sei a posto.

Un'alternativa alla ricerca delle composizioni (basata sul codice Java qui https://www.nayuki.io/page/next-lexicographical-permutation-algorithm) è la seguente. Ho trovato questo per funzionare meglio di 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); 

Noterete alcune variabili non dichiarate lì, basta dichiarare in precedenza nel codice prima di tutti i tuoi fai-loop: i, j, pos, e temp (pantaloncini firmati), e composition (stesso tipo e la lunghezza come partition). È possibile riutilizzare la dichiarazione di i per il suo utilizzo in un ciclo for nello snippet di codice delle partizioni. Si noti inoltre che vengono utilizzate variabili come last che presuppongono che questo codice sia nidificato all'interno del codice delle partizioni fornito in precedenza.

Ancora "Il codice va qui" è dove si consuma la composizione per i propri scopi.

Per riferimento qui sono le mie intestazioni.

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

Nonostante il massiccio aumento della velocità utilizzando questi approcci, per qualsiasi interi consistenti e le lunghezze di partizione questo sarà ancora farà arrabbiato con la CPU :)