Unique sets of groups from all possible combinations

The problem I've been presented with needs me to compute the total number of combinations given n students and k students per group which can be done fairly easy with recursion. Plus there are solutions on the COS "Combinational Object Server". However, the hard part of my problem is taking the combinations and sorting them so that there are sets of groups where each set utilizes ever student. I've included the recursive code for generating the combinations but I'm at a loss at how to sort through the list any further to get the unique sets of groups.

(Really Easy Example:)
Given n=6 and k=2 the number of different combinations
equals (n!)/((k!)(n-k)!)=15.

The combinations are: 000011 which is the positions {2,1}.
000101 {3,1}
000110 {3,2}
001001 {4,1}
001010 {4,2}
001100 {4,3}
010001 {5,1}
010010 {5,2}
010100 {5,3)
011000 {5,4}
100001 {6,1}
100010 {6,2}
100100 {6,3}
101000 {6,4}
110000 {6,5}

And the unique sets of groups are:
000011 000101 001001 010001 100001
001100 011000 010010 000110 001010
110000 100010 100100 101000 010100

[code]
#include
#include
using namespace std;

ofstream saveFile;
int n, k;
int myArray[0];

void uniqueGroup(int j,int m)
{
if(j>n)
{
for(int i=1; i<=n ;i++)
{
saveFile << myArray[i];
}
saveFile << endl;
}//end if
else
{
if((k-m)<(n-j+1))
{
myArray[j]=0;
uniqueGroup(j+1,m);
}
if(m<k)
{
myArray[j]=1;
uniqueGroup(j+1,m+1);
}
}//end else
}//end uniqueGroup

int main()
{
cout << "Enter number of students: ";
cin >> n;
cout << endl << "Enter number of students per group: ";
cin >> k;
saveFile.open("combinations.txt");
uniqueGroup(1,0);
saveFile.close();

char ch;
cin >> ch;
return 0;
}//end main
[/code]

Comments

  • I think this problem is similar to the social goffers problem or latin squares.

Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

In this Discussion