Combinations

Let's talk about algorithms!

Moderator: Board moderators

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

Combinations

Post by 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
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by 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
New poster
Posts: 22
Joined: Fri Jul 21, 2006 9:44 am
Location: Brasil

Post by leocm »

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

Post by 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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by 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
New poster
Posts: 22
Joined: Fri Jul 21, 2006 9:44 am
Location: Brasil

Post by leocm »

Thanks for the replies.

Moheeb
New poster
Posts: 21
Joined: Fri May 05, 2006 9:08 am
Location: Dhaka ,Bangladesh

Post by 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
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

Post by bugzpodder »

google SEPA

Post Reply

Return to “Algorithms”