CODEWITHSUNDEEP
algorithmpermutation
Greg Witczak
Greg Witczak

Reputation: 1694

Avoiding permutation patterns - print all permutations wihout 231 scheme

On the input I have a "n" number, which is the size of permutation, and I have to print all possible permutations containing n numbers (from 1 do n), but I must reject ones with "231 scheme"

"231 scheme" means that in permutation we can find such three consecutive numbers (x, y, z) which will apply to inequality z (1<2<3).

So, for example for n=4 we have 4! = 24 permutations. We reject nine of them...

...and print the other fifteen posibilities.

Ok, so that's the problem. I've already spent a lot of time thinking about this task. And I've figured out something like this:

We could generate permutations for n=3, reject 231 and then (for n=4) generate all possibilities based on ones previously generated.

So I'll pick a 132 permutation. Now we "insert" 4 on all possible ways: 4132, 1432, 1342, 1324. We can tell for sure, that the first and last permutations are fine, so we have to look closer to the other two. And my idea is to find the highest number from numbers standing on the left side of the "4", and a minimum from ones standing on the right side of "4". And if left_max>right_min, we have our "231 scheme".

For example permutation 1342: left_max=3, right_min=2, so it's correct "231" and we reject that from final answer.

I'd be very thankful for any comments, ideas and tips. I realize that my idea may be useless, but that's the best I have. So is there any other (possibly smarter and/or with better complexity) way?

Upvotes: 2

Views: 1400

Answers (2)

Sudix
Sudix

Reputation: 360

It might be an old hat, but just to add this: The number of permutations avoiding 231 are the Catalan-numbers, which can be estimated as O(2^(2n)) (they also have a nice closed formula). To be precise, for n= 15 we'd have 9,694,845 numbers.

Using the recursion formula for the Catalan-numbers enter image description here

we can build a recursion for permutations avoiding 231 as well:

all_perms(n):
    if (n=0) return [1];
    out = [];
    for i=1,...,n:
        for perm1, perm2 in all_perms(i-1), all_perms(n-i):
            increase all elements in perm2 by i-1;
            append n to perm1 (from the right), then append perm2 to that (from the right);
        add the result of appending into out;

You can further refine this algorithm using dynamic programming/memoization.

Upvotes: 0

PengOne
PengOne

Reputation: 48398

You have the right idea. Build your permutations iteratively by adding 1 up to n. When you add i, you need only check that the pattern you wish to avoid is not present with i.

For example, if the pattern is 231, then check that nothing to the left of i is greater than anything to the right of i.

If you want to print all results instead of generating them (this avoids the storage issue), then you can go through the permutations lexicographically. Scan the prefix, and if at any point the pattern is present, e.g. in the first k letters, then move on to the next prefix. This will speed up the iteration a bit.

Upvotes: 1

Related Questions