Algorithme permettant de générer toutes les permutations uniques de partitions entières de longueur fixe?

Question

Je suis à la recherche d'un algorithme qui génère toutes les permutations de partitions de longueur fixe d'un entier. L'ordre n'a pas d'importance.

Par exemple, pour n = 4 et de longueur 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 environ avec des partitions entières + permutations pour les partitions dont la longueur est inférieure à L; mais cela était trop lent parce que je suis la même partition plusieurs fois (car [0, 0, 1] peut être une permutation de [0, 0, 1] ;-)

Toute aide appréciée, et non, ce n'est pas devoirs - intérêt personnel :-)

Answer 1

OK. D'abord, oubliez les permutations et générez simplement les partitions de longueur L (comme suggéré par @Svein Bringsli). Notez que pour chaque partition, vous pouvez imposer un ordre sur les éléments, tels que>. Maintenant, juste "compte", en maintenant votre commande. Pour n = 4, k = 3:

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

Alors, comment implémenter cela? Cela ressemble à: en soustrayant 1 de la position i et en l'ajoutant à la position suivante, nous maintenons notre ordre, soustrayons 1 de la position i, ajoutons 1 à la position i + 1 et passons à la position suivante. Si nous sommes dans la dernière position, reculez.

Voici un petit python qui fait juste que:

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 

Maintenant vous avez une liste de listes (vraiment une liste des multijeux), et générer toutes les permutations de chaque multiset de la liste vous donne votre solution. Je ne vais pas entrer là-dedans, il y a un algorithme récursif qui dit essentiellement, pour chaque position, choisir chaque élément unique dans le multiset et ajouter les permutations du multiset résultant de la suppression de cet élément du multiset.

Answer 2

Étant donné que vous posez cette question par intérêt, vous seriez probablement intéressé par une réponse officielle! Il peut être trouvé dans "7.2.1.2 - Générer toutes les permutations" de de Knuth L'art de la programmation informatique (subvolume 4A).

De plus, 3 algorithmes concrets peuvent être trouvés here.

Answer 3

Comme je l'ai mentionné ci-dessus, je ne pouvais pas obtenir le code de @ rlibby pour mes besoins, et j'avais besoin de code où n = l, donc juste un sous-ensemble de votre besoin. Voici mon code ci-dessous, en C#. Je sais que ce n'est pas parfaitement une réponse à la question ci-dessus, mais je crois que vous auriez seulement à modifier la première méthode pour le faire fonctionner pour différentes valeurs de l; Fondamentalement ajouter le même code @ rlibby fait, faisant le tableau de longueur l au lieu de longueur 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

Comme l'a noté @pbarranis, le code par @rlibby ne comprend pas toutes les listes lorsque n égal k. Ci-dessous le code Python qui inclut toutes les listes. Ce code est non récursif, ce qui peut être plus efficace en ce qui concerne l'utilisation de la mémoire.

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 

Les listes sont créées pour colexicographic (algorithme et description plus here).

Answer 5

Beaucoup de recherches ont conduit à cette question.Voici une réponse qui comprend les permutations:

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

Par exemple, all_part (4, 3) comme demandé par l'OP donne:

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

Je trouve que l'utilisation d'une fonction récursive n'a pas été bonne pour agrandir longueurs et entiers car il mâche trop de RAM, et l'utilisation d'une fonction générateur/resumable (qui donne des valeurs) était trop lente et nécessitait une grande bibliothèque pour la rendre multiplateforme.

est donc ici une solution non récursive en C++ qui produit les partitions dans ordre de tri (ce qui est idéal pour les permutations aussi). J'ai trouvé cela plus de 10 fois plus rapide que des solutions récursives apparemment intelligentes et concises que j'ai essayées pour des longueurs de partition de 4 ou plus, mais pour des longueurs de 1-3, la performance n'est pas forcément meilleure (et je m'en fiche longueurs parce qu'ils sont rapides avec l'une ou l'autre approche).

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

Là où j'ai écrit faire quelque chose avec "partition" ICI. est où vous consommeriez réellement la valeur. (Sur la dernière itération le code continuera à exécuter le reste de la boucle mais je trouve cela mieux que de vérifier en permanence des conditions de sortie - il est optimisé pour les opérations plus importantes)

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 » J'ai utilisé "short non signé" car je sais que ma longueur et mon entier ne dépasseront pas certaines limites, changez cela si cela ne vous convient pas :) Vérifiez les commentaires; une variable là (cur) a dû être signée pour gérer des longueurs de 1 ou 2 et il y a une instruction if correspondante qui va avec, et j'ai aussi noté dans un commentaire que si votre vecteur de partition a signé ints il y a une autre ligne cela peut être simplifié.

Pour obtenir toutes les compositions, en C++ je voudrais utiliser cette simple stratégie de permutation qui ne heureusement produit pas de doublons:

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

Nest que dans le faire quelque chose avec « partition » ICI place, et tu es bon à faire.

Une alternative à la recherche des compositions (basée sur le code Java ici https://www.nayuki.io/page/next-lexicographical-permutation-algorithm) est la suivante. J'ai trouvé que cela fonctionne mieux 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); 

Vous remarquerez certaines variables non déclarées là, il suffit de les déclarer plus tôt dans le code avant que toutes vos boucles do-: i, j, pos et temp (short non signés), et composition (même type et la longueur comme partition). Vous pouvez réutiliser la déclaration de i pour son utilisation dans une boucle for dans l'extrait de code de partitions. Notez également les variables telles que last utilisées qui supposent que ce code est imbriqué dans le code de partitions donné précédemment.

Encore une fois "Votre code va ici" est l'endroit où vous consommez la composition pour vos propres besoins.

Pour référence, voici mes en-têtes.

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

En dépit de l'augmentation massive de la vitesse à l'aide de ces approches, pour des entiers non négligeables et longueurs de partition ce sera toujours vous rendre fou à votre CPU :)