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

Answer 1

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 :-)

Answer 2

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.

Answer 3

Have you tried using the STL? There is an algorithm called next_permutation which given a range will return true on each subsequent call until all permutations have been encountered. Works not only on strings but on any "sequence" type.

http://www.sgi.com/tech/stl/next%5Fpermutation.html

Answer 4

This might be interesting for your: Counting QuickPerm Algorithm.