Generating combinations of multiple sets

Question

I am looking for an non-recursive algorithm or C code to generate all combinations of multiple sets (not sure if that's the correct scientific name). For example:

I have N=2 sets of symbols:

set 1: [A, Y, Z]
set 2: [1, Q]

The output should be:

A1
AQ
Y1
YQ
Z1
ZQ

N can vary, same as the number of symbols in particular set. Thanks in advance for any help! :)

You're looking for the [Cartesian product](http://en.wikipedia.org/wiki/Cartesian_product) — aioobe, Nov 04 '14 at 12:56
Thanks! I didn't actually notice that :) But I still have problem with expanding the calculation to accept indefinite number of sets. It's easy for just two, but for N...? — xba, Nov 04 '14 at 13:13
I'll get back to this in the evening if you haven't received an answer by then. — aioobe, Nov 04 '14 at 13:56

score 0 · Answer 1 · edited May 23 '17 at 12:13

Algorithm from: How can I compute a Cartesian product iteratively?

We can make an int array, whose length is n, int[ ] choose[n] to keep track of how many elements we have selected among all lists. All elements are set to 0 initially.

Then we iterate through a singly linked list storing all those arrays. If we have iterated an element in array i, choose[i]++, append it to the result. When choose[i] == array i's length, then break and move on to the next array.

But I don't know how to do the appending since every time we iterate through an array the result's size will be expanded.

If you have figured that out, please let me know.

Generating combinations of multiple sets

1 Answers1