独特组合的算法

Question

我一直在尝试寻找一种方法，从嵌套在容器中的对象列表中获取唯一组合的列表。同一组中的对象不能合并。对象在所有组中都是唯一的

例子:

Group 1: (1,2)
Group 2: (3,4)

结果

1
2
3
4
1,3
1,4
2,3
2,4

如果我们像这样添加另一个组:

Group 1: (1,2)
Group 2: (3,4)
Group 3: (5,6,7)

结果是

1
2
3
4
5
6
7
1,3
1,4
1,5
1,6
1,7
2,3
2,4
2,5
2,6
2,7
3,5
3,6
3,7
4,5
4,6
4,7
1,3,5
1,3,6
1,3,7
1,4,5
1,4,6
1,4,7
2,3,5
2,3,6
2,3,7
2,4,5
2,4,6
2,4,7

我可能错过了上面的组合，但提到的组合应该足够指示了。

我有可能最多有 7 个组，每个对象有 20 个组。

我试图避免让代码知道它正在执行双倍、三倍、四倍等的组合，但我在这个过程中遇到了很多逻辑颠簸。

需要说明的是，我不是要代码，更多的是要方法、伪代码或指示会很好​​。

更新这是我看到这两个答案后的结果。

来自@Servy 的回答:

public static IEnumerable<IEnumerable<T>> GetCombinations<T>(this IEnumerable<IEnumerable<T>> sequences)
    {
        var defaultArray = new[] { default(T) };

        return sequences.Select(sequence =>
                sequence.Select(item => item).Concat(defaultArray))
            .CartesianProduct()
            .Select(sequence =>
                sequence.Where(item => !item.Equals(default(T)))
                .Select(item => item));
    }

    public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences)
    {
        IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() };
        return sequences.Aggregate(
            emptyProduct,
            (accumulator, sequence) =>
                from accseq in accumulator
                from item in sequence
                select accseq.Concat(new[] { item })
            );
    }

来自@AK_的回答

public static IEnumerable<IEnumerable<T>> GetCombinations<T>(this IEnumerable<IEnumerable<T>> groups)
    {

        if (groups.Count() == 0)
        {
            yield return new T[0];
        }

        if (groups.Count() == 1)
        {
            foreach (var t in groups.First())
            {
                yield return new T[] { t };
            }
        }

        else
        {
            var furtherResult = GetCombinations(groups.Where(x => x != groups.Last()));

            foreach (var result in furtherResult)
            {
                yield return result;
            }

            foreach (var t in groups.Last())
            {
                yield return new T[] { t };

                foreach (var result in furtherResult)
                {
                    yield return result.Concat(new T[] { t });
                }
            }
        }
    }

两者的用法

List<List<int>> groups = new List<List<int>>();

        groups.Add(new List<int>() { 1, 2 });
        groups.Add(new List<int>() { 3, 4, 5 });
        groups.Add(new List<int>() { 6, 7 });
        groups.Add(new List<int>() { 8, 9 });
        groups.Add(new List<int>() { 10, 11 });


        var x = groups.GetCombinations().Where(g => g.Count() > 0).ToList().OrderBy(y => y.Count());

什么是最佳解决方案？老实说，我能够更轻松地阅读@AK_ 的解决方案发生了什么(必须寻找有关如何获得笛卡尔积的解决方案)。

Answer 1

所以首先考虑 N 个序列的笛卡尔积问题。也就是说，每个序列中一个值的每个组合。 Here is a example of an implementation of that problem, with an amazing explanation .

但是我们如何处理输出组合的大小小于序列数的情况呢？仅处理给定序列的大小与序列数相同的情况。好吧，想象一下每个输入序列都有一个“空”值。该空值与来自其他序列(包括所有它们的 空值)的每个值组合配对。然后我们可以在最后删除这些空值，瞧，我们拥有每种尺寸的每种组合。

为此，在仍然允许输入序列实际使用 C# 文字 null 值或该类型的默认值(如果它不可为空)的同时，我们需要包装该类型.我们将创建一个包装真实值的包装器，同时还拥有它自己的默认/空值定义。从那里我们将每个序列映射到一系列包装器中，将实际默认值附加到末尾，计算笛卡尔积，然后将组合映射回“真实”值，过滤掉默认值

如果你不想看到实际的代码，请停止阅读这里。

---

public class Wrapper<T>
{
    public Wrapper(T value) { Value = value; }
    public static Wrapper<T> Default = new Wrapper<T>(default(T));
    public T Value { get; private set; }
}

public static IEnumerable<IEnumerable<T>> Foo<T>
    (this IEnumerable<IEnumerable<T>> sequences)
{
    return sequences.Select(sequence =>
            sequence.Select(item => new Wrapper<T>(item))
            .Concat(new[] { Wrapper<T>.Default }))
        .CartesianProduct()
        .Select(sequence => 
            sequence.Where(wrapper => wrapper != Wrapper<T>.Default)
            .Select(wrapper => wrapper.Value));
}