Sample a set of N numbers without replacement, each element taken from N different weighted sets

Here's my problem: I have $$N$$ sets of integers $$S_i$$ where $$|S_i| = n_i \forall i \in [1,N]$$ each with non-uniform weights $$W_i = \{w_{i,1}, ..., w_{i,n_i}\}$$ such that $$\sum_{j}{w_{i,j}} = 1$$. I want to sample $$m$$ unique lists $$P_{k \in [1,m]} = (p_{k,1}, ...,p_{k,i}, ...,p_{k,N})$$ of $$N$$ integers (including duplicates, and ordering matters), with each element $$p_{k,i} \in S_i$$.

The naive implementation I use as a proof of concept to generate a new unique list $$P_k$$: I pick an element from $$S_1$$ at random according to the weights $$W_1$$, then I pick an element from $$S_2$$ with weights $$W_2$$, etc... until I have $$N$$ elements to create a candidate list. If this list is not unique among exiting lists, I discard it and start again at the top, otherwise it becomes the list $$P_k$$. This is repeated until I get $$m$$ unique lists.

Although it works and gives me the correct result, this is very inefficient as I get more and more duplicate sets as $$m$$ increases, and as the weights $$w_i$$ diverge from a uniform distribution.

Here's an example with disjoint sets: $$N=3, n_1=4, n_2=3, n_3=5$$ $$S_1 = \{1, 2, 3, 4\}; S_2 = \{11, 12, 13\}; S_3 = \{21, 22, 23, 24, 25\};$$ With $$m=3$$, a possible sampling would be: $$P_1=(1, 11, 21), P_2=(1, 12, 24), P_3=(3, 12, 22)$$

All the sampling algorithms I have found either assume uniform distribution, or require "flattening" my problem from $$N$$ sets to one set of all possible combinations (and calculating the corresponding weights). Although the computation of the weight for a specific combination is trivial, it is not feasible for the size and number of sets I'm working with: $$2 \leq N \leq 20$$ and $$2 \leq n_i \leq 50$$. Typically $$1 \leq m \leq 1000$$ and $$m \leq \prod_{i \in [1,N]}{n_i}$$.

Does anyone has an idea to replace my current naive solution? I am looking for an algorithm that would allow me to make that sampling without replacement a. directly from $$S_i$$ and $$W_i$$, or b. a 1D weighted sampling algorithm that does not require pre-computing all possible combinations and corresponding weights.

There is a mapping from each possible list $$P$$ to an interval $$[\ell,r)$$ contained in $$[0,1)$$, such that the resulting intervals (if you consider all possible lists) form a partition of $$[0,1)$$.

In particular, if $$P=(p_1,\dots,p_N)$$ and $$N\ge 1$$, define

$$f(P) = w_{p_N} f(p_1,\dots,p_{N-1}) + w_1 + w_2 + \dots + w_{p_N-1};$$

and if $$N=0$$, define $$f(p_1) = [0,1)$$. Also, given $$x \in [0,1)$$, you can find $$P$$ such that $$x \in f(P)$$ in a straightforward way.

Now one way to sample from your distribution is to sample a real number $$x_1$$ uniformly at random from $$[0,1)$$, then map it back to the corresponding list $$P_1$$, i.e., find $$P_1$$ such that $$x_1 \in f(P_1)$$, and output $$P$$.

If you want to sample a second list $$P_2$$ that is guaranteed to be different from $$P_1$$, sample $$x_2$$ uniformly at random from $$[0,1) \setminus f(P_1)$$, find $$P_2$$ such that $$x_2 \in f(P_2)$$, and output $$P_2$$.

To sample a third list $$P_3$$ that is different from $$P_1,P_2$$, sample $$x_3$$ uniformly at random from $$[0,1) \setminus (f(P_1) \cup f(P_2))$$, find $$P_3$$ such that $$x_3 \in f(P_3)$$, and output $$P_3$$.

Repeat. Note that $$[0,1) \setminus (f(P_1) \cup \cdots \cup f(P_m))$$ can be expressed as a disjoint union of $$m+1$$ intervals, and you can sample uniformly from it in $$O(m)$$ time, so the running time to generate $$m$$ different $$P$$'s is something like $$O(m^2N)$$. This should be good enough to accommodate your parameter settings. (In fact, by storing that union of intervals in a self-balancing binary tree structure, you can sample in $$O(\log m)$$ time, so you can reduce the total running time to $$O(mN\log m)$$, but that probably won't be necessary for your parameter settings.)

• Thanks @D.W. after working on it on my side, your solution is very similar to what I came up with. But instead of picking from $[0,1) \setminus (f(P_1) \cup... \cup f(P_{m-1}))$, I update the partition of $[0,1)$ by setting the weights of the previously sampled lists $P_1, ..., P_m$ to 0. I keep track of the existing lists $P_1, ..., P_m$ in a tree. With a lot of memoization, I have very reasonable run times for $m <= 100000$ which is well beyond the requirements. Jun 29, 2022 at 22:24
• @Montspy great, I'm glad that worked out! Thanks for reporting back about what ultimately worked well for you.
– D.W.
Jul 3, 2022 at 3:24