算法-使用重复的元素找到置换的中间

Question

我们在序列中有n个重复的符号。我想找到中间排列，如果它们按出现的符号排序：a: 2, b: 1, c: 1=>

1 aabc
2 abac
3 abca
4 acab
5 acba
6 baac !!!!
7 baca
8 bcaa
9 caab
10 caba
11 cbaa

中间是baac我可以在线性时间内找到它吗？另一个好的方法是找到中间排列的前k个符号。

通过这种方式，是为了优化算术编码。

Answer 1

您可以使用Factorial number system找到第n个排列。有关说明，请参见this帖子。