多个有空值的数组之间的互换。

Question

我试图将多个不同大小的数组用空值进行换算。类似于这样。

IEnumerable<IEnumerable<T>> GetAllPermutations<T>(IEnumerable<IEnumerable<T>> lists)
{
  // if it received a list with 4 elements, it must return a list of list with 4 permutations
}

例子：

var list1 = new List<string>() { "1", "2", "3", "4" };
var list2 = new List<string>() { "5", "6", "7", "8" };
var list3 = new List<string>() { "9", "7", null, "0" };

var fullList = new List<List<string>>() { list1, list2, list3 };

var result = GetAllPermutations(fullList);

结果: 81个排列组合 (3^4)

{ "1", "2", "3", "4" }
{ "5", "2", "3", "4" }
{ "1", "6", "3", "4" }
{ "1", "2", "7", "4" }
{ "1", "2", "3", "8" }
.
.
.
.
.
{ "1", "9", "null", "0" }
{ "9", "7", null, "0" }

我试过很多东西，但都没有效果。我发现最好的办法是 本回答 从另一个问题。

var cc = Enumerable
                .Range(1, (1 << simpleList.Count) - 1)
                .Select(index => simpleList.Where((item, idx) => ((1 << idx) & index) != 0).ToList());

但它并不能用于多个列表。

EDIT: 上面的例子是一个组合式的答案，当我在处理另一个问题时，它为我工作。它确实产生了一些排列组合，但不是所有的排列组合，而且它对多个列表不起作用。

Answer 1

看起来你想要的是这些集合的枢轴的笛卡尔乘积。 所以使用下面这个来自Eric Lippert的博客的方法来做。笛卡尔产品 套数

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}));
 }

而这段代码是用来做Pivot的

IEnumerable<IEnumerable<T>> Pivot<T>(IEnumerable<IEnumerable<T>> lists)
{
    var pivot = new List<List<T>>();

    foreach(var sub in lists)
    {
        int i = 0;
        foreach(var val in sub)
        {
            if(pivot.Count <= i)
            {
                pivot.Add(new List<T>());
            }
            pivot[i].Add(val);

            i++;
        }
    }

    return pivot;
}

你应该通过以下几点来获得答案。

var list1 = new List<string>() { "1", "2", "3", "4" };
var list2 = new List<string>() { "5", "6", "7", "8" };
var list3 = new List<string>() { "9", "7", null, "0" };

var fullList = new List<List<string>>() { list1, list2, list3 };

var result = CartesianProduct(Pivot(fullList));

Answer 2

利用 笛卡尔产品:

static IEnumerable<IEnumerable<T>> GetAllPermutations<T>(IEnumerable<List<T>> lists)
{
    return lists.SelectMany(l => l.Select((item, index) => (item, index)))
        .GroupBy(c => c.index, c => c.item) // each group will have items allowed on n-th position
        .OrderBy(g => g.Key) // actually not needed in this case, but just to be sure
        .CartesianProduct();
}

public static class Ext
{
    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 }));
    }
}

Answer 3

利用积分幂的扩展方法，可以将输出的数字视为n位的基数b，计算出每个数字位置的值，再将其转换为输入的字符。

首先，积分幂扩展法。

public static int Pow(this int x, int pow) {
    int ret = 1;
    while (pow != 0) {
        if ((pow & 1) == 1)
            ret *= x;
        x *= x;
        pow >>= 1;
    }
    return ret;
}

现在，你可以把输入转换成一个列表来进行查找， 然后计算出（本例中）4位数字，并映射到输入的字母表上。

var numbase = fullList.Count;
var digits = fullList[0].Count;
var alpha = fullList.Select(l => l.ToList()).ToList();
var ans = Enumerable.Range(0, numbase.Pow(digits))
                    .Select(n => Enumerable.Range(0, digits).Select(d => alpha[(n / (numbase.Pow(d))) % numbase][d]));