Skip to main content
gamedev.net
🔒 Locked

Combinations.

Started by Modena_au 3 replies 1.1k views
Original Post
Modena_au
Modena_au
Hey all. I was hoping some one could help me out with a problem with combinations. What I''m trying to do is to generate a complete list of combinations from a given set. Say I have a set of 52, with a grouping of 5. I know I will be just shy of 2.6 million combinations. Calculating that number isn''t the problem, it''s getting all those unique results. What I''m doing right now, is to generate all 5 numbers, starting with 1,2,3,4,5 and checking for duplicates, I order the numbers highest to lowest, I then search a linked list to see if I''ve seen that combination before, and if not, I add it to my linked list. If I have seen it, I increment my set of numbers to 1,2,3,4,6 and so on. Is there a faster way to do this? When testing it takes multiple hours to generate this. Also, the group size is variant, so I can''t use nested for loops.
Brother Bob
Brother Bob
Dont know if i understood your problem. You want to know all possible combinations you can take 5 numbers out of 52 so that no 5 numbers in each combination are the same, and no two combination have the same 5 number altough in different order. So [1, 1, 2, 3, 4] is invalid because there are two 1:s, and [1, 2, 3, 4, 5] and [2, 1, 3, 4, 5] should be counted as the same. Is that right?

Here's a program that generates all such possible combinations. I hope so at least, tried it and it looks correct.

        
#include <fstream>
#include <iterator>

using namespace std;

const int max_set   = 6;
const int min_set   = 1;
const int num_elems = 3;

void foo(ostream &os, int *l, int pos, int start, int end)
{
	if(pos == num_elems)
	{
		copy(l, l+num_elems, ostream_iterator<int>(os, " "));
		os << endl;
	}
	else
	{
		for(int i = start+1; i < end; ++i)
		{
			l[pos] = i;
			foo(os, l, pos + 1, i, max_set);
		}
	}
}

int main(int argc, char **argv)
{
	ofstream os;
	os.open("foo.txt");

	int combination[num_elems];
	foo(os, combination, 0, min_set, max_set);

	os.close();
}

It will write them to a file, but beware, the file is huge (I stopped the program at ~30 MB, and it was far from done).

edit: The program as it is written now will not create a huge file, but if you use the data in your original post, 52 numbers, 5 in each combination, it will be.

It will pick numbers in the range [min_set, max_set), from min_set to one less than max_set. num_elems is the number of numbers in each combination.


[edited by - Brother Bob on May 15, 2003 10:31:18 AM]
rypyr
rypyr
Brother:

You''re logic was sound, but the limits were slightly off (min_set and max_set were excluded from your set):


  
void foo(ostream& os, int* l, int pos, int start, int end) {
  if(pos == num_elems) {
    copy(l, l+num_elems, ostream_iterator<int>(os, " ");
    os << endl;
  }
  else {
    for(int i = start; i <= end; ++i) {
      l[pos] = i;
      foo(os, l, pos+1, i+1, end);
    }
  }
}

void main() {
  int list_of_combos[num_elems];
  foo(cout, list_of_combos, 0, min_set, max_set);
}
[ My Blog | My Blog]
Burning_Ice
Burning_Ice
i whipped something up (before i read Brother Bob's post)that seems to work (and calcs the combinations with 52 - 6 in less then a second ), so i'm just gonna post it 


    

#include <stdio.h>

void generate ( int m, int n )
{
	int i = 0;
	int index = n-1;
	int* comb = new int[n];

	for ( i = 0; i < n; i++ )
		comb[i] = i+1;

	while ( 1 )
	{
		for ( int k = 0; k < n; k++ )
			printf ( "%i", comb[k] );
		printf ( "\n" );
	
		while ( comb[index] >= m - (n-index-1) )
			index--;

		if ( index == -1 )
			return;

		comb[index]++;

		for ( int j = index+1; j < n; j++ )
			comb[j] = comb[index]+(j-index);
		index = n-1;			
	}
}

int main ()
{
	int maxnum = 7;     // elements in set

	int number = 5;     // grouping


	generate ( maxnum, number );

	return 0;
}


it just prints all combinations to screen right now

Edit: made it a bit shorter




[edited by - burning_ice on May 15, 2003 11:14:22 AM]
Brother Bob
Brother Bob
quote:
Original post by rypyr
Brother:

You''re logic was sound, but the limits were slightly off (min_set and max_set were excluded from your set):
...

min_set was missing, that is correct, and I missed it, thanks for correcting me on that one. It was included, but a late change to the code excluded it and I didn''t see it. max_set was intentionally excluded from the set, and I even said it in my post that it was, but you posted a way to fix that aswell if one wants to include it. Anyways, thanks for pointing it out.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.