Permutaions With Recursion

[Lavitz]

hey guys. i was given a project today in my C++ class. The directions are as follows:

A. solicit from the user a positive integer n.
B. Generate and display a list of all the possible permutations of the first n integers.

in other words, the user inputs 3, the program spits out

123
132
213
231
312
321

now i dont want someone to post a full source code to this, id like to work on it myself, but im kinda stuck right now. i was wondering if someone could point me in the right direction as to what the recursive step might be.

i know that we have to use recursion (possibly more than one recursive function) and vectors (i think four of them) throughout the code. and i think the base case should look something like this (correct me if im wrong):

if (n==1)
      {
         (some code)
          return 1;
      }

any help would be greatly appreciated.

[WaltP]

Stuck with what? Maybe this will help... ;)

[aPPmaSTer]

It looks like we have a similar problem, Lavitz. I also have to make a recursive function, except with all possible combinations, not only one length.

An answer in either of our threads should help both of us out...

[Ancient Dragon]

One way to do it might be to convert the integer to a string to make it easier to manipulate the individual digits. sprintf() function will convert the int to a string.

[iamthwee]

Why use sprintf() in c++?

There is already a permute function in #include <algorithm> but I assume you can't use that for this exercise.

Check out the code snippets.

[Ancient Dragon]

Why use sprintf() in c++?

I agree that stringstream would be better solution than sprintf(), assuming the OP knows how to use it. Its not only a better solution but easier to use too.

[Lavitz]

we cant turn the ints into strings. there is an example of how to permute strings in the book and he doesnt want us opying it from the book basicly. we have to come up with a program that will give all the permutations as ints.

and i looked through the code snippets iamthwee, and i didnt see anything that would really help me.

[Ancient Dragon]

google is a good programmer's buddy (normally) Here is a thread I found that will help you.

[Lavitz]

ok after a few more class discussions, i still have no idea how to do this XD.

i do know that we are basicly writing the nextpermutation function from the algorithm class using recursion and integers (not strings which seems to be the only thing i can find through google). this is a chunk of my code so far.

#include <iostream>
#include <vector>

using namespace std;

int Factorial(int n)
{
    if (n == 1) return 1;
    return n * Factorial(n-1);
}

vector PermuteMe(vector Vect, int nFact)
{
//fill another vector of size n! with the permutations
}

int main()
{
    int j;
    cout << "Please enter a number to be permuted: ";
    cin >> j;
    int k = Factorial(j);
    vector<int> FillVect(j);
    for(i = 0, i < j, i++)
    {
        FillVect[i] = i + 1;
    }
    vector<int> PermuteVect(k) = PermuteMe(FillVect, k);
    for(i = 0, i < k, i ++)
    {
        cout << PermuteVect[i]
    }
    return 0;
}

any help filling in the holes or correcting my current code would be greatly appreciated.

[Lavitz]

After long hours of researching and coding, i came up with a working code. so for anyone who needs this in the future, this program will take an integer from the user and display all permutations of the first n numbers, n being the number given by the user. a side not, takes up a lot of ram. i wouldnt reccomend putting a number higher than 9. i got my computer to do 10, after a 30 minute wait, but it crashed midway through 11.

#include <iostream>
#include <vector>

using namespace std;

typedef vector<int> vint;

void erase(vector<int>& v, int pos)
{
 for(int i = pos; i < static_cast<int> (v.size() - 1); i++)
  v[i] = v[i + 1];
 v.pop_back();
}
vector <int> insert(vector<int> v, int pos, int s)
{
 int last = static_cast<int>(v.size()) - 1;
 v.push_back(v[last]);
 for (int i = last; i > pos; i--)
  v[i] = v[i - 1];
 v[pos] = s;
 return v;
}
std::vector<vint> PermuteMe(vector<int> num)
{
 vector<vint> result;
 if (num.size() == 1)
 {
  result.push_back(num);
  return result;
 }
 for(int i = 0; i < static_cast<int>(num.size()); i++)
 {
  vector<int> shorter_num = num;
  erase(shorter_num, i);
  vector<vint> shorter_permute = PermuteMe(shorter_num);
  for(int j = 0; j < static_cast<int>(shorter_permute.size()); j++)
  {
   vector<int> longer_num = insert(shorter_permute[j], 0, num[i]);
   result.push_back(longer_num);
  }
 }
 return result;
}
int main()
{    
 cout << "Please enter a number to be permuted: ";
 int j;
 cin >> j;
 cout << "\n";
 vector<int> FillVect;
 for(int i = 0; i < j; i++)
 {
  FillVect.push_back(i + 1);
 }
 vector<vint> PermuteVect = PermuteMe(FillVect);
 for(int i = 0; i < static_cast<int>(PermuteVect.size()); i++)
 {
  for(int k = 0; k < static_cast<int>(PermuteVect[i].size()); k++)
  {
   cout << PermuteVect[i][k] << " ";
  }
  cout << "\n";
 }
 return 0;
}

edit: sorry about the bad formating. the text editor thing doesnt like when i copy paste my code. gave me all these color things. and im kinda in a hurry so i didnt want to bother messing with it.