唯一组合算法

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个序列的笛卡尔积问题。也就是说，每个序列中一个值的每一个组合。下面是该问题的一个实现示例，并给出了令人惊奇的解释。

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

要做到这一点，同时仍然允许输入序列实际使用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));
}

Answer 2

In c#

这实际上是一个单子…我认为…

IEnumerable<IEnumerable<int>> foo (IEnumerable<IEnumerable<int>> groups)
{
    if (groups.Count == 0)
    {
        return new List<List<int>>();
    }
    if (groups.Count == 1)
    {
        foreach(van num in groups.First())
        {
            return yield new List<int>(){num};
        }
    }
    else
    {
        var furtherResult = foo(groups.Where(x=> x != groups.First()));
        foreach (var result in furtherResult)
        {
            yield  return result;
        }
        foreach(van num in groups.First())
        {
            yield return new List<int>(){num};
            foreach (var result in furtherResult)
            {
                yield return result.Concat(num);
            }
        }
    }
}

---

更好的版本:

public static IEnumerable<IEnumerable<T>> foo<T> (IEnumerable<IEnumerable<T>> groups)
    {
        if (groups.Count() == 0)
        {
            return new List<List<T>>();
        }
        else
        {
            var firstGroup = groups.First();
            var furtherResult = foo(groups.Skip(1));
            IEnumerable<IEnumerable<T>> myResult =  from x in firstGroup
                select new [] {x};
            myResult = myResult.Concat(  from x      in firstGroup 
                                       from result in furtherResult
                                       select result.Concat(new T[]{x}));
            myResult = myResult.Concat(furtherResult);
            return myResult;
        }
    }