Somebody could show me a algorithm whose generate, for example, the sequence:
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0
This is a example for a input with n = 3.
For n = 4, we have the sequence:
0 1 2 3
0 1 3 2
0 2 1 3
0 2 3 1
0 3 1 2
0 3 2 1
1 0 2 3
1 0 3 2
...
...
3 0 1 2
3 0 2 1
3 1 0 2
3 1 2 0
3 2 0 1
3 2 1 0
That is, I need a algorithm that generate all the n! possibles combinations of n numbers, without repeat anyone in each line.
Forgive me for my poor english...
Thank you,
Leonardo.
Combinations
Moderator: Board moderators
-
- Experienced poster
- Posts: 136
- Joined: Fri Apr 15, 2005 3:47 pm
- Location: Singapore
- Contact:
for small n, you can use next_permutation() in C++
Code: Select all
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int main () {
vector<int> v;
for (int i=0;i<3;i++) v.push_back(i);
sort(v.begin(),v.end());
for (int i=0;i<3;i++) printf("%d ",v[i]);
printf("\n");
while (next_permutation(v.begin(),v.end())) {
for (int i=0;i<3;i++) {
printf("%d ",v[i]);
}
printf("\n");
}
return 0;
}
-
- Experienced poster
- Posts: 209
- Joined: Sun Jan 16, 2005 6:22 pm
Code: Select all
#include <iostream>
#include <algorithm>
using namespace std;
int n,array[100];
void recur(int a,int len)
{
int i;
if(len==a){
for(i=0;i<len;i++) printf("%d ",array[i]);
printf("\n");
return;
}
for(i=a;i<len;i++){
swap(array[i],array[a]);
recur(a+1,len);
swap(array[i],array[a]);
}
}
int main()
{
int i;
cin>>n;
for(i=0;i<n;i++) cin>>array[i];
recur(0,n);
return 0;
}
http://www.cut-the-knot.org/do_you_know/AllPerm.shtml
btw, those are permutations (order matters), not combinations (where order does not matter)
btw, those are permutations (order matters), not combinations (where order does not matter)
go to Donald E. Knuth homepage:
http://www-cs-faculty.stanford.edu/~knuth/news04.html
look at Pre-Fascicle2b: Generating all permutations
u will get more than what u need .
Happy hacking!
http://www-cs-faculty.stanford.edu/~knuth/news04.html
look at Pre-Fascicle2b: Generating all permutations
u will get more than what u need .
Happy hacking!