如何在 C# 中创建匹配特定条件的组合组？

问题描述 投票：0回答：1

我有一个人员名单

List<Person>
，我需要他们根据几个条件产生组合组。通过一个例子可能最容易解释这一点。假设我有 
N = 19
人。

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};

我的输入是a 

PreferredGroupSize
。在这种情况下，
PreferredGroupSize = 5;
。

我需要按此 

PreferredGroupSize
和 +/-1 为剩余成员 
lastGroupSizes
分组的输出组合。 对于 19，我需要 
people
的所有组合，其中包括 3 组 5 号尺寸和一组 4 号尺寸。

使用一些模运算，我已经计算出了我需要的组数

numGroups
，以及多少个
numNormalSizeGroups
（即
PreferredGroupSize
组的数量）和多少个
numOddSizeGroups
。

计算如下：

//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;
}

我遇到的问题是我不知道如何将各组组合起来形成有效的组合。有效组合不应包含重复的成员，组数应为 

numGroups
，成员总数应为 
N
。

这些稍后将添加到诸如

Dictionary<List<Person>, float> Groups

之类的内容中

因此，例如，这将是一个有效的组合：

[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

每一行都是一个 

List<Person>
，后面跟着一个 
float Score
，代表该组的兼容性。越高越好。浮标没那么重要。重要的是只应创建有效的组合。

由于重复的成员，这将是无效的组合：

[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

由于组中总人数错误，这将是无效组合：

[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

如果违反任一条件，则不应将其添加到有效组列表中。

现在，我做以下事情：

  1. 产生尺寸为

    people
    的
    PreferredGroupSize
    的所有组合。 
    nCr = 19 choose 5

  2. 产生尺寸为

    people
    的
    lastGroupSizes
    的所有组合。 
    nCr = 19 choose 4

  3. 计算 1 和 2 产生的所有组合的组 

    Score
    ，并将组合和 
    Score
    添加到 
    Groups
    字典中。

  4. 产生尺寸为

    Groups
    的
    numGroups
    的所有组合。

    这就是主要复杂性发挥作用的地方，也是为什么我想避免产生无效组：

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

  5. 使用 

    foreach
    循环迭代那些，查找有效组，仅将有效组添加到 
    List<Person> ValidGroups
    。

    6. 计算出给定的
  6. M

    组后，跳出循环。我已按 

    Groups
    对 
    Score
    进行排序，以便更有可能首先找到得分较高的组。
    

    7. 处理有效组。
  7. 

    

    

    8. 如果 
numNormalSizeGroups
 为 0，我会跳过步骤 1；如果 
numOddSizeGroups
 为 0，我会跳过步骤 2。
通过这种方式创建了大量无效组，并且 nCr 非常大。
我相信应该有更好的方法来做到这一点，但我还没有找到方法。也许分享如何创建组合可能会有所帮助：


        //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;
            }
        }



我将此代码归因于这里：
列表的独特组合

在源代码中，代码被列为创建排列而不是组合。我已经在很多列表上运行过这个，它会产生组合。


我还将用代码运行一下当前算法的最小版本：


//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;
}



我希望这对您有所帮助，并且有人能够提供帮助。 :)

    





    
    c#
    
    algorithm
    
    linq
    
    combinations
    
    
1个回答

    

      
      
      

        

          

            

              
0
投票

              
            

          

        

        




创建一个与人员长度相同的列表，但为每个人分配组索引。从“初始”顺序开始 - 重复每个索引与给定组中的成员一样多的次数，考虑到某些组会更小。在您的情况下，您将有 5 个零、5 个一、5 个二和 4 个三：
    {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3}
  1. 。
    上面索引列表的每个排列都有一个唯一的有效组分配 - 将每个人分配给给定位置的组索引
    2. 

  2. 从第 1 点开始迭代列表的所有排列。您必须在 C++ 中实现类似 
    3. next_permutation
  3.  的东西。 
    这里
    是另一个 SoF 用户在另一个问题中的示例实现。


    4. 执行这些步骤，您将能够迭代所有有效的组合。

    



      

      
    

  

  

    
最新问题


  





  

    © www.soinside.com 2019 - 2024. All rights reserved.