如何获取具有不同元素数量的n个数组的所有可能组合？

Question

如何获取具有不同元素数量的n个数组的所有可能组合？

9

我有一些数组，在编程时不能确定其数量，可能是3、4或7个等等。每个数组都有一些元素，例如：

a={1 2 3 4}
b={6 7 5 2 1}
c={22 4 6 8 4 8 5 4}
d={....}
e, f, g, ...

我希望能够通过从每个数组中取一个数字来获取所有可能的组合，例如，我从a中选择“1”，从b中选择“7”，从c中选择第一个“8”，从d[3]和e[5]中选择...，以形成“1,7,8,d[3],e[5],...”这样的组合。由于在编译时我不知道数组的数量，所以无法使用嵌套循环。如果已知有4个数组（a、b、c、d），则可以使用4个循环：

for (int i = 0; i <= a.Length-1; i++)
{
   for (int j = 0; i <= b.Length-1; j++)
   {
      for (int k = 0; i <= c.Length-1; k++)
      {
         for (int m = 0; i <= d.Length-1; m++)
         {
            Response[f++] = a[i].toString()+","+b[j].toString()+","+c[k].toString()+","+d[m].toString();
         }
      }
   }
}

但是对于不同数量的数组，我没有任何想法。

- user3636337

为什么不使用二维数组呢？并且使用深度优先搜索方法来生成组合。 - Mifmif

@Rawling - 这不是重复的问题。这个问题有可变数量的输入。另一个问题仅限于三个输入数组。 - Enigmativity

@Enigmativity 那个问题的答案概括为这个解决方案。 - Rawling

@Rawling - 对不起，我没有在那个答案中看到递归。现在我看到了。我的错误。尽管如此，我还是更喜欢我的答案。 :-) - Enigmativity

@Enigmativity 这很公平，我认为你是对的，问题并不重复。 - Rawling

谢谢，我的问题已经解决了...我按照自己的意愿进行了更改，但是我仍然无法理解它的算法！是否有人能够回答这个问题：http://stackoverflow.com/questions/24094602/how-to-calculate-a-quadratic-function-of-n-variables - user3636337

3个回答

2

我认为linq版本看起来很棒：

from i in a
from j in b
from k in c
from m in d
select String.Join(",", i, j, k, m)

但是这个问题的答案并不容易。

Eric Lippert在他的博客上写了相关内容：

http://blogs.msdn.com/b/ericlippert/archive/2010/06/28/computing-a-cartesian-product-with-linq.aspx

- Dennis_E

实际上，响应不是一个字符串，我只是举了个例子！响应是一个数学函数...你可以把它看作响应= a+b+c+d.... 我能用这种方法来实现这个目的吗？！ - user3636337

当然。from和CartesianProduct只返回一个IEnumerable。只需更改select语句以选择所需内容即可。 - Dennis_E

2

以下扩展方法模拟了嵌套的 foreach 循环堆栈：

public static class Ext
{
    public static void ForEachNested<T>(
        this IEnumerable<IEnumerable<T>> sources,
        Action<IEnumerable<T>> action)
    {
        var enumerables = sources.ToArray();
        Stack<IEnumerator<T>> fe = new Stack<IEnumerator<T>>();
        fe.Push(enumerables[0].GetEnumerator());

        while (fe.Count > 0)
        {
            if (fe.Peek().MoveNext())
            {
                if (fe.Count == enumerables.Length)
                    action(new Stack<T>(fe.Select(e => e.Current)));
                else
                    fe.Push(enumerables[fe.Count].GetEnumerator());
            }
            else
            {
                fe.Pop().Dispose();
            }
        }
    }
}

您可以按照以下方式使用它：

new[] { a, b, c, d }.ForEachNested(e => { Response[f++] = string.Join(",", e); });

或者，进行数学运算，

new[] { a, b, c, d }.ForEachNested(e => { Response[f++] = e.Sum(); });

这样做的好处是不需要进行数百次的数组分配。

通常情况下，我会避免使用类似LINQ的方法来执行操作而不是查询，但由于这与foreach循环的工作方式非常相似，所以我并不介意。

- Rawling

我在这方面遇到了一个问题，声明没有错误，但是当我使用时，我定义了四个向量 a、b、c、d......并构造了一个由这些向量组成的数组，但是函数 ForEachNested(...) 的 "e" 参数无法识别。 - user3636337

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Enigmativity · Accepted Answer

这是有效的：

Func<
    IEnumerable<IEnumerable<int>>,
    IEnumerable<IEnumerable<int>>> f0 = null;
f0 = xss =>
{
    if (!xss.Any())
    {
        return new [] { Enumerable.Empty<int>() };
    }
    else
    {
        var query =
            from x in xss.First()
            from y in f0(xss.Skip(1))
            select new [] { x }.Concat(y);
        return query;
    }
};

Func<IEnumerable<IEnumerable<int>>, IEnumerable<string>> f =
    xss => f0(xss).Select(xs => String.Join(",", xs));

所以，如果我的输入是：

var input = new []
{
    new [] { 1, 2, 3, 4, },
    new [] { 6, 7, 5, 2, 1, },
    new [] { 22, 4, 6, 8, 4, 8, 5, 4, },
};

我可以通过以下方法获取结果：

var results = f(input);

以下是根据评论请求简单汇总结果的版本：

Func<IEnumerable<IEnumerable<int>>, IEnumerable<int>> f = null;
f = xss =>
{
    if (!xss.Any())
    {
        return new [] { 0 };
    }
    else
    {
        var query =
            from x in xss.First()
            from y in f(xss.Skip(1))
            select x + y;
        return query;
    }
};

var input = new []
{
    new [] { 1, 2, 3, 4, },
    new [] { 6, 7, 5, 2, 1, },
    new [] { 22, 4, 6, 8, 4, 8, 5, 4, },
};

var results = f(input);