如何按照排序顺序生成一个数组的所有排列？

Question

我有一个数组，用户可以插入一个字符串。

以下是我的代码：

int main(){
  char anagrama[13];
  cin >> anagrama;
  for(int j = 0; j < strlen(anagrama); j++){
    cout << anagrama[j];
    for(int k = 0; k < strlen(anagrama); k++){
      if(j != k)
        cout << anagrama[k];
    }
    cout << endl;
  }
}

问题在于我需要按照排序顺序列出字符串的所有排列组合。

例如，如果用户输入：abc，则输出必须是：

abc
acb
bac
bca
cab
cba

我的代码没有显示所有排列，并且也没有排序

你能帮我吗？

我需要实现，但是不能使用已有的函数。

我想用递归函数，但是不知道怎么做。

这是一个例子： http://www.disfrutalasmatematicas.com/combinatoria/combinaciones-permutaciones-calculadora.html ，不重复且已排序

- Code Geas Coder

---

鉴于“没有已经实现的功能”意味着作业，因此我不会提供完整的代码。是的，您可以使用递归。迭代字符串中的字符，每次删除该字符，以便在调用本身时可以通过仍未使用的字符传递。合理的函数签名为void f(std::vector<std::string>& results, const std::string& unused_chars, const std::string& prefix_so_far = "")。如果f发现unused_chars为空，则可以将prefix_so_far添加到results中。 - Tony Delroy

组合与排列不同（以您的示例为例）。在组合中，元素的顺序并不重要，而在排列中顺序是重要的。 - rendon

将所有组合推入向量中，然后进行排序。 - someone_ smiley

Answer 1

在C++中，您可以使用std::next_permutation逐个遍历排列。在第一次调用std::next_permutation之前，需要按字母顺序对字符进行排序：

cin>>anagrama;
int len = strlen(anagrama);
sort(anagrama, anagrama+len);
do {
    cout << anagrama << endl;
} while (next_permutation(anagrama, anagrama+len));

这里有一个关于 Ideone 的 演示。

如果你必须自己实现排列，你可以借用next_permutation的源代码，或者选择一种更简单的递归方式来实现排列算法。

- Sergey Kalinichenko

---

不，我需要实现排列，不能使用函数。 - Code Geas Coder

我打算使用递归实现一个排列算法，但是我遇到了一些问题。 - Code Geas Coder

Answer 2

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

using namespace std;

void permute(string select, string remain){
    if(remain == ""){
        cout << select << endl;
        return;
    }
    for(int i=0;remain[i];++i){
        string wk(remain);
        permute(select + remain[i], wk.erase(i, 1));
    }
}

int main(){
    string anagrama;
    cout << "input character set >";
    cin >> anagrama;
    sort(anagrama.begin(), anagrama.end());
    permute("", anagrama);
}

---

另一个版本

#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>

using namespace std;

void permute(string& list, int level, vector<string>& v){
    if(level == list.size()){
        v.push_back(list);
        return;
    }
    for(int i=level;list[i];++i){
        swap(list[level], list[i]);
        permute(list, level + 1, v);
        swap(list[level], list[i]);
    }
}

int main(){
    string anagrama;
    vector<string> v;
    cout << "input character set >";
    cin >> anagrama;
    permute(anagrama, 0, v);
    sort(v.begin(), v.end());
    copy(v.begin(), v.end(), ostream_iterator<string>(cout, "\n"));
}

- BLUEPIXY

---

好的，但是“string（wk）”是什么？这个函数有什么作用？ - Code Geas Coder

我该如何对输出进行排序？ - Code Geas Coder

@AlexanderOvalle wk(remain) 构造函数。将 remain 复制到 wk 中。 - BLUEPIXY

为什么我每个周期都要声明wc？ - BLUEPIXY

@AlexanderOvalle swap交换指定元素。在这个版本中，它被交换而不是删除。 - BLUEPIXY

Answer 3

@alexander 这个程序的输出顺序与您请求的完全相同：

下面是一个最简单的代码，可以生成给定数组的所有组合/排列，而不包括一些特殊库（只包括 iostream.h 和 string），并且没有使用比通常更多的特殊命名空间（仅使用 namespace std）。

void shuffle_string_algo( string ark )
{

//generating multi-dimentional array:

char** alpha = new char*[ark.length()];
for (int i = 0; i < ark.length(); i++)
    alpha[i] = new char[ark.length()];

//populating given string combinations over multi-dimentional array
for (int i = 0; i < ark.length(); i++)
    for (int j = 0; j < ark.length(); j++)
        for (int n = 0; n < ark.length(); n++)
            if( (j+n) <= 2 * (ark.length() -1) )
                if( i == j-n)
                    alpha[i][j] = ark[n];
                else if( (i-n)== j)
                    alpha[i][j] = ark[ ark.length() - n];

if(ark.length()>=2)
{
    for(int i=0; i<ark.length() ; i++)
    {
        char* shuffle_this_also = new char(ark.length());
        int j=0;
        //storing first digit in golobal array ma
        ma[v] = alpha[i][j];

        //getting the remaning string
        for (; j < ark.length(); j++)
            if( (j+1)<ark.length())
                shuffle_this_also[j] = alpha[i][j+1];
            else
                break;
        shuffle_this_also[j]='\0';

        //converting to string
        string send_this(shuffle_this_also);

        //checking if further combinations exist or not
        if(send_this.length()>=2)
        {
            //review the logic to get the working idea of v++ and v--
            v++;
            shuffle_string_algo( send_this);
            v--;
        }
        else
        {
            //if, further combinations are not possiable print these combinations 
            ma[v] = alpha[i][0];
            ma[++v] = alpha[i][1];
            ma[++v] = '\0';
            v=v-2;

            string disply(ma);
            cout<<++permutaioning<<":\t"<<disply<<endl;
        }
    }
}
}

和主要：

int main()
{
string a;
int ch;
do
{
    system("CLS");
    cout<<"PERMUNATING BY ARK's ALGORITH"<<endl;
    cout<<"Enter string: ";
    fflush(stdin);
    getline(cin, a);

    ma = new char[a.length()];

    shuffle_string_algo(a);

    cout<<"Do you want another Permutation?? (1/0): ";
    cin>>ch;
} while (ch!=0);

return 0;
}

希望能对你有所帮助！如果你在理解逻辑方面遇到问题，请在下方评论，我会进行编辑。

- ARK

Answer 4

/*Think of this as a tree. The depth of the tree is same as the length of string.
In this code, I am starting from root node " " with level -1. It has as many children as the characters in string. From there onwards, I am pushing all the string characters in stack.
Algo is like this:

1. Put root node in stack.
2. Loop till stack is empty
2.a If backtracking
2.a.1 loop from last of the string character to present depth or level and reconfigure datastruture.
2.b Enter the present char from stack into output char

2.c If this is leaf node, print output and continue with backtracking on.
2.d Else find all the neighbors or children of this node and put it them on stack. */



        class StringEnumerator
        {
        char* m_string;
        int   m_length;
        int   m_nextItr;
        public:
        StringEnumerator(char* str, int length): m_string(new char[length + 1]), m_length(length)  , m_Complete(m_length, false)
        {
        memcpy(m_string, str, length);
        m_string[length] = 0;
        }
    StringEnumerator(const char* str, int length): m_string(new char[length + 1]), m_length(length)  , m_Complete(m_length, false)
    {
        memcpy(m_string, str, length);
        m_string[length] = 0;
    }
    ~StringEnumerator()
    {
        delete []m_string;
    }

    void Enumerate();
   };


        const int MAX_STR_LEN = 1024;
        const int BEGIN_CHAR = 0;

        struct StackElem
        {  
      char Elem;
      int Level;
      StackElem(): Level(0), Elem(0){}
      StackElem(char elem, int level): Elem(elem), Level(level){}

        };

        struct CharNode
        {
      int Max;
      int Curr;
      int Itr;
      CharNode(int max = 0): Max(max), Curr(0), Itr(0){}
      bool IsAvailable(){return (Max > Curr);}
      void Increase()
      {
        if(Curr < Max)
            Curr++;
      }
      void Decrease()
      {
        if(Curr > 0)
            Curr--;
       }
       void PrepareItr()
      {
        Itr = Curr;
       }
};




        void StringEnumerator::Enumerate()
{

    stack<StackElem> CStack;
    int count = 0;
    CStack.push(StackElem(BEGIN_CHAR,-1));
    char answerStr[MAX_STR_LEN];
    memset(answerStr, 0, MAX_STR_LEN);

    bool forwardPath = true;

    typedef std::map<char, CharNode> CharMap;

    typedef CharMap::iterator CharItr;
    typedef std::pair<char, CharNode> CharPair;

    CharMap mCharMap;
    CharItr itr;

    //Prepare Char Map
    for(int i = 0; i < m_length; i++)
    {
        itr = mCharMap.find(m_string[i]);
        if(itr != mCharMap.end())
        {
            itr->second.Max++;
        }
        else
        {
            mCharMap.insert(CharPair(m_string[i], CharNode(1)));
        }
    }


    while(CStack.size() > 0)
    {
        StackElem elem = CStack.top();
        CStack.pop();

        if(elem.Level != -1)     // No root node
        {
            int currl = m_length - 1;
            if(!forwardPath)
            {
                while(currl >= elem.Level)
                {
                    itr = mCharMap.find(answerStr[currl]);
                    if((itr != mCharMap.end()))
                    {
                        itr->second.Decrease();
                    }
                    currl--;
                }

                forwardPath = true;
            }

            answerStr[elem.Level] = elem.Elem;

            itr = mCharMap.find(elem.Elem);
            if((itr != mCharMap.end()))
            {
                itr->second.Increase();
            }
        }

        //If leaf node
        if(elem.Level == (m_length - 1))
        {
            count++;
            cout<<count<<endl;
            cout<<answerStr<<endl;
            forwardPath = false;
            continue;
        }

        itr = mCharMap.begin();

        while(itr != mCharMap.end())
        {
            itr->second.PrepareItr();
            itr++;
        }


        //Find neighbors of this elem 
        for(int i = 0; i < m_length; i++)
        {
            itr = mCharMap.find(m_string[i]);
            if(/*(itr != mCharMap.end()) &&*/ (itr->second.Itr < itr->second.Max))
            {
                CStack.push(StackElem(m_string[i], elem.Level + 1));
                itr->second.Itr++;
            }
        }


    }


}

- akhileshzmishra

Answer 5

我已经写了一个没有实现任何函数和模板的版本，实际上它是用C编写的，但已被转换为C++。

易于理解但效率较低，其输出结果是您想要的，已排序。

#include <iostream>
#define N 4
using namespace std;

char ch[] = "abcd";

int func(int n) {
    int i,j;
    char temp;
    if(n==0) {
        for(j=N-1;j>=0;j--)
            cout<<ch[j];
        cout<<endl;
        return 0;
    }
    for(i=0;i<n;i++){
        temp = ch[i];
        for(j=i+1;j<n;j++)
            ch[j-1] = ch[j];
        ch[n-1] = temp;
        //shift
        func(n-1);
        for(j=n-1;j>i;j--)
            ch[j] = ch[j-1];
        ch[i] = temp;
        //and shift back agian
    }
    return 1;
}

int main(void)
{
    func(N);
    return 0;
}

- vvy

---

与标准库函数相比，理解起来并不那么容易。 - Abhinav Gauniyal

Answer 6

如果你有一个字符串的std::vector，那么你可以按照下面的方式“排列”向量项。 C++14 代码

#include <iostream>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <boost/algorithm/string/join.hpp>
using namespace std;

int main() {
    // your code goes here
    std::vector<std::string> s;
    s.push_back("abc");
    s.push_back("def");
    s.push_back("ghi");

    std::sort(s.begin(), s.end());
    do
    {
      std::cout << boost::algorithm::join(s,"_") << std::endl ;
    } while(std::next_permutation(s.begin(), s.end())); 
    return 0;
}

输出:

abc_def_ghi

abc_ghi_def

def_abc_ghi

def_ghi_abc

ghi_abc_def

ghi_def_abc

- Mitendra