Search specific permutation of permutationsubset with constraints

Question

Iam searching one permutation P consisting of p1...pn of following subset S. S is defined of the Labels L. L1...Lk. Where a L contains pi...pj. Where the inverse of P has at most k-1 decreasing adjecent Elements. k <= n.

Example:

n := 4

k := 2

L1 := 1,2

L2 := 3,4

L := L1,L2,L1,L2

S := 1324,1423,2314,2413

one solution would be P := 1342

no solution would be P := 3142 because decreasing adjecent elements are 2 but only max1 ist allowed because k =2.

Exists therefor an algorithm to find P of S defined by L?

Currently I use bruteforce to figure one permutation P, but its getting very fast unusable slow.

Answer 1

So each of L1, ..., Lk is a consecutive set of elements. At each place we see Li, Lj in the definition of L, one of three things is true:

1. i < j in which case it is ascending.
2. i = j in which case it could be ascending or descending.
3. i > j in which case it must be descending.

By counting the number of places where case 3 is true, we get a minimum number of descending elements already in the definition of L.

Next, for each Li we have a pattern we can write down with len(Li)-1 ; and , where a ; means that there are elements of other Ljs between two members of Li, and , means that Li elements are adjacent and so the order of the elements may result in a descent. We want to know, "For each possible number of descents within Li, how many permutations of Li have that number of descents?"

We will think of building the permutations as follows:

The first element goes at position 0.
The second element goes to position 0 or 1. (If at 0, the first element is moved.)
The third element goes to position 0, 1, or 2.
etc

A descent is when the next element is smaller than the previous, at a transition matching a ,.

We actually will want the following data structure for later use:

cache[Li] gives:
    by how many elements are chosen:
        by the last element chosen:
            by the number of descents we will add:
                how many ways of finishing this permutation

So we can write a recursive function that takes:

1. The pattern for Li.
2. How many elements have been chosen.
3. What index was last chosen.

It then returns a dictionary mapping descents to count of ways to finish the permutation for Li.

Memoize that and we get our desired data structure.

Now we'll repeat the idea. We want:

cache2[i] gives:
    by number of descents to use:
        how many permutations of L[i], L[i+1], ..., L[k] meet it.

Again we can write a recursive function using cache to calculate this, and we can memoize it to get cache2.

---

And NOW we can reverse the process.

1. We know how many descents came from the definition of L.
2. We know the distribution of remaining descents from cache2[1], so we can randomly pick how many descents there will be meeting our condition among L1...Lk.
3. For L1...Lk we can look at cache[L1][1][0] and cache2[i+1] to figure out how many descents there will be within Li with the correct probability.
4. For each Li we can look at how many descents we want to wind up with, its pattern, and cache2[Li] to figure out a random sequence of inserts winding up with the right pattern. The first insert is always at 0. After that you always know the size, and where the last insert was, and how many descents are left. So for each possiblenext insert you figure out if it counts as a descent (look at both pattern, and whether it is before the last insert), and the number of ways to finish from there. Then you can choose the next insert randomly with the right possibility.
5. For each Li we can turn the pattern of inserts into the list of values in order. (I will explain this step more.)
6. We can now follow the pattern of L and fill in all of the values.

Now for step 5, let's illustrate with your example from the chat. Suppose that L2 = [4, 5, 6] and the pattern of inserts we came up with was [0, 1, 0]. How do we figure out the arrangement of values?

Well first we do our inserts:

[1]
[1, 2]
[3, 1, 2]

This says that the first element (4) goes to the third place, the second (5) to the first, and the third (6) to the second. So our permutation for L2 is [5, 6, 4].

---

This will be a lot of code to write. But it will be polynomial. Specifically if m is the count of the most common label, cache will have total size at most O(k m^2). Thanks to memoization, each entry takes O(m) to calculate. Everything else is small relative to that. So total space is O(k m^2) and time is O(k m^3).