# Enumerating sets in a random order

I have multiples arrays. I'd like to enumerate all sets containing exactly one item from each array in a (pseudo-)random order, without explicitly building the array of all sets.

Any solution, even with poor pseudo-randomization, is welcome.

EDIT: Example for clarity:

Say I have arrays

A = { a1, a2 }, B = { b1, b2 }, C = { c1 }


I want to enumerate all the sets containing exactly one ax, bx and cx

{ a1, b1, c1 }, { a1, b2, c1 }, { a2, b1, c1 }, { a2, b2, c1 }


I want to enumerate them in a random order. The naïve solution would be to enumerate them in an array, then shuffle this array. But the solution is huge and I don't want to store it explicitely in memory.

• an example would help ? I can't clearly understand what you want to achieve. Commented Sep 26, 2016 at 14:10
• Which resources have you checked? Are you aware of algorithms for sampling permutations and/or subsets? Commented Sep 26, 2016 at 15:57
• I don't just need sampling, I need the guarantee that each combination appears exactly once over the whole enumeration. Commented Sep 27, 2016 at 8:59

Suppose that you have arrays $A_1,\ldots,A_d$ of sizes $n_1,\ldots,n_d$. The total number of tuples is thus $n_1 \times \cdots \times n_d$. Given a number in the range $1,\ldots,n_1 \times \cdots \times n_d$, you can decipher it into a tuple (I leave this part to you). It now remains to compute a pseudorandom permutation of the numbers $1,\ldots,n_1 \times \cdots \times n_d$, another task I leave to you.