Existe-il des meilleures méthodes pour faire de permutation de la chaîne?

Pourquoi ne pas vous essayer 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

j'aimerais seconder réponse de Permaquid . L'algorithme qu'il cite fonctionne d'une manière fondamentalement différente des divers algorithmes d'énumération par permutation qui ont été offerts. Il ne génère pas toutes les permutations de n objets, il génère une permutation spécifique distincte, donnée un entier entre 0 and n!-1 . Si vous n'avez besoin que d'une permutation spécifique, c'est beaucoup plus rapide que de les énumérer toutes et d'en sélectionner une.

même si vous avez besoin de toutes les permutations, il fournit des options qu'un algorithme d'énumération de permutation unique ne fournit pas. J'ai écrit une fois un cracker de cryptarithme de force brute, qui a essayé toutes les assignations possibles de lettres à des chiffres. Pour les problèmes base-10 , c'était adéquat, puisqu'il n'y a que des permutations 10! à essayer. Mais pour base-11 problèmes ont pris quelques minutes et base-12 problèmes ont pris près d'une heure.

j'ai remplacé la permutation algorithme d'énumération que j'avais utilisé avec un simple i=0--to--N-1 pour-boucle, en utilisant L'algorithme Permaquid Cité. Le résultat a été que légèrement plus lent. Mais ensuite j'ai divisé la gamme entière en quarts, et couru quatre pour-boucles simultanément, chacun dans un fil séparé. Sur mon processeur quad-core, le programme résultant a fonctionné près de quatre fois plus vite.

comme trouver une permutation individuelle en utilisant les algorithmes d'énumération de permutation est difficile, générant il est également difficile de délimiter les sous-ensembles de l'ensemble des permutations. L'algorithme que Permaquid a cité rend ces deux très facile

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

tout algorithme pour générer des permutations va s'exécuter en temps polynomial, parce que le nombre de permutations pour les caractères dans une chaîne de longueur n est (n!) . Cela dit, il y a quelques algorithmes assez simples en place pour générer des permutations. Vérifiez l'algorithme Johnson-Trotter .

l'algorithme Knuth random shuffle mérite d'être étudié.

// In-place shuffle of char array
void shuffle(char array[], int n)
{
    for ( ; n > 1; n--)
    {
        // Pick a random element to move to the end
        int k = rand() % n;  // 0 <= k <= n-1  

        // Simple swap of variables
        char tmp = array[k];
        array[k] = array[n-1];
        array[n-1] = tmp;
    }
}

tout algorithme qui utilise ou génère toutes les permutations prendra O (N!*N), O(N!) au moins pour générer toutes les permutations et O(N) pour utiliser le résultat, et c'est vraiment lent. Notez que l'impression de la chaîne est également en O(N) autant que je sache.

en une seconde, vous pouvez de façon réaliste seulement manipuler des chaînes jusqu'à un maximum de 10 ou 11 caractères, quelle que soit la méthode que vous utilisez. Depuis 11 ans!* 11 = 439084800 itérations (faire autant d'itérations en une seconde sur la plupart des machines c'est pousser) et 12!* 12 = 5748019200 itérations. Ainsi, même l'implémentation la plus rapide prendrait environ 30 à 60 secondes sur 12 caractères.

factoriel grandit trop vite pour que vous puissiez espérer gagner quoi que ce soit en écrivant une implémentation plus rapide, vous obtiendriez tout au plus un personnage. Donc je suggère la recommandation de Prasoon. C'est facile à coder et c'est assez rapide. Bien que coller à votre code est tout à fait bien aussi.

je vous recommande juste de prendre soin de vous ne pas avoir par inadvertance des caractères supplémentaires dans votre chaîne de caractères tels que le caractère null. Puisque cela rendra votre code un facteur de n plus lent.

j'ai récemment écrit un algorithme de permutation. Il utilise un vecteur de type T (template) au lieu d'une chaîne de caractères, et il n'est pas super rapide car il utilise la récursion et il y a beaucoup de copie. Mais peut-être Pouvez-vous vous inspirer du code. Vous pouvez trouver le code ici .

le seul pour améliorer de manière significative les performances est de trouver un moyen d'éviter d'itérer à travers toutes les permutations en premier lieu!

Permutant est inévitablement une opération lente (O(n!), ou pire, selon ce que vous faites avec chaque permutation), malheureusement rien que vous pouvez faire changera ce fait.

aussi, notez que n'importe quel compilateur moderne va aplatir votre récursion lorsque les optimisations sont activées, donc les (petits) gains de performance de l'optimisation manuelle sont encore réduits.

voulez-vous parcourir toutes les permutations, ou compter le nombre de permutations?

pour le premier, utilisez std::next_permutation comme suggéré par d'autres. Chaque permutation prend O (N) temps(mais moins de temps amorti) et aucune mémoire sauf son callframe, vs O(N) temps et O (N) mémoire pour votre fonction de récursion. Tout le processus est O(N!) et vous ne pouvez pas faire mieux que cela, comme d'autres l'ont dit, parce que vous ne pouvez pas obtenir plus de O (X) résultats d'un programme en moins de O (X) temps! Sans ordinateur quantique, en tout cas.

Pour le dernier, vous avez juste besoin de savoir combien d'éléments uniques dans la chaîne.

big_int count_permutations( string s ) {
    big_int divisor = 1;
    sort( s.begin(), s.end() );
    for ( string::iterator pen = s.begin(); pen != s.end(); ) {
        size_t cnt = 0;
        char value = * pen;
        while ( pen != s.end() && * pen == value ) ++ cnt, ++ pen;
        divisor *= big_int::factorial( cnt );
    }
    return big_int::factorial( s.size() ) / divisor;
}

vitesse est limitée par l'opération de trouver des éléments en double, qui pour char s peut être fait en O(N) temps avec une table de recherche.

je ne pense pas que c'est mieux, mais il fonctionne et ne pas utiliser la récursivité:

#include <iostream>
#include <stdexcept>
#include <tr1/cstdint>

::std::uint64_t fact(unsigned int v)
{
   ::std::uint64_t output = 1;
   for (unsigned int i = 2; i <= v; ++i) {
      output *= i;
   }
   return output;
}

void permute(const ::std::string &s)
{
   using ::std::cout;
   using ::std::uint64_t;
   typedef ::std::string::size_type size_t;

   static unsigned int max_size = 20;  // 21! > 2^64

   const size_t strsize = s.size();

   if (strsize > max_size) {
      throw ::std::overflow_error("This function can only permute strings of size 20 or less.");
   } else if (strsize < 1) {
      return;
   } else if (strsize == 1) {
      cout << "0 : " << s << '\n';
   } else {
      const uint64_t num_perms = fact(s.size());
      // Go through each permutation one-by-one
      for (uint64_t perm = 0; perm < num_perms; ++perm) {
         // The indexes of the original characters in the new permutation
         size_t idxs[max_size];

         // The indexes of the original characters in the new permutation in
         // terms of the list remaining after the first n characters are pulled
         // out.
         size_t residuals[max_size];

         // We use div to pull our permutation number apart into a set of
         // indexes.  This holds what's left of the permutation number.
         uint64_t permleft = perm;

         // For a given permutation figure out which character from the original
         // goes in each slot in the new permutation.  We start assuming that
         // any character could go in any slot, then narrow it down to the
         // remaining characters with each step.
         for (unsigned int i = strsize; i > 0; permleft /= i, --i) {
            uint64_t taken_char = permleft % i;
            residuals[strsize - i] = taken_char;

            // Translate indexes in terms of the list of remaining characters
            // into indexes in terms of the original string.
            for (unsigned int o = (strsize - i); o > 0; --o) {
               if (taken_char >= residuals[o - 1]) {
                  ++taken_char;
               }
            }
            idxs[strsize - i] = taken_char;
         }
         cout << perm << " : ";
         for (unsigned int i = 0; i < strsize; ++i) {
            cout << s[idxs[i]];
         }
         cout << '\n';
      }
   }
}

la chose amusante à ce sujet est que le seul État qu'il utilise de la permutation à la permutation est le nombre de la permutation, le nombre total de permutations, et la chaîne originale. Cela signifie qu'il peut être facilement encapsulé dans un itérateur ou quelque chose comme cela sans avoir à préserver avec soin l'état exact correct. Il peut même être un itérateur à accès aléatoire.

bien sûr ::std::next_permutation stocke l'état dans les relations entre les éléments, mais cela signifie qu'il ne peut pas fonctionner sur des choses non ordonnées, et je me demanderais vraiment ce qu'il fait si vous avez deux choses égales dans la séquence. Vous pouvez résoudre cela en permutant les index bien sûr, mais cela ajoute un peu plus de complication.

fonctionnera avec n'importe quelle plage d'itérateurs à accès aléatoire pourvu qu'elle soit assez courte. Et si ce n'est pas le cas, vous ne serez jamais obtenir par le biais de toutes les permutations de toute façon.

L'idée de base de cet algorithme est que chaque permutation de N éléments peuvent être énumérés. Le nombre total est de N! ou fact(N) . Et toute permutation donnée peut être considérée comme une cartographie des indices sources de la séquence originale dans un ensemble d'indices de destination dans la nouvelle séquence. Une fois que vous avez une énumération de toutes les permutations la seule chose à faire est de mapper chaque numéro de permutation dans une permutation réelle.

le premier élément de la liste permutée peut être n'importe lequel des N éléments de la liste originale. Le second élément peut être n'importe lequel des éléments n-1 restants, et ainsi de suite. L'algorithme utilise l'opérateur % pour séparer le numéro de permutation en un ensemble de sélections de cette nature. Tout d'abord,il modulo est le nombre de permutation par N pour obtenir un nombre de [0, N). Il écarte le reste en divisant par N, puis il modulo's it par la taille de la liste - 1 pour obtenir un nombre de [0, N-1] et ainsi de suite. C'est ce que fait la boucle for (i = .

la deuxième étape consiste à traduire chaque nombre en un index dans la liste originale. Le premier nombre est facile parce que c'est juste un index droit. Le second nombre est un index dans une liste qui contient tous les éléments sauf celui supprimé au premier index, et ainsi de suite. C'est ce que fait la boucle for (o = .

residuals est une liste d'indices dans les liste. idxs est une liste d'indices dans la liste d'origine. Il y a une correspondance unique entre les valeurs de residuals et idxs . Ils représentent chacun la même valeur dans différents espaces de coordonnées'.

la réponse pointée par la réponse que vous avez choisie a la même idée de base, mais a une façon beaucoup plus élégante d'accomplir la cartographie que ma méthode plutôt littérale et brute force. Ce chemin sera légèrement plus rapide que ma méthode, mais ils sont tous les deux environ la même vitesse et ils ont tous les deux le même avantage d'accès aléatoire dans l'espace de permutation qui rend un grand nombre de choses plus facile, y compris (comme la réponse que vous avez choisi souligné) algorithmes parallèles.

en fait, vous pouvez le faire en utilisant Knuth shuffling algo!

// find all the permutations of a string
// using Knuth radnom shuffling algorithm!

#include <iostream>
#include <string>

template <typename T, class Func>
void permutation(T array, std::size_t N, Func func)
{
    func(array);
    for (std::size_t n = N-1; n > 0; --n)
    {
        for (std::size_t k = 0; k <= n; ++k)
        {
            if (array[k] == array[n]) continue;
            using std::swap;
            swap(array[k], array[n]);
            func(array);
        }
    }
}

int main()
{
    while (std::cin.good())
    {
        std::string str;
        std::cin >> str;
        permutation(str, str.length(), [](std::string const &s){ 
            std::cout << s << std::endl; });
    }
}

This post: http://cplusplus.co.il/2009/11/14/enumerating-permutations / traite de permuter à peu près n'importe quoi, pas seulement des cordes. Le message en lui-même et les commentaires ci-dessous sont assez instructif et je ne voudrais pas faire un copier-coller..

si vous êtes intéressé par la génération de permutation, j'ai fait un article de recherche dessus il y a quelques temps: http://www.oriontransfer.co.nz/research/permutation-generation

il est livré complet avec le code source, et il ya environ 5 méthodes différentes mis en œuvre.

même moi j'ai trouvé difficile de comprendre cette version récursive de la première fois et il m'a fallu un certain temps pour chercher une voie berre.Meilleure méthode pour trouver (je pense) est d'utiliser l'algorithme proposé par Narayana Pandita . L'idée de base est:

1. triez D'abord la chaîne en ordre décroissant puis trouvez l'index du premier élément de la fin qui est inférieur à son caractère suivant lexicigraphiquement. Appeler cet élément indexe le "premier index".
2. maintenant trouver le plus petit caractère qui est plus grand que l'élément au "premier index". Appelez cet élément index le "ceilIndex".
3. remplace maintenant les éléments "firstIndex" et "ceilIndex".
4. inverser la partie de la chaîne de caractères à partir de l'index 'firstIndex+1' jusqu'à la fin de la chaîne.
5. (au lieu du point 4) Vous pouvez aussi trier la partie de la chaîne à partir de l'index 'firstIndex+1' à la fin de la chaîne.

points 4 et 5 font la même chose mais la complexité temporelle dans le cas du point 4 est O(n*n!) et que, dans le cas du point 5, Le Point 5 est O (N ^ 2*n!).

l'algorithme ci-dessus peut même être appliqué au cas où nous avons des caractères dupliqués dans la chaîne. :

le code pour afficher toute la permutation d'une chaîne de caractères :

#include <iostream>

using namespace std;

void swap(char *a, char *b)
{
    char tmp = *a;
    *a = *b;
    *b = tmp;
}


int partition(char arr[], int start, int end)
{
    int x = arr[end];
    int i = start - 1;
    for(int j = start; j <= end-1; j++)
    {
        if(arr[j] <= x)
        {
            i = i + 1;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i+1], &arr[end]);
    return i+1;
}

void quickSort(char arr[], int start, int end)
{
    if(start<end)
    {
        int q = partition(arr, start, end);
        quickSort(arr, start, q-1);
        quickSort(arr, q+1, end);
    }
}

int findCeilIndex(char *str, int firstIndex, int n)
{
    int ceilIndex;
    ceilIndex = firstIndex+1;

    for (int i = ceilIndex+1; i < n; i++)
    {
        if(str[i] >= str[firstIndex] && str[i] <= str[ceilIndex])
            ceilIndex = i;
    }
    return ceilIndex;
}

void reverse(char *str, int start, int end)
{
    while(start<=end)
    {
        char tmp = str[start];
        str[start] = str[end];
        str[end] = tmp;
        start++;
        end--;
    }
}

void permutate(char *str, int n)
{
    quickSort(str, 0, n-1);
    cout << str << endl;
    bool done = false;
    while(!done)
    {
        int firstIndex;
        for(firstIndex = n-2; firstIndex >=0; firstIndex--)
        {
            if(str[firstIndex] < str[firstIndex+1])
                break;
        }
        if(firstIndex<0)
            done = true;
        if(!done)
        {
            int ceilIndex;
            ceilIndex = findCeilIndex(str, firstIndex, n);
            swap(&str[firstIndex], &str[ceilIndex]);
            reverse(str, firstIndex+1, n-1);
            cout << str << endl;
        }
    }
}


int main()
{
    char str[] = "mmd";
    permutate(str, 3);
    return 0;
}

en Voilà un que je viens de bousculer!!

void permute(const char* str, int level=0, bool print=true) {

    if (print) std::cout << str << std::endl;

    char temp[30];
    for (int i = level; i<strlen(str); i++) {

        strcpy(temp, str);

        temp[level] = str[i];
        temp[i] = str[level];

        permute(temp, level+1, level!=i);
    }
}

int main() {
    permute("1234");

    return 0;
}

ce n'est pas la meilleure logique, mais alors, je suis un débutant. Je serai très heureux et obligé si quelqu'un me donne des suggestions sur ce code

#include<iostream.h>
#include<conio.h>
#include<string.h>
int c=1,j=1;


int fact(int p,int l)
{
int f=1;
for(j=1;j<=l;j++)
{
f=f*j;
if(f==p)
return 1;

}
return 0;
}


void rev(char *a,int q)
{
int l=strlen(a);
int m=l-q;
char t;
for(int x=m,y=0;x<q/2+m;x++,y++)
{
t=a[x];
a[x]=a[l-y-1];
a[l-y-1]=t;
}
c++;
cout<<a<<"  ";
}

int perm(char *a,int f,int cd)
{
if(c!=f)
{
int l=strlen(a);
rev(a,2);
cd++;
if(c==f)return 0;
if(cd*2==6)
{
for(int i=1;i<=c;i++)
{
if(fact(c/i,l)==1)
{
rev(a,j+1);
rev(a,2);
break;
}
}
cd=1;
}
rev(a,3);
perm(a,f,cd);
}
return 0;
}

void main()
{
clrscr();
char *a;
cout<<"\n\tEnter a Word";
cin>>a;
int f=1;

for(int o=1;o<=strlen(a);o++)
f=f*o;

perm(a,f,0);
getch();
}

**// Prints all permutation of a string**

    #include<bits/stdc++.h>
    using namespace std;


    void printPermutations(string input, string output){
        if(input.length() == 0){
            cout<<output <<endl;
            return;
        }

        for(int i=0; i<=output.length(); i++){
            printPermutations(input.substr(1),  output.substr(0,i) + input[0] + output.substr(i));
        }
    }

    int main(){
        string s = "ABC";
        printPermutations(s, "");
        return 0;
    }

  //***************anagrams**************//


  //************************************** this code works only when there are no   
  repeatations in the original string*************//
  #include<iostream>
  using namespace std;

  int counter=0;

  void print(char empty[],int size)
  {

  for(int i=0;i<size;i++)
  {
    cout<<empty[i];
  }
  cout<<endl;
  }


  void makecombination(char original[],char empty[],char comb[],int k,int& nc,int size)
{
nc=0;

int flag=0;
for(int i=0;i<size;i++)
{
    flag=0;                                                                   // {
    for(int j=0;j<k;j++)
    {
        if(empty[j]==original[i])                                                                // remove this code fragment
        {                                                                                        // to print permutations with repeatation
            flag=1;
            break;
        }
    }
    if(flag==0)                                                                // }
    {
        comb[nc++]=original[i];
    }
}
//cout<<"checks  ";
//    print(comb,nc);
}


void recurse(char original[],char empty[],int k,int size)
{
char *comb=new char[size];


int nc;


if(k==size)
{
    counter++;
    print(empty,size);
    //cout<<counter<<endl;

}
else
{
    makecombination(original,empty,comb,k,nc,size);
    k=k+1;
    for(int i=0;i<nc;i++)
    {
        empty[k-1]=comb[i];

        cout<<"k = "<<k<<" nc = "<<nc<<" empty[k-1] = "<<empty[k-1]<<endl;//checks the  value of k , nc, empty[k-1] for proper understanding
        recurse(original,empty,k,size);
    }
}

}

int main()
{
const int size=3;
int k=0;
char original[]="ABC";

char empty[size];
for(int f=0;f<size;f++)
empty[f]='*';

recurse(original,empty,k,size);

cout<<endl<<counter<<endl;
return 0;
}