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.