Writing a permutation function

Question

I've been asked to write a permutation function that uses recursion. The only parameter of the function should be the string that I should find all the permutations of. The function should return a vector with all possible permutations. I know I can use next_permutation in STL Algorithms, but I've been asked not to.

I have the base case set up, and I know I need a for loop, but I'm not quite sure where to go from there. Can someone point me in the right direction?

vector <string> getPerm(string str)
{
    vector<string> v;
    if(w.length() <= 1)
    {
        v.push_back(str);
        return v;
    }
    else
    {
        for(int i = 0; i < str.size(); i++)
        {
            //Some code
        }
    }
}

Any help would be appreciated.

Here's a [simple algorithm](http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order) for creating successive permutations, which might give you s start — Collin, Oct 24 '12 at 18:15
If you're writing an algorithm that uses recursion, you really don't want to look at Collin's algorithm nor at `next_permutation` because neither is recursive. — Ken Bloom, Oct 24 '12 at 18:26
Helpfull link: http://stackoverflow.com/questions/11483060/stdnext-permutation-implementation-explanation — Rontogiannis Aristofanis, Oct 24 '12 at 18:31
@RondogiannisAristophanes this is not a duplicate, becuase that version isn't recursive, and this one is. — Ken Bloom, Oct 24 '12 at 18:32
@KenBloom Correct, but it is a general strategy you might be able to figure out a recursive algorithm for — Collin, Oct 24 '12 at 18:33
@Collin: There is one *obvious* recursive algorithm, and it does not guarantee that your permutations come out in lexicographic order. Thus, the STL algorithm is not it. — Ken Bloom, Oct 24 '12 at 18:35

score 4 · Accepted Answer · answered Oct 24 '12 at 20:47

Imagine you already have the result of the previous iteration of your function, with returns all the permutations of the first n-1 elements of your string.

vector<string>& v_prev = getPerm(str.substr(0, str.length()-1));

Use this in the

//Some code

part of your code.

Another tip: use the 0-length string as the stop-condition of your recursion. You can construct the 1-lenght permutations recursively ;)

Here is the entire solution:

vector<string> getPerm(string str)
{
  vector<string> v; 
  if (str.empty())
  {
    v.push_back(string());
    return v;
  }
  else
  {
    vector<string>& v_prev = getPerm(str.substr(0, str.length()-1));
    for(int i = 0; i < v_prev.size(); i++)
    {
      for (int j = 0; j < v_prev[i].length() + 1; j++)
      {
        string p = v_prev[i];
        p.insert(j, str.substr(str.length() - 1, 1));
        v.push_back(p);
      }
    }
    return v;
  }
}

score 1 · Answer 2 · answered Oct 24 '12 at 18:17

Think about these permutations of the string "123"

And think about these permutations of "12"

12
21

Can you see how you might construct the permutations of a n letter string if you know the permutations of all the n-1 letter substrings. That type of solution would be recursive.

score 1 · Answer 3 · answered Oct 24 '12 at 18:31

1

For each element x in yourArray
- Make a copy of yourArray without element x. Call this new array newArray.
- Find all of the permutations of newArray
- add element x to the beginning of each of those permutations

answered Oct 24 '12 at 18:31

Ken Bloom

57,498
14
111
168

Rafał Wojciechowski · Answer 4 · 2012-10-24T21:35:19.527

1

Implementing what just Ken Bloom wrote:

vector <string> getPerm(string str)
{
  vector<string> v;
  if(str.length() <= 1)
  {
    v.push_back(str);
    return v;
  }
  else
  {
    for(int i = 0; i < str.size(); i++){
      vector<string> perms = getPerm(str.substr(0,i)+str.substr(i+1));

      for(int j = 0; j < perms.size(); j++){
        v.push_back(str[i] + perms[j]);
      }
    }
  }
}

edited Oct 24 '12 at 21:35

answered Oct 24 '12 at 19:29

Rafał Wojciechowski

141
3

problem with "copy-paste" fixed – Rafał Wojciechowski Oct 24 '12 at 21:39

score 0 · Answer 5 · answered Oct 24 '12 at 18:40

0

Try something like this:

permut(s) :
  if s.length=0 : exit;
  else :
    for i=0 to s.length :
      front:=s[i];
      remove(s,i);
      s2 := front + permut(s);
      print s2, NEWLINE;

answered Oct 24 '12 at 18:40

Rontogiannis Aristofanis

8,883
8
41
58

Writing a permutation function

5 Answers5