如何从多个List<MyObj>生成带Unique约束的对象组合？

需求是从多个List<MyObj>集合中生成每个集合取一个元素的组合，要求每个组合最多包含一个Unique=true的MyObj对象，避免先生成全量组合再过滤的低效方案。

核心思路 #

直接生成符合约束的组合，分两种场景处理：

• 场景1：组合无Unique=true元素：每个集合仅筛选出Unique=false的元素，计算这些子集的笛卡尔积。
• 场景2：组合恰好有一个Unique=true元素：遍历每个集合，针对当前集合筛选出Unique=true的元素，其余所有集合都筛选出Unique=false的元素，计算该组子集的笛卡尔积，最后将所有场景2的结果合并。

代码实现 #

首先定义MyObj类：

public class MyObj
{
    public int Value { get; set; }
    public bool Unique { get; set; }

    // 重写ToString方便查看结果
    public override string ToString()
    {
        return $"Value: {Value}, Unique: {Unique}";
    }
}

然后实现核心的组合生成逻辑，包括通用笛卡尔积方法和约束处理：

using System;
using System.Collections.Generic;
using System.Linq;

public class CombinationGenerator
{
    // 通用笛卡尔积计算方法
    private static IEnumerable<List<T>> CartesianProduct<T>(IEnumerable<IEnumerable<T>> sequences)
    {
        IEnumerable<List<T>> result = new List<List<T>> { new List<T>() };
        foreach (var sequence in sequences)
        {
            result = from seq in result
                     from item in sequence
                     select new List<T>(seq) { item };
        }
        return result;
    }

    // 生成符合约束的组合
    public static IEnumerable<List<MyObj>> GenerateValidCombinations(List<List<MyObj>> allLists)
    {
        var validCombinations = new List<List<MyObj>>();

        // 场景1：所有元素都是Unique=false
        var allNonUniqueSubsets = allLists.Select(list => list.Where(obj => !obj.Unique).ToList());
        // 检查是否每个子集都有元素（避免空集合导致笛卡尔积为空）
        if (allNonUniqueSubsets.All(subset => subset.Any()))
        {
            validCombinations.AddRange(CartesianProduct(allNonUniqueSubsets));
        }

        // 场景2：恰好一个元素是Unique=true，其余都是Unique=false
        for (int i = 0; i < allLists.Count; i++)
        {
            // 当前集合取Unique=true的元素
            var currentUniqueItems = allLists[i].Where(obj => obj.Unique).ToList();
            if (!currentUniqueItems.Any())
                continue; // 当前集合没有Unique=true的元素，跳过

            // 其他集合取Unique=false的元素
            var otherNonUniqueSubsets = new List<IEnumerable<MyObj>>();
            bool hasEmptySubset = false;
            for (int j = 0; j < allLists.Count; j++)
            {
                if (j == i)
                {
                    otherNonUniqueSubsets.Add(currentUniqueItems);
                }
                else
                {
                    var nonUniqueItems = allLists[j].Where(obj => !obj.Unique).ToList();
                    if (!nonUniqueItems.Any())
                    {
                        hasEmptySubset = true;
                        break;
                    }
                    otherNonUniqueSubsets.Add(nonUniqueItems);
                }
            }

            if (!hasEmptySubset)
            {
                validCombinations.AddRange(CartesianProduct(otherNonUniqueSubsets));
            }
        }

        return validCombinations;
    }
}

示例测试 #

用你提供的示例数据验证：

public class Program
{
    public static void Main()
    {
        // 初始化示例对象
        MyObj obj1 = new MyObj { Value = 1, Unique = false };
        MyObj obj2 = new MyObj { Value = 2, Unique = true };
        MyObj obj3 = new MyObj { Value = 3, Unique = true };
        MyObj obj4 = new MyObj { Value = 4, Unique = false };
        MyObj obj5 = new MyObj { Value = 5, Unique = false };
        MyObj obj6 = new MyObj { Value = 6, Unique = false };

        List<MyObj> objs12 = new List<MyObj> { obj1, obj2 };
        List<MyObj> objs34 = new List<MyObj> { obj3, obj4 };
        List<MyObj> objs56 = new List<MyObj> { obj5, obj6 };

        var allLists = new List<List<MyObj>> { objs12, objs34, objs56 };

        // 生成符合约束的组合
        var validCombos = CombinationGenerator.GenerateValidCombinations(allLists);

        // 输出结果
        foreach (var combo in validCombos)
        {
            Console.WriteLine("组合：");
            foreach (var obj in combo)
            {
                Console.WriteLine($"  {obj}");
            }
            Console.WriteLine("---");
        }
    }
}

输出结果说明 #

运行后会输出所有有效组合：

• 场景1的组合：[obj1, obj4, obj5]、[obj1, obj4, obj6]
• 场景2的组合：
  • 从第一个集合取Unique=true：[obj2, obj4, obj5]、[obj2, obj4, obj6]
  • 从第二个集合取Unique=true：[obj1, obj3, obj5]、[obj1, obj3, obj6]
• 第三个集合没有Unique=true的元素，所以该分支无结果

所有组合都满足最多一个Unique=true的约束，且没有生成任何无效组合，效率远高于全量生成再过滤的方式。

内容的提问来源于stack exchange，提问作者user12571241