C++

Forum

 
Question Permutation recursion

CDude (3)
Write your question here.
Hi guys, i want to write an boolnextPermutation(int array[],int arraySize), in which
1)
If the maximal element of the array (which is n) is not the first element of the
array, say n=ai , where i>1 , then to produce the "next" permutation you
need to swap ai and ai− 1 .
2）If the maximal element of the array is in the first position, i.e. n=a1 , then to
produce the “next” permutation to the permutation (a1 ,. . . ,an ) , first find the
“next” permutation to the (n-1)-element permutation (a2 , .. . ,a n) , and then
append a1 to the end of the obtained array of (n-1) elements.
so if a = [123] the result will be [132],[312],[213],[231],[321]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
 
  #include <iostream>
//#include <array>
using namespace std;

void print(int *a,int arraySize)
{
    for (int i =0 ;i<=arraySize-1;i++)
        cout << a[i];
    cout << endl;
}


int indOfMax(int *a,int from,int to)
{
    int ind = from;
    int max = a[from];
    for(int i = from; i <=to; i++)
        {
        if(max < a[i])
            {
            max = a[i];
            ind = i;
            }
        }
    return ind;
}


void swap(int *a, int first, int second)
{
    int temp;
    temp = a[first];
    a[first]= a[second];
    a[second] = temp;
}


bool nextPermutation(int *a,int arraySize)
{
    print(a,arraySize);
    int j = indOfMax(a,0,arraySize-1);
    if (j!=0)
    {
        swap(a,j,j-1);
        return nextPermutation(a,arraySize);
    }
    else
    {
        int max = a[0];
        for (int i = 0; i<=arraySize-2;i++)
        {
            a[i] = a [i+1];
        }

        if(nextPermutation(a,arraySize-1))
        {

            a[arraySize-1] = max;
            return nextPermutation(a,arraySize);
        }
        /*if (nextPermutation(a,arraySize-1))
        {
            a[arraySize-1] = max;
        }*/

    }
     return false;
}


int main()
{
    int a[3] = {1,2,3};

    nextPermutation(a,3);
    return 0;
}
keskiverto (10402)
What is the question?
CDude (3)
..well the question is, my code does not work well, and i have no idea where it has errors~
keskiverto (10402)
does not work well

Would you elaborate on that?
CDude (3)
it means that it debug well, but it will run out the memory once getting started
keskiverto (10402)
Lets say that the input array is {7}. How does the recursion end?
Topic archived. No new replies allowed.