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

Question

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.

Answer 1

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.)