按字典顺序排序的堆栈排列

Question

数字 N 的堆栈排列定义为您可以通过执行以下操作打印的序列数

保留两个堆栈，比如 A 和 B。
将B中的数字从1倒序推入N。（所以B的顶部是1，B中的最后一个元素是N）
进行以下操作

从A或B中选择最前面的元素，打印并删除（弹出）。这只能在非空堆栈上完成。
将顶部元素从 B 移动到 A（如果 B 不为空）
如果两个堆栈都为空则停止

按某种顺序进行这些操作得到的所有可能序列称为stack permutations。

例如：N = 2
堆栈排列是 (1, 2) 和 (2, 1)
例如：N = 3
堆栈排列是 (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1) 和 (3, 2, 1)

N个数的堆栈排列数为C(N)，其中C(N)为第N个Catalan Number。

假设我们生成给定N的所有堆栈排列，然后按字典顺序（字典顺序）打印它们，我们如何确定第k个排列，而不是实际生成所有排列然后对它们进行排序？

我想要一些可编程的算法方法。

Answer 1

你没有说 k 应该基于 0 还是基于 1。我选择了0。切换回来很容易。

方法是先写一个函数来计算从给定的决策点开始有多少堆栈排列。使用记忆使其快速。然后通过跳过导致字典序更小的排列的决策，沿着决策树继续前进。这将导致您想要的决定列表。

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)))

Answer 2

这可以使用 factoradic(https://en.wikipedia.org/wiki/Factorial_number_system)

如果您需要 Java 中的快速解决方案，请使用 JNumberTools

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

这个API会直接按照字典顺序生成下一个第n个排列。因此，您甚至可以生成 100 个项目的下一个十亿次排列。

要生成给定大小的下一个第 n 个排列，请使用：

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

JNumberTools 的 Maven 依赖项是：

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

按字典顺序排序的堆栈排列

Stack permutations sorted in lexicographical order

algorithm

math

stack

permutation