1
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ Do you want to generate all of those permutations and the priority is guiding you which ones to output first? Or do you want to create random ones? In addition, you need to more formally specify what the priorities are. For example, how can $a_5$ have priority over $a_4$? $\endgroup$
    – Ingix
    May 11, 2019 at 6:47
  • $\begingroup$ Thanks for your input. I'd like to use the priority to guide the output, but assuming large numbers perhaps the top few will be sufficient. I've made a change to how the sets are described to hopefully clear up what I mean by the priorities. I'm trying to keep it generalized, but I don't want to be obscure either. $\endgroup$ May 11, 2019 at 8:17
  • $\begingroup$ Can you clarify on the binary priority for the output? Lets say you have a collection of all $X$ solutions $X_1,X_2,X_3\dots$, then when does $X_i=(x^i_1,x^i_2,\dots)$ have higher output priority over $X_j=(x^j_1,x^j_2,\dots)$? Lets say for example $x^i_1,x^i_2,\dots,x^i_5$ have binary bits $1,0,1,0,0$ and $x^j_1,x^j_2,\dots,x^j_5$ have binary bits $0,1,0,1,0$, then does $X_i$ have higher, lower, or equal, output priority to $X_j$? $\endgroup$
    – Vepir
    May 11, 2019 at 11:07

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.