Как я могу найти все перестановки строки без использования рекурсии?

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

Answer 1

Другим подходом было бы выделить массив из n! и заполняйте их так же, как вы бы вручную.

Если строка «abcd», поместите все символы «a» в позицию 0 для первого n-1! массивы, в позиции 1 для следующего n-1! массивы и т. д. Затем поместите все символы "b" в положение 1 для первого n-2! массивы и т. д., все символы "c" в позиции 2 для первого n-3! массивы и т. д., и все символы "d" в позиции 3 для первого n-4! массивы и т. д., используя арифметику по модулю n в каждом случае для перемещения из позиции 3 в позицию 0 при заполнении массивов.

Замена не требуется, и вы уже давно знаете, достаточно ли у вас памяти для сохранения результатов.

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 и функций-членов (хотя для простоты использовал конструктор).

Обратите внимание, что перестановки генерируются в обратном порядке к оригиналу.

Я должен добавить, что использование стека таким образом просто симулирует рекурсию.

Answer 3

Вы пробовали использовать STL? Существует алгоритм под названием next_permutation, который при заданном диапазоне будет возвращать true при каждом последующем вызове, пока не будут встречены все перестановки. Работает не только со строками, но и с любым типом «sequence».

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

Answer 4

Первый совет - не передавайте аргументы std: string по значению. Используйте константные ссылки

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

Что касается решения C, вы должны изменить типы переменных с std :: string на char * (тьфу, и вы должны правильно управлять памятью). Я думаю, что аналогичный подход - написание функций

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

с той же семантикой, что и функции STL - подойдет. Вы можете найти исходный код для std::next_permutation с объяснением здесь . Я надеюсь, что вам удастся написать подобный код, который работает на char * (BTW std :: next_permutation может работать с char * без проблем, но вы хотели C-решение), так как мне лень делать это самостоятельно: -)

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

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