How to get all possible combinations for n arrays with different number of elements?

Question

I have some number of arrays which is unknown at programming time, maybe it is 3 or 4 or 7 ... each array has some elements, i.e,

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

I want to get get all possible combinations by sampling one number from each array for example one case is that I pick up "1" from a, "7" from b, first "8" from c, d[3], e[5],... to make "1,7,8,d[3],e[5],...". It's not possible to use nested for loops because I don't know the number of arrays at compile time. If it was known for example 4 arrays (a,b,c,d) I could use 4 loops:

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

but for different number of arrays, I don't have any idea.

why don't you use a two-dimentional array instead ? and use a DFS method to generate combination — Mifmif, Jun 03 '14 at 10:30
@Rawling - This is not a duplicate. This question has a variable number of inputs. The other question is restricted to only three input arrays. — Enigmativity, Jun 03 '14 at 10:51
@Enigmativity The answer to that question generalized to this solution. — Rawling, Jun 03 '14 at 10:52
@Rawling - I'm sorry, I didn't see recursion in that answer. I see it now. My mistake. Nevertheless, I like my answer better. :-) — Enigmativity, Jun 03 '14 at 10:59
@Enigmativity That's fair enough, I think you're right anyway in that the *question* isn't a duplicate. — Rawling, Jun 03 '14 at 11:00
Thanks, my problem was solved...I changed it according to my desire, nevertheless I couldn't realize its algorithm! is it possible for any one who also answer this quaestion: http://stackoverflow.com/questions/24094602/how-to-calculate-a-quadratic-function-of-n-variables — user3636337, Jun 07 '14 at 06:55

Enigmativity · Accepted Answer · 2014-06-03T11:24:36.930

8

This works:

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

So if I have this input:

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

I can get the results this way:

var results = f(input);

results

Here's a version which simply sums the results, as per the request in the comments:

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

edited Jun 03 '14 at 11:24

answered Jun 03 '14 at 10:51

Enigmativity

113,464
11
89
172

actually the response is not a string, I wrote it as an example! response is a mathematical function... you may assume it like response= a+b+c+d+.... Am I able to use this method for that purpose?! – user3636337 Jun 03 '14 at 11:05
As in you just want to sum all the values?! Please include an example of what output you're looking for?! – arserbin3 Jun 03 '14 at 11:12
no! for two vector a , b it is as follows: response=constant1*a+constant2*b+constant3*a*b+constant4*a^2+constant5*b^2+constant6; for three vector a, b, c it is as follows: response=constant1*a+constant2*b+constant3*c+constant4*a*b+constant5*a*c+constant6*b*c+constant7*a^2+constant8*b^2+constant9*c^2+constant10; – user3636337 Jun 03 '14 at 11:23
@user3636337 - I've added a summing version to my answer. But it seems like it isn't even as simple as summing the values. I think you need to clarify your question. – Enigmativity Jun 03 '14 at 11:26
Thanks, my problem was solved...I changed it according to my desire, nevertheless I couldn't realize its algorithm! is it possible for you one to also answer this quaestion: stackoverflow.com/questions/24094602/ – user3636337 Jun 07 '14 at 07:19

score 2 · Answer 2 · answered Jun 03 '14 at 10:35

2

I think the linq version looks awesome:

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

But the answer to your question is not easy. Eric Lippert wrote about it on his blog:

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

answered Jun 03 '14 at 10:35

Dennis_E

8,751
23
29

actually the response is not a string, I wrote it as an example! response is a mathematical function... you may assume it like response= a+b+c+d.... Am I able to use this method for that purpose?! – user3636337 Jun 03 '14 at 11:04
Sure. The from's and the CartesianProduct just return an IEnumerable. Just change the select statement to select what you need. – Dennis_E Jun 03 '14 at 11:14

score 2 · Answer 3 · answered Jun 03 '14 at 11:13

The following extension method imitates a nested stack of foreach loops:

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

You could use it as follows:

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

or, to do your maths,

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

This has the advantage of not performing hundreds of array allocations.

Ordinarily I'd shy away from using a LINQ-like method to act rather than query but as this is closely imitating how a foreach loop works I don't mind so much.

I have one problems with that, the declarations has no errors but when I use it, i define four vectors a,b,c,d...and construct an array of these vectors but the "e" parameter of function ForEachNested(...) is unrecognizable — user3636337, Jun 07 '14 at 10:23

How to get all possible combinations for n arrays with different number of elements?

3 Answers3

Linked