数字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,3,3(、(1,3,2(、
N个数的堆栈排列的数目是C(N(，其中C(N(是第N个Catalan Number。
假设我们为给定的N生成所有堆栈排列，然后按字典顺序(字典顺序(打印它们，我们如何确定第k个排列，而不实际生成所有排列，然后对它们进行排序？
我想要一些可编程的算法方法。
您没有说明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)))
这可以使用因子分解(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>