CODEWITHSUNDEEP
algorithmmathstackpermutation
Abhay Patil
Abhay Patil

Reputation: 399

Stack permutations sorted in lexicographical order

A stack permutation of number N is defined as the number of sequences which you can print by doing the following

  1. Keep two stacks say A and B.
  2. Push numbers from 1 to N in reverse order in B. (so the top of B is 1 and the last element in B is N)
  3. Do the following operations

All possible sequences obtained by doing these operations in some order are called stack permutations.

eg: N = 2
stack permutations are (1, 2) and (2, 1)
eg: N = 3
stack permutations are (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1) and (3, 2, 1)

The number of stack permutations for N numbers is C(N), where C(N) is the Nth Catalan Number.

Suppose we generate all stack permutations for a given N and then print them in lexicographical order (dictionary order), how can we determine the kth permutation, without actually generating all the permutations and then sorting them?

I want some algorithmic approaches that are programmable.

Upvotes: 0

Views: 666

Answers (2)

Deepesh Patel
Deepesh Patel

Reputation: 11

This is possible using factoradic(https://en.wikipedia.org/wiki/Factorial_number_system)

If you need quick solution in Java use JNumberTools

JNumberTools.permutationsOf("A","B","C")
                .uniqueNth(4) //next 4th permutation
                .forEach(System.out::println);

This API will generate the next nth permutation directly in lexicographic order. So you can even generate next billionth permutation of 100 items.

for generating next nth permutation of given size use:

JNumberTools.permutationsOf("A","B","C")
                .kNth(2,4) //next 4th permutation of size 2
                .forEach(System.out::println);

maven dependency for JNumberTools is:

<dependency>
    <groupId>io.github.deepeshpatel</groupId>
    <artifactId>jnumbertools</artifactId>
    <version>1.0.0</version>
</dependency>

Upvotes: 0

btilly
btilly

Reputation: 46445

You didn't say whether k should be 0 based or 1 based. I chose 0. Switching back is easy.

The approach is to first write a function to be able to count how many stack permutations there are from a given decision point. Use memoization to make it fast. And then proceed down the decision tree by skipping over decisions that lead to permutations which are lexicographically smaller. That will lead to the list of decisions that are the one you want.

def count_stack_permutations (on_b, on_a=0, can_take_from_a=True, cache={}):
    key = (on_b, on_a, can_take_from_a)
    if on_a < 0:
        return 0 # can't go negative.
    elif on_b == 0:
        if can_take_from_a:
            return 1 # Just drain a
        else:
            return 0 # Got nothing.
    elif key not in cache:
        # Drain b
        answer = count_stack_permutations(on_b-1, on_a, True)
        # Drain a?
        if can_take_from_a:
            answer = answer + count_stack_permutations(on_b, on_a-1, True)
        # Move from b to a.
        answer = answer + count_stack_permutations(on_b-1, on_a+1, False)
        cache[key] = answer

    return cache[key]

def find_kth_permutation (n, k):
    # The end of the array is the top
    a = []
    b = list(range(n, 0, -1))
    can_take_from_a = True # We obviously won't first. :-)

    answer = []
    while 0 < max(len(a), len(b)):
        action = None
        on_a = len(a)
        on_b = len(b)

        # If I can take from a, that is always smallest.
        if can_take_from_a:
            if count_stack_permutations(on_b, on_a - 1, True) <= k:
                k = k - count_stack_permutations(on_b, on_a - 1, True)
            else:
                action = 'a'
        # Taking from b is smaller than digging into b so I can take deeper.
        if action is None:
            if count_stack_permutations(on_b-1, on_a, True) <= k:
                k = k - count_stack_permutations(on_b-1, on_a, True)
            else:
                action = 'b'
        # Otherwise I will move.
        if action is None:
            if count_stack_permutations(on_b-1, on_a, False) < k:
                return None # Should never happen
            else:
                action = 'm'

        if action == 'a':
            answer.append(a.pop())
            can_take_from_a = True
        elif action == 'b':
            answer.append(b.pop())
            can_take_from_a = True
        else:
            a.append(b.pop())
            can_take_from_a = False
    return answer

# And demonstrate it in action.
for k in range(0, 6):
    print((k, find_kth_permutation(3, k)))

Upvotes: 1

Related Questions