30

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

我有这个代码：

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 没有重复和排序

4

6 回答 6

50

在 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或者选择更简单的递归方式实现置换算法。

于 2013-07-01T00:59:17.203 回答
12 
#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"));
}
于 2013-07-01T01:40:07.813 回答
2 
/*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++;
            }
        }


    }


}
于 2014-04-02T04:47:14.970 回答
2

@alexander 该程序的输出与您要求的完全一致：

这里，是一个最简单的代码，用于生成给定数组的所有组合/排列，不包括一些特殊的库（只包括iostream.h和字符串），并且不使用一些特殊的命名空间（只使用命名空间 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;
}

希望！它可以帮助你！如果您在理解逻辑方面遇到问题，请在下面发表评论，我将进行编辑。

于 2014-08-02T15:17:28.000 回答
1

我写了一个甚至没有实现任何模板和容器的功能。实际上它最初是用 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;
}
于 2013-07-01T02:00:17.367 回答
1

如果您有 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

于 2018-11-12T09:22:02.903 回答