I am doing some self study and have come up with a problem I'm not sure how to go about solving. Please correct me if I've used any term incorrectly. Purely mathematical or Python approaches are fine.
I have ordered sets:
$A = \{a_1, a_2, a_3, a_4, a_5\}$
$B = \{b_1, b_2, b_3\}$
$C = \{c_1, c_2, c_3, c_4, c_5, c_6\}$
$D = \{d_1, d_2, d_3, d_4, d_5, d_6\}$
Let's say each $a,b,c,d$ has two properties: the first defining its position within the order of its respective set, and the second a binary priority for the output. (e.g. $a_1 = (1,1), a_2 = (2,0), a_3 = (3,1)$).
I want to generate permutations that contain every element of $A,\ B,\ C,$ and $D$ such that order is preserved from within each set, i.e. $(a_1, b_1, a_2, …)$ is fine, but $(a_2, a_1, …)$ is not.
Additionally, as part of the output, I want to minimize (frontload) the positions of certain elements (e.g. $a_1, d_2, a_5$ each have priority over $a_2, a_4,$ or $d_1$).
Desired end result: $X = (x_1, x_2, x_3, …, x_{20})$ where each $x$ is an element from $A, B, C,$ or $D$.
How can I find solutions?
Best Answer
Remark
Assuming you want to generate all the solutions, you can solve the problem without priority output, and then iterate and apply the priority output to the collection of all solutions.
I'll present you the first thing that falls on my mind - a structure of the problem that shows how you can recursively generate all permutations while satisfying the condition of preserving the order within sets.
If however you need only to output (and generate) the top priority permutations as a subset of all permutations (which would be preferred if the total number of all permutations is very large), then you'll need to prioritize those permutations while generating the solutions.
The general problem
Generally, lets have sets $A_1,A_2,A_3,\dots,A_m$, where $i$th one has $n_i=|A_i|$ elements $a^{i}_1,a^{i}_2,a^{i}_3,\dots,a^{i}_{n_i}$.
We want to get all permutations that satisfy the condition that the order is preserved from within each set. (The order being defined by indices of elements: $a^i_j\lt a^i_{j+1},j\in\{1,\dots,n_i\}$.)
The base case
If $m=1$ then the only such permutation is ordered $A_1$, that is: $X^1=(a^{1}_1, a^{1}_2, a^{1}_3, \dots, a^{1}_{n_1})$.
If $m=2$, then each such permutation is of form $X^2=(A^2_1, a^{1}_1, A^2_2, a^{1}_2, A^2_3, a^{1}_3, \dots, A^2_{n_1}, a^{1}_{n_1}, A^2_{n_1+1})$,
where $A^2_k$ are ordered, mutually disjoint, subsets of $A_2$ such that order is preserved: $\max A^2_j < \min A^2_{j+1}$.
Now simply partition $A_2$ into sets $A^2_k$ in all valid ways to get all $X^2$ permutations.
You can satisfy the order preservation $\max A^2_j < \min A^2_{j+1}$ property by keeping track of some index $M$, and iterating elements of $A_2$ in order.
That is, $a^2_1$ can be put into any of $A^2_1,\dots,A^2_{n_1+1}$ sets, then $a^2_2$ can be put into any of $A^2_{M_1},...,A^2_{n_1+1}$ where $M_1$ is the index of set $A^2_{M_1}$ where $a^2_1$ was placed, then $a^2_3$ can be put into any of $A^2_{M_2},...,A^2_{n_1+1}$ where $M_2$ is now the index of set $A^2_{M_2}$ where $a^2_2$ was placed, $\dots$ and so on for all $a^2_i$.
You should have $\binom{n_1+n_2}{n_2}$ solutions for $m=2$, where $\binom \square \square$ is the binomial coefficient.
Example:
$A_1=\{a^1_1,a^2_2,a^3_3\}=A=\{a_1,a_2,a_3\}$
$A_2=\{a^2_1,a^2_2\}=B=\{b_1,b_2\}$
First iteration, we insert $b_1$ in all valid ordered $A^2_k=B_k$ subsets to get:
$(b_1,a_1,a_2,a_3),(a_1,b_1,a_2,a_3),(a_1,a_2,b_1,a_3),(a_1,a_2,a_3,b_1)$
Second iteration, we insert $b_2$ in all valid ordered $A^2_k=B_k$ subsets from previous iteration, to get:
$M_1=1\implies(b_1,b_2,a_1,a_2,a_3),(b_1,a_1,b_2,a_2,a_3),(b_1,a_1,a_2,b_2,a_3),(b_1,a_1,a_2,a_3,b_2)$
$M_1=2\implies(a_1,b_1,b_2,a_2,a_3),(a_1,b_1,a_2,b_2,a_3),(a_1,b_1,a_2,a_3,b_2)$
$M_1=3\implies(a_1,a_2,b_1,b_2,a_3),(a_1,a_2,b_1,a_3,b_2)$
$M_1=4\implies(a_1,a_2,a_3,b_1,b_2)$
There is no $b_3$ so we are done (no third iteration).
We have $10$ solutions yielded by last iteration, as expected: $\binom{3+2}{2}=\binom{5}{2}=\frac{5!}{2!3!}=10$.
Now you can print these in what ever order of output priority you like.
The general case
You can continue to build permutations for $m+1$ sets on top of permutations for $m$ sets, using the same algorithm as in the base case.
Lets say you have all solutions (permutations) $s\in S_m$ for case $m$. Then to get $S_{m+1}$, apply the same algorithm as in base case, but instead of single $(A_1,A_2)$ pair, we are applying it to all pairs $(s,A_{m+1}),s\in S_m$.
Adding on to the last example, if we introduce the set $A_3=C=\{c_1,c_2,c_3,c_4\}$,
Then we are now applying the base case to:
$s=\{s_1,s_2,s_3,s_4,s_5\}\in S_2=\{(b_1,b_2,a_1,a_2,a_3),(b_1,a_1,b_2,a_2,a_3),\dots,(a_1,a_2,a_3,b_1,b_2)\}$
$C=\{c_1,c_2,c_2,c_4\}$
For every $s$. You are expecting $\binom{5+4}{4}=126$ solutions (permutations) for every $s$. Since we have ten such solutions $|S_2|=10$, in total we have $10\cdot126=1260$ solutions that are $\in S_3$, for this particular example.
The example in question,
$A = \{a_1, a_2, a_3, a_4, a_5\}$
$B = \{b_1, b_2, b_3\}$
$C = \{c_1, c_2, c_3, c_4, c_5, c_6\}$
$D = \{d_1, d_2, d_3, d_4, d_5, d_6\}$
Would have $\binom{5+3}{3}\binom{8+6}{6}\binom{14+6}{6}=56\cdot3003\cdot38760=6\text{ }518\text{ }191\text{ }680>6\cdot10^9$ solutions.
Which can be generated by applying base case to $A,B$ to get $S_2$, then base case to all $s\in S_2,C$ to get $S_3$, and finally the base case to all $s\in S_3,D$ to get all $X=(x_1,x_2,\dots,x_{20})\in S_4$, as mentioned in the general case.