c# - 不同组按特定顺序的组合

Question

我有一个参数列表，每个参数都接受特定范围的输入。我正在创建一个测试，以创建所有可能的有效输入。此外，每个组都是可选的(可以完全跳过)，因此组合长度不一定必须与列表的长度相同。

输入

List<string[]> temp = new List<string[]>
{
    // The order of these groups is important
    new string[] { "a", "b", "c" },
    new string[] { "d", "e" },
    new string[] { "f", "g", "h" }
};

约束

1. 每组 0 或 1 个项目(上面的 string[])
2. 订单List<T>必须保留

有效组合

1. a, e, f
2. a, d, g
3. c, e, f
4. b, g
5. c, f

无效组合

1. a, b, f ( a 和 b 来自同一组 - 不允许)
2. a, f, d (顺序错误 - d 必须位于 f 之前)

到目前为止，我已返回我的库，其中有 Combinations LINQ 方法。

public static class IEnumerableExtensions
{
    // Can be used to get all permutations at a certain level
    // Source: http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n#1898744
    public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
    {
        return k == 0 ? new[] { new T[0] } :
          elements.SelectMany((e, i) =>
            elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] { e }).Concat(c)));
    }
}

过去我只在单个序列上使用它来执行类似 generate every permutation of URL segments 的操作。但我在嵌套列表上使用它时遇到了困难，该列表具有每组一个和特定顺序的限制。

我知道我可以通过执行 3 个嵌套循环并使用列表来跟踪已使用的项目来解决这个特定的难题，但我事先不知道 List<T> 中有多少项目。 ，所以这在一般情况下不起作用。

如何获得上述输入的所有有效组合？

I would prefer LINQ, but will accept any solution that solves this problem.

Answer 1

使用一些扩展函数，

public static IEnumerable<T> Prepend<T>(this IEnumerable<T> rest, params T[] first) => first.Concat(rest);
public static IEnumerable<T> AsSingleton<T>(this T source) {
    yield return source;
}

你可以写

public static IEnumerable<IEnumerable<T>> ParametersWithEmpty<T>(this IEnumerable<IEnumerable<T>> ParmLists) {
    if (ParmLists.Count() == 0)
        yield break; // empty
    else {
        var rest = ParametersWithEmpty(ParmLists.Skip(1));
        foreach (var p in ParmLists.First()) {
            yield return p.AsSingleton(); // p.Concat(empty)
            foreach (var r in rest)
                yield return r.Prepend(p); // p.Concat(r)
        }
        foreach (var r in rest)
            yield return r; // empty.Concat(r)
    }
}

你可以这样调用它:

var ans = temp.ParametersWithEmpty();

要在结果中包含所有级别，您必须跳过上述代码中隐含的空情况:

public static IEnumerable<IEnumerable<T>> Parameters<T>(this IEnumerable<IEnumerable<T>> ParmLists) {
    if (ParmLists.Count() == 1)
        foreach (var p in ParmLists.First())
            yield return p.AsSingleton();
    else {
        var rest = Parameters(ParmLists.Skip(1));
        foreach (var p in ParmLists.First()) {
            foreach (var r in rest)
                yield return r.Prepend(p);
        }
    }
}

最后，这是一个替代版本，它可能会使其更加清晰，因为它输出序列，就好像每个参数列表前面都有空一样，但也会返回答案中的所有空序列。

public static IEnumerable<IEnumerable<T>> ParametersWithEmpty2<T>(this IEnumerable<IEnumerable<T>> ParmLists) {
    if (ParmLists.Count() == 0)
        yield return Enumerable.Empty<T>();
    else {
        var rest = ParametersWithEmpty2(ParmLists.Skip(1));
        foreach (var r in rest)
            yield return r; // empty.Concat(r)
        foreach (var p in ParmLists.First()) {
            foreach (var r in rest)
                yield return r.Prepend(p); // p.Concat(r)
        }
    }
}