Comment puis-je trouver toutes les permutations d'une chaîne sans utiliser la récursivité?

Une pile non-récursive équivalent de votre code:

#include <iostream>
#include <string>
struct State
{
State (std::string topermute_, int place_, int nextchar_, State* next_ = 0)
: topermute (topermute_)
, place (place_)
, nextchar (nextchar_)
, next (next_)
{
}
std::string topermute;
int place;
int nextchar;
State* next;
};
std::string swtch (std::string topermute, int x, int y)
{
std::string newstring = topermute;
newstring[x] = newstring[y];
newstring[y] = topermute[x]; //avoids temp variable
return newstring;
}
void permute (std::string topermute, int place = 0)
{
//Linked list stack.
State* top = new State (topermute, place, place);
while (top != 0)
{
State* pop = top;
top = pop->next;
if (pop->place == pop->topermute.length () - 1)
{
std::cout << pop->topermute << std::endl;
}
for (int i = pop->place; i < pop->topermute.length (); ++i)
{
top = new State (swtch (pop->topermute, pop->place, i), pop->place + 1, i, top);
}
delete pop;
}
}
int main (int argc, char* argv[])
{
if (argc!=2)    
{
std::cout<<"Proper input is 'permute string'";
return 1;
}
else
{
permute (argv[1]);
}
return 0;
}

J'ai essayé de faire en C et éviter c++ conteneurs STL et les fonctions membres (utilisé un constructeur pour des raisons de simplicité).

Remarque, les permutations sont générés dans l'ordre inverse à l'original.

Je dois ajouter que, à l'aide d'une pile de cette manière est tout simplement de simuler la récursivité.

OriginalL'auteur jon-hanson

Premier de conseils - ne pas passer std:chaîne d'arguments par valeur. Utiliser const références

string swtch(const string& topermute, int x, int y)
void permute(const string & topermute, int place)

Il vous permettra d'économiser beaucoup de copie inutile.

Comme pour C++ solution, vous disposez des fonctions std::next_permutation et std::prev_permutation dans algorithm en-tête. Vous pouvez donc écrire:

int main(int argc, char* argv[])
{    
if(argc!=2)    
{
cout<<"Proper input is 'permute string'" << endl;
return 1;
}
std::string copy = argv[1];
//program argument and lexically greater permutations
do
{
std::cout << copy << endl;
} 
while (std::next_permutation(copy.begin(), copy.end());
//lexically smaller permutations of argument
std::string copy = argv[1];
while (std::prev_permutation(copy.begin(), copy.end())
{
std::cout << copy << endl;
}
return 0;    
}

Comme pour la C la solution, vous avez à changer les variables de types de std::string en char * (pouah, et vous avez à gérer la mémoire correctement). Je pense approche similaire - l'écriture de fonctions

int next_permutation(char * begin, char * end);
int prev_permutation(char * begin, char * end);

avec la même sémantique que les fonctions STL - fera. Vous pouvez trouver le code source pour std::next_permutation avec explication ici. J'espère que vous parvenez à écrire un code similaire qui fonctionne sur char * (BTW std::next_permutation peut travailler avec char * pas de problèmes, mais vous avez voulu C) comme je suis trop paresseux pour le faire par moi-même 🙂

OriginalL'auteur Tadeusz Kopec

Cela résout le problème sans récursivité. Le seul problème est qu'il va générer des doublons de sortie dans le cas où un caractère est répété dans la chaîne.

#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<string.h>
int factorial(int n)
{
int fact=1;
for(int i=2;i<=n;i++)
fact*=i;
return fact;
}
char *str;
void swap(int i,int j)
{
char temp=str[i];
str[i]=str[j];
str[j]=temp;
}
void main()
{
clrscr();
int len,fact,count=1;
cout<<"Enter the string:";
gets(str);
len=strlen(str);
fact=factorial(len);
for(int i=0;i<fact;i++)
{
int j=i%(len-1);
swap(j,j+1);
cout<<"\n"<<count++<<". ";
for(int k=0;k<len;k++)
cout<<str[k];
}
getch();
}

OriginalL'auteur crashed