Variable number of for loops without recursion but with Stack?

Question

I know the usual approach for "variable number of for loops" is said to use a recursive method. But I wonder if I could solve that without recursion and instead with using Stack, since you can bypass recursion with the use of a stack.

My example:
I have a variable number of collections and I need to combine every item of every collection with every other item of the other collections.

// example for collections A, B and C:
A (4 items) + B (8 items) + C (10 items)
4 * 8 * 10 = 320 combinations

I need to run through all those 320 combinations. Yet at compile time I don't know if B or C or D exist. How would a solution with no recursive method but with the use of an instance of Stack look like?

Edit:
I realized Stack is not necessary here at all, while you can avoid recursion with a simple int array and a few while loops. Thanks for help and info.

Well, technically, recursion is using the program's function call stack :p — Nyerguds, Apr 22 '16 at 07:14
My question would be: As a recursive method is the obvious logical choice for such a problem, why would you like to make the solution unnecessarily complicated? It's like asking "How can I add 5.5 and 4.6 using only ints?" — philkark, Apr 22 '16 at 07:22
@phil13131 Your example is impossible. Are you saying my question asks for the impossible? I don't think so. — Bitterblue, Apr 22 '16 at 07:39
@user6235927 Of course it's possible to implement floating point arithmetic using integers. How do you think the early processors that didn't have FPUs did it? — Matthew Watson, Apr 22 '16 at 07:47
@user6235927 My example is by far not impossible. You could recursively calculate every decimal digit using integers and add them up and then display it as a collection of one digit integers. High precision calculators have to work that way. It is just overly complicated for such a simple task. — philkark, Apr 22 '16 at 07:47
@Nyerguds and with an implicit stack one would still call it a recursive process. In the end the actual machine code run would be very similar. — Sylwester, Apr 22 '16 at 08:40
You need to allocate dynamically loop variables. You would like to do use the stack for this. My question: You are using a language that is always running with a garbish collection. So why not using the heap? As far as I know its impossible to allocate dynamic space on the stack (without the recusive function call workaround). — Schafwolle, Apr 22 '16 at 08:59

Magnus · Answer 1 · 2016-04-22T09:30:16.067

2

Not with a stack but without recursion.

void Main()
{
    var l = new List<List<int>>()
    {
        new List<int>(){ 1,2,3 },
        new List<int>(){ 4,5,6 },
        new List<int>(){ 7,8,9 }
    };

    var result = CartesianProduct(l);
}

static IEnumerable<IEnumerable<T>> CartesianProduct<T>(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})                       
        );
 }

Function taken form Computing a Cartesian Product with LINQ

edited Apr 22 '16 at 09:30

answered Apr 22 '16 at 07:29

Magnus

45,362
8
80
118

1

[Here's the source article (by Eric Lippert) for the code posted above](https://blogs.msdn.microsoft.com/ericlippert/2010/06/28/computing-a-cartesian-product-with-linq/) And [here's the original SO answer where this code comes from](http://stackoverflow.com/a/3098381/106159) – Matthew Watson Apr 22 '16 at 07:41
1

Do I understand this correctly or have you just hidden the recursiveness into standard libraries (; – philkark Apr 22 '16 at 07:50
@phil13131 There is no recursion in the linq functions used here. – Magnus Apr 22 '16 at 09:36

score 0 · Accepted Answer · edited May 23 '17 at 12:31

Here is an example of how to do this. Algorithm is taken from this question - https://stackoverflow.com/a/2419399/5311735 and converted to C#. Note that it can be made more efficient, but I converted inefficient version to C# because it's better illustrates the concept (you can see more efficient version in the linked question):

    static IEnumerable<T[]> CartesianProduct<T>(IList<IList<T>> collections) {
        // this contains the indexes of elements from each collection to combine next
        var indexes = new int[collections.Count];
        bool done = false;
        while (!done) {
            // initialize array for next combination
            var nextProduct = new T[collections.Count];
            // fill it
            for (int i = 0; i < collections.Count; i++) {
                var collection = collections[i];
                nextProduct[i] = collection[indexes[i]];
            }
            yield return nextProduct;
            // now we need to calculate indexes for the next combination
            // for that, increase last index by one, until it becomes equal to the length of last collection
            // then increase second last index by one until it becomes equal to the length of second last collection
            // and so on - basically the same how you would do with regular numbers - 09 + 1 = 10, 099 + 1 = 100 and so on.

            var j = collections.Count - 1;
            while (true) {
                indexes[j]++;
                if (indexes[j] < collections[j].Count) {
                    break;
                }
                indexes[j] = 0;
                j--;
                if (j < 0) {
                    done = true;
                    break;
                }
            }
        }
    }

I just build a function myself that does pretty much the same. Thanks! — Bitterblue, Apr 22 '16 at 09:34

Variable number of for loops without recursion but with Stack?

2 Answers2