Combinations

[leocm]

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]

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]

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]

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]

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]

Thanks for the replies.

[Moheeb]

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]

google SEPA