4
$\begingroup$

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.

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

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ This is definitely the way to go! However, the same problem is postponed, how do I build my pseudorandom permutation of the said numbers without putting them into an array? $\endgroup$
    – Julien
    Commented Sep 26, 2016 at 14:25
  • $\begingroup$ Julien, I'm afraid you'll have to figure this out on your own. If you get stuck, you can ask a new question. $\endgroup$ Commented Sep 26, 2016 at 14:27
  • $\begingroup$ @Julien (Pseudo-)Random number generation is a topic with lots of literature and good library support. When generating anything random, you typically assume access to some source of random numbers, be it in theory or practice. $\endgroup$
    – Raphael
    Commented Sep 26, 2016 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.