How can I find all permutations of a string without using recursion?

Question

Can someone help me with this: This is a program to find all the permutations of a string of any length. Need a non-recursive form of the same. ( a C language implementation is preferred)

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

Solution 1

A stack based non-recursive equivalent of your code:

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

I've tried to make it C-like and avoided c++ STL containers and member functions (used a constructor for simplicity though).

Note, the permutations are generated in reverse order to the original.

I should add that using a stack in this way is just simulating recursion.

Solution 2

Another approach would be to allocate an array of n! char arrays and fill them in the same way that you would by hand.

If the string is "abcd", put all of the "a" chars in position 0 for the first n-1! arrays, in position 1 for the next n-1! arrays, etc. Then put all of the "b" chars in position 1 for the first n-2! arrays, etc, all of the "c" chars in position 2 for the first n-3! arrays, etc, and all of the "d" chars in position 3 for the first n-4! arrays, etc, using modulo n arithmetic in each case to move from position 3 to position 0 as you are filling out the arrays.

No swapping is necessary and you know early on if you have enough memory to store the results or not.

Solution 3

First one advice - don't pass std:string arguments by value. Use const references

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

It will save you a lot of unnecessary copying.

As for C++ solution, you have functions std::next_permutation and std::prev_permutation in algorithm header. So you can write:

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

As for C solution, you have to change variables types from std::string to char * (ugh, and you have to manage memory properly). I think similar approach - writing functions

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

with same semantics as STL functions - will do. You can find source code for std::next_permutation with explanation here. I hope you can manage to write a similar code that works on char * (BTW std::next_permutation can work with char * with no problems, but you wanted C solution) as I am to lazy to do it by myself :-)

Solution 4

This solves the problem without recursion. The only issue is that it will generate duplicate output in the case where a character is repeated in the string.

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

View more solutions

Comments

[Harry Johnston]

This is an interesting approach to the problem, but unfortunately it will fail for a string longer than 12 characters because factorial(len) will overflow. It shouldn't be too hard to correct this, if you'd care to try? (Hint: allocate an integer array with the same length as the string.)

[sasidhar]

Not a complete solution to the problem, from n!/2 to n! the values are repeated from 1 to n!/2

[StepUp]

you should explain better your answer. It is not okay just post code without explanation. OP should understand what answers mean.