来自给定集合的所有可能的组合，但不重复集合的内部元素

本文关键字：集合 元素 内部 有可能 组合 | 更新日期: 2024-09-24 07:22:34

我有一些固定的整数集，每个整数集中的distict值都在增加，例如：

{1, 2, 4}, {1, 3}, {2, 4}, {2, 7}, {3, 6}, {5, 6}, {3, 5, 7}.

是否有任何算法或更好的C#代码，从给定的集合生成所有可能的组合，但不重复其内部整数，即

[{1, 2, 4}, {3, 6}] < all integers are unique
[{1, 2, 4}, {3, 5, 7}] < all integers are unique
[{1, 3}, {2, 4}, {5, 6}] <– all integers are unique.

等等

========================================

以下是输入数据的可能组织：

        var set1 = new HashSet<int>() { 1, 2, 4 };
        var set2 = new HashSet<int>() { 1, 3 };
        var set3 = new HashSet<int>() { 2, 4 };
        var set4 = new HashSet<int>() { 2, 7 };
        var set5 = new HashSet<int>() { 3, 6 };
        var set6 = new HashSet<int>() { 5, 6 };
        var set7 = new HashSet<int>() { 3, 5, 7 };
        var inputList = new List<HashSet<int>>();
        inputList.Add(set1);
        inputList.Add(set2);
        inputList.Add(set3);
        inputList.Add(set4);
        inputList.Add(set5);
        inputList.Add(set6);
        inputList.Add(set7);

我需要从inputList中获得所有可能的集合列表（即组合）的列表（或集合），每个内部列表（组合）中都有唯一的整数。

此问题被标记为重复，并且已在此处找到答案："生成所有可能的组合（8个答案）"。然而，在我看来，这本质上是一个不同的问题：

  • 输入数据不是相同长度的两个数组，而是一个集合列表，每个集合中有不同数量的元素；

  • 相同的元素可以存在于不同的集合中。

来自给定集合的所有可能的组合，但不重复集合的内部元素

就我个人而言，我认为这是一个由两部分组成的问题：

  • 在提供给您的号码列表中查找唯一的号码。要在C#中做到这一点，你可以使用hashset，也可以使用linq（我认为你想要它，因为你用linq标记了它）
  • 形成这些数字的所有可能组合。这里已经回答了：从数字列表中获取所有可能的组合

编辑/更正

因此，深入研究这个问题，这里的目标是找到SETS的组合，而不是这些集合中的单个数字（正如我在上面最初指出的）。考虑到这一点，我会做以下事情：

  • 创建一个正方形的二维布尔数组。每个布尔值表示该索引处的集合是否与其他索引处的集冲突。先填这个
  • 使用标准组合数学（与上面提到的相同），但与布尔值列表的检查相结合以丢弃无效结果

我相信这确实应该奏效。我（可能）马上在这里创建一个例子！

代码

重要提示：这在任何意义上都不漂亮或优化，但它确实有效，它确实说明了解决这个问题的方法。一个简单的优化是将布尔数组传递到递归步骤中，在递归步骤中生成组合，并在生成冲突后立即停止递归。这将节省大量的时间和计算能力。话虽如此，我将把它留给读者练习。

只需将以下内容粘贴到一个新的控制台应用程序中，它就可以工作了。祝你好运！

    static void Main(string[] args)
    {
        // create/read sets here
        var integers = new List<int[]>(){new []{1,2,4}, new []{1,3}, new []{2, 4}, new []{2, 7}, new []{3, 6}, new []{5, 6}, new []{2, 5, 7}};
        // allocate/populate booleans - loop may be able to be refined
        var conflicts = new bool[integers.Count, integers.Count];
        for (var idx = 0; idx < integers.Count; idx++)
            for (var cmpIdx = 0; cmpIdx < integers.Count; cmpIdx++)
                conflicts[idx, cmpIdx] = integers[idx].Any(x => integers[cmpIdx].Contains(x));
        // find combinations (index combinations)
        var combinations = GetCombinations(integers.Count);
        // remove invalid entries
        for (var idx = 0; idx < combinations.Count; idx++)
            if (HasConflict(combinations[idx], conflicts))
                combinations.RemoveAt(idx--);
        // print out the final result
        foreach (var combination in combinations) PrintCombination(combination, integers);
        // pause
        Console.ReadKey();
    }

    // get all combinatins
    static List<Combination> GetCombinations(int TotalLists)
    {
        var result = new List<Combination>();
        for (var combinationCount = 1; combinationCount <= TotalLists; combinationCount++)
            result.AddRange(GetCombinations(TotalLists, combinationCount));
        return result;
    }
    static List<Combination> GetCombinations(int TotalLists, int combinationCount)
    {
        return GetCombinations(TotalLists, combinationCount, 0, new List<int>());
    }
    // recursive combinatorics - loads of alternatives including linq cartesian coordinates
    static List<Combination> GetCombinations(int TotalLists, int combinationCount, int minimumStart, List<int> currentList)
    {
        // stops endless recursion - forms final result
        var result = new List<Combination>();
        if (combinationCount <= 0)
        {
            if ((currentList ?? new List<int>()).Count > 0)
            {
                result.Add(new Combination() { sets = currentList });
                return result;
            }
            return null;
        }
        for (var idx = minimumStart; idx <= TotalLists - combinationCount; idx++)
        {
            var nextList = new List<int>();
            nextList.AddRange(currentList);
            nextList.Add(idx);
            var combinations = GetCombinations(TotalLists, combinationCount - 1, idx + 1, nextList);
            if (combinations != null) result.AddRange(combinations);
        }
        return result;
    }
    // print the combination
    static void PrintCombination(Combination value, List<int[]> sets)
    {
        StringBuilder serializedSets = new StringBuilder();
        foreach (var idx in value.sets)
        {
            if (serializedSets.Length > 0) serializedSets.Append(", ");
            else serializedSets.Append("{");
            serializedSets.Append("{");
            for (var setIdx = 0; setIdx < sets[idx].Length; setIdx++)
            {
                if (setIdx > 0) serializedSets.Append(", ");
                serializedSets.Append(sets[idx][setIdx].ToString());
            }
            serializedSets.Append("}");
        }
        serializedSets.Append("}");
        Console.WriteLine(serializedSets.ToString());
    }
    static bool HasConflict(Combination value, bool[,] conflicts)
    {
        for (var idx = 0; idx < value.sets.Count; idx++)
            for (var cmpIdx = idx + 1; cmpIdx < value.sets.Count; cmpIdx++)
                if (conflicts[value.sets[idx], value.sets[cmpIdx]]) return true;
        return false;
    }
    // internal class to manage combinations
    class Combination { public List<int> sets; }
相关文章：