How do I create groups of combinations that match specific conditions in C#?

Question

I have a list of people List<Person> who I need to produce groups of combinations according to a couple of conditions. This may be easiest explained with an example. Let's say I have N = 19 people.

List<Person> people = new List<Person>(){A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S};

I am given as input a PreferredGroupSize. In this case, PreferredGroupSize = 5;.

I need as output combinations grouped by this PreferredGroupSize and +/-1 for remaining members lastGroupSizes. For 19, I need all combinations of people with 3 groups of size 5 and a single group of size 4.

Using some modulus operations, I have already calculated the number of groups I need numGroups, as well as how many numNormalSizeGroups (i.e., number of PreferredGroupSize groups) and how many numOddSizeGroups.

This is calculated as follows:

//if(mod > (PreferredGroupSize)/2.0f)) make small groups.
//else make large groups.

float val1 = N % PreferredGroupSize;
float val2 = PreferredGroupSize / 2.0f;
if (N % PreferredGroupSize == 0)
{
   lastGroupSizes = PreferredGroupSize;
   numOddSizeGroups = 0;
   numNormalSizeGroups = N / PreferredGroupSize;
}
else if (val1 > val2)
{
   lastGroupSizes = PreferredGroupSize - 1;
   numOddSizeGroups = PreferredGroupSize - N % PreferredGroupSize;
   numGroups = (int)MathF.Ceiling(((float)N) / PreferredGroupSize);
   numNormalSizeGroups = numGroups - numOddSizeGroups;
}
else
{
   lastGroupSizes = PreferredGroupSize + 1;
   numOddSizeGroups = N % PreferredGroupSize;
   numGroups = (int)MathF.Floor(N / PreferredGroupSize);
   numNormalSizeGroups = numGroups - numOddSizeGroups;
}

The issue I'm having is I do not know how to combine the groups to form valid combinations. Valid combinations should contain no duplicate members, the number of groups should be numGroups, and the total members should be N.

These will later be added to something like a Dictionary<List<Person>, float> Groups

So, for example, this would be a valid combination:

[A B C D E], 0.55
[F G H I J], 0.72
[K L M N O], 0.74
[P Q R S], 0.75

Each row is a List<Person>, followed by a float Score that represents the compatibility of the group. Higher is better. The floats aren't so important. What is important is that only valid combinations should be created.

This would be an invalid combination due to a repeated member:

[A B C D E], 0.55
[F B H I J], 0.77
[K L M N O], 0.74
[P Q R S], 0.75

This would be an invalid combination due to the wrong total number of people in the groups:

[A B C D], 0.63
[F G H I J], 0.72
[K L M N O], 0.74
[P Q R S], 0.75

If either condition is violated, it should be not be added to the list of valid groups.

Right now, I do the following:

1. Produce all combinations of people of size PreferredGroupSize. nCr = 19 choose 5

2. Produce all combinations of people of size lastGroupSizes. nCr = 19 choose 4

3. Calculate a group Score for all combinations produced by 1 and 2 and add the combinations and Score to the Groups Dictionary.

4. Produce all combinations of Groups of size numGroups.

   This is where the major complexity comes into play, and why I want to avoid producing invalid groups:

   nCr = ((19 choose 5) + (19 choose 4)) choose numGroups

5. Iterate over those using a foreach loop, looking for valid groups, adding only valid groups to a List<Person> ValidGroups.

6. Break out of the loop after a given M groups have been calculated. I have sorted Groups by the Score so that higher scoring groups are more likely to be found first.

7. Process the valid groups.

I skip Step 1 if numNormalSizeGroups is 0, and I skip Step 2 if numOddSizeGroups is 0.

There are a ton of invalid groups created this way, and the nCr is very large. I believe there should be a better way to do this, but I have not yet found a way. Perhaps sharing how combinations are created may be helpful in assisting:

        //make combinations of a certain length
        public static IEnumerable<IEnumerable<T>> GetCombinations<T>(IEnumerable<T> items, int count)
        {
            int i = 0;
            foreach (var item in items)
            {
                if (count == 1)
                    yield return new T[] { item };
                else
                {
                    foreach (var result in GetCombinations(items.Skip(i + 1), count - 1))
                        yield return new T[] { item }.Concat(result);
                }

                ++i;
            }
        }

I attribute this code to here: Unique combinations of list

At the source, the code is listed as creating permutations instead of combinations. I have run this on many lists, and it produces combinations.

I'll also run through a somewhat minimal version of the current algorithm a bit with code:

//1. Produce all combinations of people of size PreferredGroupSize.
//2. Produce all combinations of people of size lastGroupSizes.
//Skip Step 1 if numNormalSizeGroups is 0
//Skip Step 2 if numOddSizeGroups is 0
bool calculatedNormal = false;
bool calculatedOdd = false;
while(!calculatedNormal || !calculatedOdd)
{
   int gSize = 0;
   if(!calculatedNormal)
   {
      calculatedNormal = true;
      if(numNormalSizeGroups>0)
         gSize = PreferredGroupSize;
      else
         continue;
   }
   else if(!calculatedOdd)
   {
      calculatedOdd = true;
      if(numOddSizeGroups>0)
         gSize = lastGroupSizes;
      else
         break;
   }

   //Calculate a group Score for all combinations produced by 1 and 2.
   //Add the combinations and Score to the Groups Dictionary.
   var combos = GetCombinations(people, gSize);
   float groupScore = 0;
   List<Person> curGroup;

   //for purposes of this example, generate pseudorandom float:
   Random rand = new Random();

   foreach(var combo in combos)
   {
        //groupScore = CalculateGroupScore(combo);
        groupScore = (float)rand.NextDouble();

        curGroup = new List<Person>();
        foreach(Person person in combo)
            curGroup.Add(person);
        Groups.Add(curGroup, groupScore);
   }
}

//I have sorted Groups by the Score
//so that higher scoring groups are more 
//likely to be found first.
Groups = Groups.OrderByDescending(x => x.Value).ToDictionary(x => x.Key, x => x.Value);

//4. Produce all combinations of Groups of size numGroups.
var AllGroupCombos = GetCombinations(Groups, numGroups);

int M = 10000;
List<Person> gList = new List<Person>();
List<Person> ValidGroups = new List<Person>();
int curPeopleInGroup = 0;
bool addGroup = true;


//5. Iterate over those using a foreach loop
foreach(var combo in AllGroupCombos)
{
    curPeopleInGroup = 0;
    addGroup = true;
    gList.Clear();

    //Look for valid groups
    foreach(KeyValuePair<List<Person>, float> keyValuePair in combo)
    {
        foreach(Person person in keyValuePair.Key)
        {
            if(!gList.Contains(person)
            {
               gList.Add(person);
               ++curPeopleInGroup;
            }
            else
            {
               addGroup = false;
               break;
            }
        }
        if(!addGroup)
            break;
    }
    //Add only valid groups to a List<Person> ValidGroups.
    if(!addGroup || curPeopleInGroup != N)
        continue;
    var comboList = combo.ToList();
    ValidGroups.Add(comboList);
    
    //6. Break out of the loop after a given M 
    //groups have been calculated. 
    if(ValidGroups.Count() >= M)
       break;
}

I hope this was helpful, and that someone will be able to assist. :)