Problem Detail: 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.
Asked By : Julien
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/63904 Ask a Question Download Related Notes/Documents
