如何在不使用递归的情况下找出字符串的所有排列？

Question

有人能帮我解决这个问题吗：这是一个用于查找任意长度字符串的所有排列的程序。需要一种非递归形式的实现方式。(最好使用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;    
}

- Shrinidhi

---

这不是一个“C”语言解决方案——您使用了内置的字符串类型、cout、操作符重载……这要比由Stroustrup本人编写的更像C++。 - Chris Lutz

你是对的。[c]标签被删除以节省一个编辑。 - Tomalak

我在暗示我想要一个C语言实现这个C++代码。 - Shrinidhi

Answer 1

另一种方法是分配一个n！个字符数组的数组，并以手工方式填充它们。

如果字符串是“abcd”，则将所有“a”字符放在第一个n-1!数组的位置0中，在下一个n-1!数组的位置1中，依此类推。然后将所有“b”字符放在第一个n-2!数组的位置1中，以此类推，将所有“c”字符放在第一个n-3!数组的位置2中，以此类推，将所有“d”字符放在第一个n-4!数组的位置3中，使用模n算术在每种情况下从位置3移动到位置0，当您填写数组时，不需要交换，并且您很早就知道是否有足够的内存来存储结果。

- user1522420

Answer 2

一个基于堆栈的非递归版本的代码等价于：

#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容器和成员函数（只为简单起见使用构造函数）。

请注意，排列是按照与原始顺序相反的顺序生成的。

我应该补充说明，以这种方式使用堆栈只是模拟递归。

- jon-hanson

Answer 3

第一条建议 - 不要通过值传递std:string参数。使用const引用。

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

这将为您节省很多不必要的复制。

至于C++解决方案，您可以在头文件中使用std::next_permutation和std::prev_permutation函数。因此，您可以编写以下代码：

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;    
}

关于 C 的解决方案，您需要将变量类型从 std::string 更改为 char*（呃，您需要正确地管理内存）。我认为类似的方法是编写函数。

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

与STL函数相同的语义-没问题。您可以在这里找到带有解释的std::next_permutation源代码。我希望您能够编写类似的代码，以适用于char *（顺便说一句，std::next_permutation可以轻松使用char *，但您想要C解决方案），因为我懒得自己动手 :-)。

- Tadeusz Kopec for Ukraine

Answer 4

你尝试过使用STL吗？有一个叫做next_permutation的算法，它会在给定范围内返回true，直到遇到所有排列。它不仅适用于字符串，还适用于任何“序列”类型。

http://www.sgi.com/tech/stl/next_permutation.html

- Matthieu N.

---

我想你指的是这个链接：http://marknelson.us/2002/03/01/next-permutation/。 - Shrinidhi

是的，那是一篇很好的页面，解释了它的用法。只是想让你知道，在算法中还有一个std::prev_permutation函数。 - Matthieu N.

Answer 5

这种方法可以解决问题，而且不需要使用递归。唯一的问题是，在字符串中有重复字符的情况下，它会生成重复的输出。

#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();
}

- crashed

---

这是一个有趣的解决问题的方法，但不幸的是，对于长度超过12个字符的字符串，它将失败，因为factorial(len)会溢出。如果你愿意尝试的话，应该不难纠正这个问题。（提示：分配一个与字符串长度相同的整数数组。） - Harry Johnston

不是问题的完全解决方案，从n！/2到n！的值重复了从1到n！/2的值。 - sasidhar

Answer 6

#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));
    }   
}

- Susheel Hoolihalli

---

你应该更好地解释你的答案。仅仅发布代码而没有解释是不可以的。原帖作者应该理解答案的含义。 - StepUp