Как сгенерировать все перестановки массива в отсортированном порядке?

У меня есть массив, и пользователь может вставить строку.

И у меня есть этот код:

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 без повторения и сортировки

Ответ 1

В С++ вы можете использовать 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 или выбрать более простой способ реализации алгоритма перестановки рекурсивно.

Ответ 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"));
}

Ответ 3

/*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++;
            }
        }


    }


}

Ответ 4

@alexander вывод этой программы в точном порядке по вашему запросу:

ЗДЕСЬ, является простейшим кодом для генерации всех комбинаций/перестановок заданного массива без включения некоторых специальных библиотек (включены только iostream.h и строка) и без используя некоторые специальные пространства имен, чем обычно (используется только 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;
        }
    }
}
}

и main:

int main()
{
string a;
int ch;
do
{
    system("CLS");
    cout<<"PERMUNATING BY ARK 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;
}

НАДЕЖДА! это помогает! если у вас возникла проблема с пониманием логики, просто комментарий ниже, и я отредактирую.

Ответ 5

Я написал один без функции, уже реализованной даже с любыми шаблонами и контейнерами. на самом деле это было написано на 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;
}