Existe-t-il de meilleures méthodes pour effectuer la permutation de chaîne?

Question

 void permute(string elems, int mid, int end)
{
    static int count;
    if (mid == end) {
        cout << ++count << " : " << elems << endl;
        return ;
    }
    else {
    for (int i = mid; i <= end; i++) {
            swap(elems, mid, i);
            permute(elems, mid + 1, end);
            swap(elems, mid, i);
        }
    }
}
 

La fonction ci-dessus montre les permutations de str (avec str[0..mid-1] tant que préfixe constant et str[mid..end] tant que suffixe permutable). Nous pouvons donc utiliser permute(str, 0, str.size() - 1) pour afficher toutes les permutations d'une chaîne.

Mais la fonction utilise un algorithme récursif; peut-être que ses performances pourraient être améliorées?

Existe-t-il de meilleures méthodes pour permuter une chaîne?

Answer 1

Voici un algorithme non récursif en C++ de l'article de Wikipédia pour les non-ordonnée génération de permutations. Pour la chaîne s de la longueur n, pour n'importe quel k de 0 de n! - 1 inclusivement, suivant modifie s afin d'obtenir une seule permutation (qui est, différentes de celles générées pour toute autre valeur de k sur la plage). Pour générer toutes les permutations, exécutez-le pour tout n! k valeurs sur la valeur d'origine de la s.

void permutation(int k, string &s) 
{
    for(int j = 1; j < s.size(); ++j) 
    {
        swap(s, k % (j + 1), j); 
        k = k / (j + 1);
    }
}

Ici, swap(s, i, j) swaps position i et j de la chaîne s.

Answer 2

Pourquoi n'essayez-vous pas std::next_permutation() ou std::prev_permutation() ?

Liens:

std :: next_permutation ()
std :: prev_permutation ()

Un exemple simple:

 #include<string>
#include<iostream>
#include<algorithm>

int main()
{
   std::string s="123";
   do
   {

      std::cout<<s<<std::endl;

   }while(std::next_permutation(s.begin(),s.end()));
}
 

Sortie:

 123
132
213
231
312
321
 

Answer 3

J'aimerais deuxième Permaquid de réponse. L'algorithme, il cite les œuvres d'une façon fondamentalement différente de l'différents permutation énumération des algorithmes qui ont été proposés. Il ne génère pas de toutes les permutations de n objets, il génère un distinct spécifique de permutation, étant donné un nombre entier compris entre 0 and n!-1. Si vous avez besoin qu'une seule permutation, c'est beaucoup plus rapide que d'énumérer tous et en sélectionnant l'un.

Même si vous avez besoin de toutes les permutations, il fournit des options qu'une seule permutation algorithme d'énumération n'est pas. Une fois, j'ai écrit un brute-force cryptarithm cracker, qui a essayé tous les moyens possibles d'affectation des lettres aux chiffres. Pour base-10 problèmes, il a été adéquat, car il y a seulement 10! permutations à essayer. Mais pour l' base-11 des problèmes ont pris une couple de minutes et base-12 des problèmes a fallu près d'une heure.

J'ai remplacé la permutation algorithme d'énumération que j'avais été à l'aide d'un simple i=0--to--N-1 pour la boucle, à l'aide de l'algorithme Permaquid cité. Le résultat a été que légèrement plus lent. Mais puis-je diviser l'intervalle entier dans les quartiers, et a couru de quatre pour-boucles simultanément, chacun dans un thread séparé. Sur mon processeur quad-core, le programme s'est déroulé près de quatre fois plus rapide.

Tout comme le fait de trouver une personne de permutation à l'aide de la permutation de l'énumération des algorithmes est difficile, générant délimitées sous-ensembles de l'ensemble de toutes les permutations est également difficile. L'algorithme que Permaquid cité fait à la fois de ces très facile

Answer 4

Voir permutations STL.

En particulier, vous voulez std :: next_permutation .

 void permute(string elems, int mid, int end)
{
  int count = 0;
  while(next_permutation(elems.begin()+mid, elems.end()))
    cout << << ++count << " : " << elems << endl;
}
 

... ou quelque chose comme ça...

Answer 5

Tout algorithme permettant de générer des permutations va s'exécuter en temps polynomial, car le nombre de permutations pour les caractères dans une chaîne de longueur n est égal à (n!) . Cela dit, il existe des algorithmes sur place assez simples pour générer des permutations. Découvrez l' algorithme de Johnson-Trotter .