Generate all permutation

Pages: 12
georgek (19)
I try to create a program for generate all permutation (for example input nr=3 and result will be 1 2 3, 1 3 2, 2 3 1 ...). I try to use non-recursive backtracking. I don't understand why the program is not function propertly.
Here is my code:

#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;
bool valid(vector <int> v)
{
bool val=true;
for(int i=0; i<v.size(); i++)
for(int k=i+1; k<v.size(); k++)
if (v[i]==v[k]) val=false;
return val;
}

void write (vector <int> v)
{
for(int k=0; k<v.size(); k++)
cout<<v[k]<<" ";
cout<<endl;
}

void generate_permutations(int n)
{
vector <int> vec;
for(int i=1; i<=n; i++)
{
vec.push_back(i);
int k=1;
while(k>1)
{
vec.push_back(k);
if(!valid(vec))
{
vec.pop_back(); k++;}
else
{
if(vec.size()==n)
{
write(vec);
vec.pop_back();
k--;
}
else
{
if(vec[k]<n)
{
vec[k]++;
k++;
}
else
{
vec.pop_back();
k--;
}
}
}

}
vec.clear();
}
}

int main(int argc, char *argv[])
{
int n;
cout<<"nr: ";
cin>>n;
generate_permutations(n);
return 0;
}

What solutions is for repare this code?
Zaita (2770)
Ok.

Firstly, Please put your code in [c0de] your code here [/c0de] tags (replace 0 with o. (you can edit your post to do this)

Secondly, What are the symptoms of your problem? You tell us something is wrong, but how do you know? what is not working exactly right?

Help us, to help you by providing us with enough information.
http://www.cplusplus.com/forum/articles/1295/
Last edited on
georgek (19)
i think is for begginer section. apology please...i,m new here
Zaita (2770)
It doesn't matter if it's in beginner, or general C++. But you need to provide us with some more information to help us help you fix the problem.

Alot of the volunteers here don't have time to take alot of code, compile it and analyse it to see what is wrong. We rely on you telling us what the problem is so we can quickly scan the code for issues to help you solve it :)
georgek (19)
[c0de]
#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;
bool valid(vector <int> v)
{
bool val=true;
for(int i=0; i<v.size(); i++)
for(int k=i+1; k<v.size(); k++)
if (v[i]==v[k]) val=false;
return val;
}

void write (vector <int> v)
{
for(int k=0; k<v.size(); k++)
cout<<v[k]<<" ";
cout<<endl;
}

void generate_permutations(int n)
{
vector <int> vec;
for(int i=1; i<=n; i++)
{
vec.push_back(i);
int k=1;
while(k>1)
{
vec.push_back(k);
if(!valid(vec))
{
vec.pop_back(); k++;}
else
{
if(vec.size()==n)
{
write(vec);
vec.pop_back();
k--;
}
else
{
if(vec[k]<n)
{
vec[k]++;
k++;
}
else
{
vec.pop_back();
k--;
}
}
}

}
vec.clear();
}
}

int main(int argc, char *argv[])
{
int n;
cout<<"nr: ";
cin>>n;
generate_permutations(n);
return 0;
}
[/c0de]
the program not generate all permutation....this is a big problem :)
Zaita (2770)
Click edit. And use [code] not [c0de].
georgek (19)
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
 
#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;
bool valid(vector <int> v)
{
    bool val=true;
    for(int i=0; i<v.size(); i++)
        for(int k=i+1; k<v.size(); k++)
            if (v[i]==v[k]) val=false;
    return val;
}

void write (vector <int> v)
{
    for(int k=0; k<v.size(); k++)
        cout<<v[k]<<" ";
    cout<<endl;
}

void generate_permutations(int n)
{
    vector <int> vec;
    for(int i=1; i<=n; i++)
    {
        vec.push_back(i);
        int k=1;
        while(k>1)
        {
            vec.push_back(k);
            if(!valid(vec))
            {
                vec.pop_back(); k++;}
            else
            {
                if(vec.size()==n)
                {
                    write(vec);
                    vec.pop_back();
                    k--;
                }
                else
                {
                    if(vec[k]<n)
                    {
                        vec[k]++;
                        k++;
                    }
                    else
                    {
                        vec.pop_back();
                        k--;
                    }
                }
            }

        }
        vec.clear();
    }
}

int main(int argc, char *argv[])
{
    int n;
    cout<<"nr: ";
    cin>>n;
    generate_permutations(n);
    return 0;
}
Zaita (2770)
http://www.bearcave.com/random_hacks/permute.html

:) Thats a nicer, shorter implementation. Unfortunately, I can see a few issues in your algorithim that makes it impossible for it to generate them all.

E.g.
1
2
3
4
 
    vector <int> vec;
    for(int i=1; i<=n; i++)
    {
        vec.push_back(i);

You will push 1 number onto it, then you will run through your next k-loop with only 1 number in your vector. And you will do this until you have N numbers. But you shouldn't be running your K loop until you have N numbers, not upto N numbers.
georgek (19)
My restrioction for this problem is not use recursive function. If th proble is implement used a recursive function, then the code is very simpler.
georgek (19)
1
2
3
4
 
 
for(int i=1; i<=n; i++)
    {
        vec.push_back(i);

is to push the first number in a set of combinations. For a set a combinates i means like {(1,2,3), (1,3,2)}. Another set is {(2,1,3), (2,3,1)}. (for nr=3)
Zaita (2770)
The main issue with your method of generating them is that you are not storing any information between each set you generate.

So how do you know if you have done 213 or 231? That link I provided shows you a very simple way to generate all the permutations. The code is small and tidy. You can easily modify that to use a vector instead of a static array. It also shows you have to store static variables between runs to ensure you get every combination and don't generate the same combination twice.

Without storing information you are only going to be moving forward, and will miss some combinations. Which I suspect is what yours is doing?
georgek (19)
the informaton is storing in vec and in a k variable.
georgek (19)
the modification of vec.size() says in what direction you are moving
Zaita (2770)
1
2
 
int k = 1;
 while (k > 1) {


K will never be > 1.
georgek (19)
For this problem i try a similar code.
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
 
#include <iostream>
#include <vector>
using namespace std;
#include <conio.h>
bool valid(vector <int> v)
{
    bool val=true;
    for(int i=0; i<v.size(); i++)
        for(int k=i+1; k<v.size(); k++)
            if (v[i]==v[k]) val=false;
    return val;
}
void write (vector <int> v)
{
    for(int k=0; k<v.size(); k++)
        cout<<v[k]<<" ";
    cout<<endl;
}
void generate_permutation(int n)
{
    vector <int> vec;
    for (int i=1; i<=n; i++)
    {
        vec.push_back(i);
        for(int k=1; k<=n; k++)
        {
            vec.push_back(k);
            if(!valid(vec)) vec.pop_back();
            else
            {
                if(vec.size()==n)
                {
                    write(vec);
                    vec.pop_back();
                    int level=vec.size()-1;
                    bool val=true;
                    while(level!=0 && val)
                    if(vec[level]<n)
                    {
                        vec[level]++;
                        k=1;
                        val=false;
                    }
                    else
                    {
                        vec.pop_back();
                        level--;
                    }
                }
            }
        }
        vec.clear();
    }
}
int main(int argc, char *argv[])
{
    int n;
    cout<<"nr: ";
    cin>>n;
    generate_permutation(n);
    getch();
    return 0;
}


The result is incomplete solution. (this generate not all permutatios)
Zaita (2770)
Your problem here is:
1
2
3
4
 
        for(int k=1; k<=n; k++)
        {
            vec.push_back(k);
            if(!valid(vec)) vec.pop_back();

You are incrementing K from 1->N. So your algorithm is always moving forward. Thats why the 2nd number in your answer is always N+1 (where I!=N, others answer is 1). See what I mean?

georgek (19)
let say 
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
 
#include <iostream>
#include <vector>
using namespace std;
#include <conio.h>
bool valid(vector <int> v)
{
    bool val=true;
    for(int i=0; i<v.size(); i++)
        for(int k=i+1; k<v.size(); k++)
            if (v[i]==v[k]) val=false;
    return val;
}
void write (vector <int> v)
{
    for(int k=0; k<v.size(); k++)
        cout<<v[k]<<" ";
    cout<<endl;
}
void generate_permutation(int n)
{
    vector <int> vec;
    for (int i=1; i<=n; i++)

    {
        vec.push_back(i);
        int k=2;
        while(k>1)
        {
            vec.push_back(k);
            if(!valid(vec)) vec.pop_back();
            else
            {
                if(vec.size()==n)
                {
                    write(vec);
                    vec.pop_back();
                    int level=vec.size()-1;
                    bool val=true;
                    while(level!=0 && val)
                    if(vec[level]<n)
                    {
                        vec[level]++;
                        k++;
                        val=false;
                    }
                    else
                    {
                        vec.pop_back();
                        level--;
                    }
                }
            }
        }
        vec.clear();
    }
}
int main(int argc, char *argv[])
{
    int n;
    cout<<"nr: ";
    cin>>n;
    generate_permutation(n);
    getch();
    return 0;
}
georgek (19)
that moification is necesssary ...?
georgek (19)
that is better code to resolve this problem: first or last?
georgek (19)
any suggestion to change effectivly one of this two codes is help me a lot
Pages: 12