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.

• Nyerguds: Well, technically, recursion is using the program's function call stack :p
• philkark: 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?"
• Bitterblue: @phil13131 Your example is impossible. Are you saying my question asks for the impossible? I don't think so.
• Matthew Watson: @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?
• philkark: @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.

Answer 1

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

• Matthew Watson: Here's the source article (by Eric Lippert) for the code posted above And here's the original SO answer where this code comes from
• philkark: Do I understand this correctly or have you just hidden the recursiveness into standard libraries (
• Magnus: @phil13131 There is no recursion in the linq functions used here.

Answer 2

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

• Bitterblue: I just build a function myself that does pretty much the same. Thanks!