有人可以帮我这个：这是找任何长度的字符串的所有排列的程序。 需要同样的非递归形式。 （一个C语言实现是优选的）
using namespace std;
string swtch(string topermute, int x, int y)
{
string newstring = topermute;
newstring[x] = newstring[y];
newstring[y] = topermute[x]; //avoids temp variable
return newstring;
}
void permute(string topermute, int place)
{
if(place == topermute.length() - 1)
{
cout<<topermute<<endl;
}
for(int nextchar = place; nextchar < topermute.length(); nextchar++)
{
permute(swtch(topermute, place, nextchar),place+1);
}
}
int main(int argc, char* argv[])
{
if(argc!=2)
{
cout<<"Proper input is 'permute string'";
return 1;
}
permute(argv[1], 0);
return 0;
}
你的代码的基于堆栈的非递归相当于：
#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;
}
我试图使它类C，避免了C ++ STL容器和成员函数（用于简单构造虽然）。
请注意，在排列以相反的顺序，以原来的生成。
我要补充一点，以这种方式使用栈只是模拟递归。
另一种方法是将分配为n的数组！ 字符数组，并以同样的方式，你会用手工填写他们。
如果字符串为“ABCD”，把所有的“A”字符的位置为0第n-1个！ 阵列，在接下来的n-1个位置1！ 阵列等，然后把所有的“B”字符的位置1为第n-2个！ 阵列，等等，所有的“c”的字符的在第一n-3位2！ 阵列，等等，以及所有在3位的“d”的char第一n-4！ 阵列等，使用模n算术在每种情况下为您正在填写阵列移动从位置3到位置0。
没有交换是必要的，你早，如果你有足够的内存来存储结果还是不知道。
按值的字符串参数： - 第一种意见不及格性病。 使用常量引用
string swtch(const string& topermute, int x, int y)
void permute(const string & topermute, int place)
它会为你节省很多不必要的复制。
至于C ++的解决方案，你有功能std::next_permutation和std::prev_permutation在algorithm头。 所以，你可以这样写：
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;
}
至于℃溶液来，你必须从的std :: string改变变量类型为char *（啊，你必须正确地管理内存）。 我想类似的方法 - 写功能
int next_permutation(char * begin, char * end);
int prev_permutation(char * begin, char * end);
具有相同的语义，STL功能 - 会做。 你可以找到源代码std::next_permutation与解释这里 。 我希望你能设法写一个类似的代码，对char *作品（BTW标准:: next_permutation可以使用char *，没有任何问题的工作，但你想℃溶液来），因为我懒我自己做:-)
您必须使用STL试过吗？ 有一个叫这给直到遇到了所有排列了一系列将在每个后续调用返回true next_permutation算法。 作品不仅对字符串，但是，任何“序列”类型。
http://www.sgi.com/tech/stl/next_permutation.html
这解决了问题，而无需递归。 唯一的问题是，它会在一个字符字符串中重复的情况下产生重复的输出。
#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();
}
#include <iostream>
#include <string>
using namespace std;
void permuteString(string& str, int i)
{
for (int j = 0; j < i; j++) {
swap(str[j], str[j+1]);
cout << str << endl;
}
}
int factorial(int n)
{
if (n != 1) return n*factorial(n-1);
}
int main()
{
string str;
cout << "Enter string: ";
cin >> str;
cout << str.length() << endl;
int fact = factorial(str.length());
int a = fact/((str.length()-1));
for (int i = 0; i < a; i++) {
permuteString(str, (str.length()-1));
}
}
