Creating Arrays of permutations

Question

I have an array that looks like this

mainArray =>
 [a] =>
 [A]
 [B]
 [C]
 [b] =>
 [D]
 [E]
 [F]
 [c] =>
 [G]
 [H]
 [I]

I want to put these into an array like this:

secondArray =>
 [0] => { [A], [D], [G] }
 [1] => { [A], [E], [G] }
 .
 .
 .
 [n] => { [C], [F], [I] }

I am having trouble figuring out how to get the right number of elements in $secondArray that start with a certain element in { [A],[B], .. }. For example, how many start with [A].

This is what I think I have to do:

secondArray =>
 [0] =>
 [A]
secondArray =>
 [0] =>
 [A]
 [D]
secondArray =>
 [0] =>
 [A]
 [D]
 [G]
secondArray =>
 [0] =>
 [A]
 [D]
 [G]
 [1] =>
 [A]
 [D]
 [H]
secondArray =>
 [0] =>
 [A]
 [D]
 [G]
 [1] =>
 [A]
 [D]
 [H]
 [2] =>
 [A]
 [D]
 [I]
secondArray =>
 [0] =>
 [A]
 [D]
 [G]
 [1] =>
 [A]
 [D]
 [H]
 [2] =>
 [A]
 [D]
 [I]
 [3] =>
 [A]
 [E]
 [G]
 [4] =>
 [A]
 [E]
 [H]
 [5] =>
 [A]
 [E]
 [I]
secondArray =>
 [0] =>
 [A]
 [D]
 [G]
 [1] =>
 [A]
 [D]
 [H]
 [2] =>
 [A]
 [D]
 [I]
 [3] =>
 [A]
 [E]
 [G]
 [4] =>
 [A]
 [E]
 [H]
 [5] =>
 [A]
 [E]
 [I]
 [6] =>
 [A]
 [F]
 [G]
 [7] =>
 [A]
 [F]
 [H]
 [8] =>
 [A]
 [F]
 [I]

and so on, but I can't really think of how to implement it...

Any help would be appreciated

• Marlon: What language are you using? Please tag accordingly...
• John Dvorak: @Marlon This is an algorithm question. I suppose pseudocode is sufficient.

Answer 1

You can generate the elements sequentially.

To implement the iterator:

-remember the array of input arrays, if there exists a next element.
 and an array of indexes of the same length.
-if any input array is empty, the result set is empty and there is no next (first) element.
-initialise the array of indexes to all zeroes.
To get the next element:
-If you remember there is no next element, fail.
-compute the result:
--start with an empty result
--For each input array and its corresponding index
---Append input[index] to the result
-compute the next set of indexes:
--Iterate the indexes in reverse order. For each index
---Increment the index
---If the index now points past its corresponding input array
----Reset the index to zero
---Else
----Return the result, exiting the function.
-Remember there is no next element
-Return the result (last element).

If you do want all combinations at once, the code simplifies slightly:

-if any input array is empty, the result set is empty.
-initialise the array of indexes to all zeroes.
-compute the result and store in the result set.
-while not done generating results:
--Iterate the indexes in reverse order. For each index
---Increment the index
---If the index now points past its corresponding input array
----Reset the index to zero
---Else
----Compute the result from the current indexes
----Add the result to the result set
----Continue generating the results
--(all indexes were reset to zero) finish generating the results.
-return the result set.

Answer 2

In Ruby:

['A', 'B', 'C'].product(['D', 'E', 'F'])
# => [['A', 'D'], ['A', 'E']...

Array#product can accept multiple arrays.