## Combinations

Let's talk about algorithms!

Moderator: Board moderators

leocm
New poster
Posts: 22
Joined: Fri Jul 21, 2006 9:44 am
Location: Brasil

### Combinations

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.

jan_holmes
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;
}
``````

leocm
New poster
Posts: 22
Joined: Fri Jul 21, 2006 9:44 am
Location: Brasil
jan_holmes wrote:for small n, you can use next_permutation() in C++
Thank you Jan, but I would like an algorithm to implement in any language and with any n, (n large).

Somebody knows?

asif_rahman0
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;
}
``````
hope this will help!!!:)

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
http://www.cut-the-knot.org/do_you_know/AllPerm.shtml

btw, those are permutations (order matters), not combinations (where order does not matter)

leocm
New poster
Posts: 22
Joined: Fri Jul 21, 2006 9:44 am
Location: Brasil
Thanks for the replies.

Moheeb
New poster
Posts: 21
Joined: Fri May 05, 2006 9:08 am
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!

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm