Recursive Permutation C++

Question

I have problem with assignment, we need to implement recursive permutation in c++ for numbers. Here is the code which is partly working, but missing some numbers. I can't find where the problem is.

This code does work, but not exactly the right way.

This code take and array of number with size of that array. in this case I am trying to solve the problem which appears when I send array longer than 3 numbers. If I send 3 numbers, output is:

Output in this case is correct. But when I set array to 4 and send size of it 4 I get:

///
1 2 3 4 /
1 2 4 3 /
1 4 2 3 /
4 1 2 3 / 
**2 1 3   /
2 3 1   /
3 2 1   /**
3 2 1 4 /
3 2 4 1 / 
3 4 2 1 /
4 3 2 1 /

Output is partly correct, but some numbers are missing.

Program should give output of all possible variations of numbers in array

#include <iostream>
using namespace std;

bool nextPermutation(int[],int);
void swap(int&, int&);
int Maxind(int[],int);
int Minind(int[],int);
void print (int[], int);
bool test (int[], int);
int fl=0;


int main() {
    int a[]={1,2,3,4};
    nextPermutation(a,4);
    return 0;
}


void print(int a[], int s) {
    for(int i=0; i<s; i++) 
    { 
        cout<<a[i]<<" "; 
    }
    cout<<endl;
}
bool nextPermutation(int a[], int s)
{
    int i=Maxind(a,s);
    if(fl==0)
        print(a,s);
    if(i!=0) {
        swap(a[i],a[i-1]);
        nextPermutation(a,s); 
    }

    else if(i==0 && test(a,s))
    {
        int p=a[0];
        for(int i=0; i<=s-2; i++)
            a[i]=a[i+1];
        fl=1;
        nextPermutation(a,s-1);
        a[s-1]=p;
        fl=0;
        nextPermutation(a,s);            
    }
    else 
        return false;
}

bool test (int a[], int s) {    
    if (Maxind(a,s)==0 && Minind(a,s)==s-1)
        return false;
    else
        return true;
}

void swap(int& a, int& b)
{
    int t=a; a=b; b=t;
}

int Maxind(int a[], int s)
{
    int m=a[0], ind=0;
    for(int i=0; i<s; i++) 
        if(m<a[i]) {
            m=a[i];
            ind=i;
        }
    return ind;
}

int Minind(int a[], int s)
{
    int m=a[0], ind=0;
    for(int i=0; i<s; i++) 
        if(m>a[i]) {
            m=a[i];
            ind=i;
        }
    return ind;
}

Have you tried stepping through it in a debugger line by line, while watching all variables? — Some programmer dude
If you want some help it would useful if you briefly explain what your code does etc. Did you step through the application in a debugger? — sebi
Some things I notice: fl is some global variable used only in nextPermutation which is generally bad design and error-prone. Then: You're doing permutation, but somehow depend on the numeric order of the elements (with Maxind / Minind). Permutation has nothing to do with the numeric order of the elements to permutate and therefore your algorithm shouldn't depend on it. — flyx
that implementation looks complex for such problem. search for "k permutation of n element with or without repetition" — alexbuisson

goGud goGud · Accepted Answer · 2013-09-04T06:47:41

You need to send all numbers of possibilities for permutation.

If you change your main function you will get the solution. Add a loop in main funciton and send to nextPermutation(a, i) with variable i

int main() {
    for(int i = 1; i < 5; i++) {
        int a[]= {1,2,3,4};
        nextPermutation(a,i);
    }
    return 0;
}

You should debug your program and also i figure out that your s value is decrasing here:

else if(i==0 && test(a,s)) {
    int p=a[0];
    for(int i=0; i<=s-2; i++) {
        a[i]=a[i+1];
    }
    fl=1;
    nextPermutation(a,s-1);
    //*** careful you are decreasing s here and your output gives 3 numbers. !!***
    a[s]=p;
    fl=0;
    nextPermutation(a,s);
}

Recursive Permutation C++

2 Answers