在Linq(C#)中将多个不同大小的集合动态交叉连接在一起

Question

我有一个未知数量的桶(集合),每个桶具有未知数量的实体

我需要生成所有实体的笛卡尔积,这样我最终会得到一个具有ARRAYS实体的COLLECTION,并且在每个数组中,每个桶都有1个代表性.

因此,如果我有5个桶(B1..B5),并且桶B1,B2各有1个项目,而桶B3,B4和B5各有4个,8个和10个项目,我将拥有320个阵列的集合,每个数组将有5个项目.

这里唯一的问题是,在开发时,桶的大小和桶的数量都是未知的.

性能在这里并不是非常重要,因为大多数时候,我的桶只有1个实体,而且很少有时候我的桶会包含20-30个项目...而且我通常会有5个30桶

我想在某种程度上使用linq,但是当我试图想象这是如何工作的时候,我的大脑正在变得油腻

Answer 1

您可以创建如下的扩展方法:

public static class EnumerableExtensions
{
    public static IEnumerable<TValue []> Permutations<TKey, TValue>(this IEnumerable<TKey> keys, Func<TKey, IEnumerable<TValue>> selector)
    {
        var keyArray = keys.ToArray();
        if (keyArray.Length < 1)
            yield break;
        TValue [] values = new TValue[keyArray.Length];
        foreach (var array in Permutations(keyArray, 0, selector, values))
            yield return array;
    }

    static IEnumerable<TValue []> Permutations<TKey, TValue>(TKey [] keys, int index, Func<TKey, IEnumerable<TValue>> selector, TValue [] values)
    {
        Debug.Assert(keys.Length == values.Length);

        var key = keys[index];
        foreach (var value in selector(key))
        {
            values[index] = value;
            if (index < keys.Length - 1)
            {
                foreach (var array in Permutations(keys, index+1, selector, values))
                    yield return array;
            }
            else
            {
                yield return values.ToArray(); // Clone the array;
            }
        }
    }
}

例如,它可以像:

    public static void TestPermutations()
    {
        int [][] seqence = new int [][]
        {
            new int [] {1, 2, 3},
            new int [] {101},
            new int [] {201},
            new int [] {301, 302, 303},
        };

        foreach (var array in seqence.Permutations(a => a))
        {
            Debug.WriteLine(array.Aggregate(new StringBuilder(), (sb, i) => { if (sb.Length > 0) sb.Append(","); sb.Append(i); return sb; }));
        }
    }

并产生以下输出:

1,101,201,301
1,101,201,302
1,101,201,303
2,101,201,301
2,101,201,302
2,101,201,303
3,101,201,301
3,101,201,302
3,101,201,303

那是你要的吗？

Answer 2

以下是如何在单个Linq语句中没有递归的情况下执行此操作(为方便起见,包含在扩展方法中):

public static IEnumerable<IEnumerable<T>> GetPermutations<T>(
                     IEnumerable<IEnumerable<T>> listOfLists)
{
    return listOfLists.Skip(1)
        .Aggregate(listOfLists.First()
                .Select(c => new List<T>() { c }),
            (previous, next) => previous
                .SelectMany(p => next.Select(d => new List<T>(p) { d })));
}

这个想法很简单:

1. 跳过第一行,这样我们就可以将它用作聚合的初始值.
2. 将此初始值放在我们将在每次迭代中增长的列表中.
3. 在每次迭代中,为每个元素创建一个新列表,previous并在其中添加每个元素next(这是由new List<T>(p) { d })完成的.

例

假设您有一个数组数组,如下所示:

var arr = new[] {
  new[] { 1,2 },
  new[] { 10,11,12 },
  new[] { 100,101 }
};

然后arr.GetPermutations()将返回包含以下内容的列表列表:

1,10,100
1,10,101
1,11,100
1,11,101
1,12,100
1,12,101
2,10,100
2,10,101
2,11,100
2,11,101
2,12,100
2,12,101

Answer 3

更快的非 Linq、非递归解决方案。我们预先分配了整个输出矩阵，然后一次只填充一列。

T[][] Permutations<T>(T[][] vals)
{
    int numCols = vals.Length;
    int numRows = vals.Aggregate(1, (a, b) => a * b.Length);

    var results = Enumerable.Range(0, numRows)
                            .Select(c => new T[numCols])
                            .ToArray();

    int repeatFactor = 1;
    for (int c = 0; c < numCols; c++)
    {
        for (int r = 0; r < numRows; r++)
            results[r][c] = vals[c][r / repeatFactor % vals[c].Length];
        repeatFactor *= vals[c].Length;
    }

    return results;
}