通过索引获取指定度的排列
我已经花了几个小时在这个问题上，但还是没搞明白。
这里说的“排列的度”是指为了得到一个排列，最少需要进行多少次交换。比如，(0, 1, 2, 3)的度是0，因为它已经是有序的；(0, 1, 3, 2)的度是1，因为只需要交换3和2一次；而(1, 0, 3, 2)的度是2，因为需要交换1和0，以及3和2。
我们把Snd看作是一个包含所有长度为n的排列的空间，这些排列的度是d。
我想要两个算法。一个是输入这个空间里的一个排列，给它分配一个索引号；另一个是输入Snd中某个项目的索引号，找出它对应的排列。索引号应该是连续的，也就是说在0到len(Snd)-1的范围内，每个排列都有一个独特的索引号。
我希望这个算法的效率是O(sane)；这意味着如果你想要第17个排列，算法不应该去检查0到16之间的所有排列来找出你的排列。
有没有什么办法可以解决这个问题？
（如果你要提供代码，我更喜欢Python，谢谢。）
更新：
我想要一个解决方案，其中：
- 这些排列是按照字典序排列的（不是手动排序，而是用一个高效的算法一开始就按字典序给出），
- 我希望算法能够接受不同度数的序列，这样我可以说“我想要在度数为1、3或4的排列空间中，获取第78个排列”。（基本上，这个函数会接受一个度数的元组。）这也会影响从排列计算索引的反向函数；根据度数的集合，索引会有所不同。
我已经尝试解决这个问题两天了，但没有成功。如果你能提供Python代码，那就太好了。
7 个回答
这看起来很有趣，所以我想了想。
我们以大卫的例子31042为例，来找出它的索引。首先，我们要确定“度”，这个度是指排列循环的数量之和，每个循环减去1。
01234
31042
permutation cycles (0342)(1)
degree = (4-1) + (1-1) = 3
def cycles(prefix):
_cycles = []
i = j = 0
visited = set()
while j < len(prefix):
if prefix[i] == i:
_cycles.append({"is":[i],"incomplete": False})
j = j + 1
i = i + 1
elif not i in visited:
cycle = {"is":[],"incomplete": False}
cycleStart = -1
while True:
if i >= len(prefix):
for k in range(len(_cycles) - 1,-1,-1):
if any(i in cycle["is"] for i in _cycles[k]["is"]):
cycle["is"] = list(set(cycle["is"] + _cycles[k]["is"]))
del _cycles[k]
cycle["incomplete"] = True
_cycles.append(cycle)
break
elif cycleStart == i:
_cycles.append(cycle)
break
else:
if prefix[i] == j + 1:
j = j + 1
visited.add(i)
if cycleStart == -1:
cycleStart = i
cycle["is"].append(i)
i = prefix[i]
while j in visited:
j = j + 1
i = j
return _cycles
def degree(cycles):
d = 0
for i in cycles:
if i["incomplete"]:
d = d + len(i["is"])
else:
d = d + len(i["is"]) - 1
return d
接下来，我们要计算有多少个度为3的排列是以0、1或2开头的；我们可以用大卫的公式来算：
number of permutations of n=5,d=3 that start with "0" = S(4,4-3) = 6
number of permutations of n=5,d=3 that start with "1" = S(4,4-2) = 11
[just in case you're wondering, I believe the ones starting with "1" are:
(01)(234)
(01)(243)
(201)(34)
(301)(24)
(401)(23)
(2301)(4)
(2401)(3)
(3401)(2)
(3201)(4)
(4201)(3)
(4301)(2) notice what's common to all of them?]
number of permutations of n=5,d=3 that start with "2" = S(4,4-2) = 11
我们在想，是否可能存在一个字典序更小的度为3的排列，它也以“310”开头。唯一的可能性似乎是31024：
01234
31024 ?
permutaiton cycles (032)(4)(1)
degree = (3-1) + (1-1) + (1-1) = 2
since its degree is different, we will not apply 31024 to our calculation
以“3”开头的、字典序小于31042的度为3的排列必须以“30”作为前缀。它们的数量等于我们在排列循环中保持“3”在“0”之前，以及“0”在“1”之前的方式，同时保持循环的数量之和（每个减去1，即度）为3。
(031)(24)
(0321)(4)
(0341)(2)
count = 3
看起来在31042之前，有6 + 11 + 11 + 3 = 31个n=5，d=3的排列。
def next(prefix,target):
i = len(prefix) - 1
if prefix[i] < target[i]:
prefix[i] = prefix[i] + 1
elif prefix[i] == target[i]:
prefix.append(0)
i = i + 1
while prefix[i] in prefix[0:i]:
prefix[i] = prefix[i] + 1
return prefix
def index(perm,prefix,ix):
if prefix == perm:
print ix
else:
permD = degree(cycles(perm))
prefixD = degree(cycles(prefix))
n = len(perm) - len(prefix)
k = n - (permD - prefixD)
if prefix != perm[0:len(prefix)] and permD >= prefixD:
ix = ix + S[n][k]
index(perm,next(prefix,perm),ix)
S = [[1]
,[0,1]
,[0,1,1]
,[0,2,3,1]
,[0,6,11,6,1]
,[0,24,50,35,10,1]]
（让我们试着用大卫的程序确认一下，我在用Windows的电脑）：
C:\pypy>pypy test.py REM print(index([3,1,0,4,2],[0],0))
31
C:\pypy>pypy davids_rank.py REM print(rank(5,{3},[3,1,0,2,4]))
31
我觉得你想要的是一种变体，类似于莱文斯坦距离，这个概念用来衡量两个字符串之间需要多少次编辑。计算这个距离的高效方法是使用一种叫做动态规划的技术——在链接的文章中提供了一种“普通”莱文斯坦距离的伪算法。你需要对这个算法进行调整，因为在你的情况下，允许的操作不是添加、删除或替换字符，而是交换两个位置的元素。
关于你的第二个算法：排列的程度和“a”所产生的排列之间并不是一对一的关系，而是可能的结果数量随着交换次数的增加而呈指数增长：对于一个包含k个元素的序列，有k*(k-1)/2对可以交换的索引。如果我们把这个数字称为l，那么经过d次交换后，你会有l^d种可能的结果（尽管其中一些可能是相同的，比如先交换0和1，然后再交换2和3，或者先交换2和3，再交换0和1）。
我在StackOverflow上写了一个关于类似问题的回答，你可以看看这个链接：https://stackoverflow.com/a/13056801/10562。这可能对你有帮助吗？
可能的区别在于生成排列时的交换位，但这里提供了一个从索引到排列和从排列到索引的函数，都是用Python写的。
后来我还创建了这个Rosetta Code的任务，里面有更多的参考资料和代码：http://rosettacode.org/wiki/Permutations/Rank_of_a_permutation。
希望对你有帮助 :-)
长度为 n 和度数为 d 的排列，实际上就是可以写成 k = n - d 个循环的组合，这些循环把 n 个元素分开。这样的排列数量可以用一种叫做“第一类斯特林数”的数学概念来表示，通常用 n 在上，k 在下的方括号表示。
第一类斯特林数满足一个递推关系
[n] [n - 1] [n - 1]
[ ] = (n - 1) [ ] + [ ]
[k] [ k ] [k - 1],
这意味着，从直观上看，把 n 个元素分成 k 个循环的方式，可以通过把 n - 1 个非最大元素分成 k 个循环，然后把最大元素插入到 n - 1 种方式中的一种，或者把最大元素放在自己的循环里，再把 n - 1 个非最大元素分成 k - 1 个循环来实现。从递推值的表格中，我们可以追踪这些决策的过程。
memostirling1 = {(0, 0): 1}
def stirling1(n, k):
if (n, k) not in memostirling1:
if not (1 <= k <= n): return 0
memostirling1[(n, k)] = (n - 1) * stirling1(n - 1, k) + stirling1(n - 1, k - 1)
return memostirling1[(n, k)]
def unrank(n, d, i):
k = n - d
assert 0 <= i <= stirling1(n, k)
if d == 0:
return list(range(n))
threshold = stirling1(n - 1, k - 1)
if i < threshold:
perm = unrank(n - 1, d, i)
perm.append(n - 1)
else:
(q, r) = divmod(i - threshold, stirling1(n - 1, k))
perm = unrank(n - 1, d - 1, r)
perm.append(perm[q])
perm[q] = n - 1
return perm
这个回答虽然没有我其他的回答那么优雅或高效，但它描述了一种多项式时间的算法，可以处理排列顺序的额外约束。我将介绍一个子程序，给定一个n个元素的排列前缀和一组度数，它可以计算有多少个排列以该前缀开始，并且其度数属于这个集合。通过这个子程序，我们可以进行n元搜索，找到指定子集中指定等级的排列，每次扩展已知前缀一个元素。
我们可以把n个元素的排列p想象成一个有n个顶点和n条弧的有向图，其中每个顶点v都有一条弧指向p(v)。这个有向图由一组不相交的循环组成。例如，排列31024看起来像这样：
_______
/ \
\->2->0->3
__ __
/ | / |
1<-/ 4<-/ .
给定一个排列的前缀，我们可以想象与该前缀对应的子图，这将是一些不相交的路径和循环。例如，前缀310看起来像这样：
2->0->3
__
/ |
1<-/ .
我将描述一个一一对应关系，连接（1）这个前缀的扩展（它们是排列）和（2）在相关元素集合上的完整排列。这种一一对应关系在常数项的范围内保持循环的数量（即元素的数量减去度数）。常数项就是前缀中的循环数量。
在（2）中提到的排列是基于以下元素集合。首先从原始集合开始，删除所有在前缀中完整的循环所涉及的元素，并为每条路径引入一个新元素。例如，如果前缀是310，那么我们删除完整循环1，并为路径2->0->3引入一个新元素A，结果得到集合{4, A}。现在，给定集合（1）中的一个排列，我们通过删除已知的循环并用新元素替换每条路径来获得集合（2）中的排列。例如，排列31024对应于排列4->4，A->A，而排列31042对应于排列4->A，A->4。我声称（1）这个映射是一一对应的，（2）它保持之前描述的度数。
第一类斯特林数的定义，大致上是这样的，写作：
[n]
[ ]
[k]
（ASCII艺术方括号），它表示n个元素的排列中度数为n-k的数量。要计算n个元素排列中r个元素前缀的扩展数量，先计算c，即前缀中的完整循环数量。然后，对于指定集合中的每个度数d，求和第一类斯特林数：
[ n - r ]
[ ]
[n - d - c]
对于“不可行”索引的项取值为零（一些分析上动机的斯特林数定义在意想不到的地方是非零的）。
要从排列中获得一个等级，我们再次进行n元搜索，不过这次我们使用排列而不是等级来指导搜索。
这里有一些Python代码，包括一个测试函数。
import itertools
memostirling1 = {(0, 0): 1}
def stirling1(n, k):
ans = memostirling1.get((n, k))
if ans is None:
if not 1 <= k <= n: return 0
ans = (n - 1) * stirling1(n - 1, k) + stirling1(n - 1, k - 1)
memostirling1[(n, k)] = ans
return ans
def cyclecount(prefix):
c = 0
visited = [False] * len(prefix)
for (i, j) in enumerate(prefix):
while j < len(prefix) and not visited[j]:
visited[j] = True
if j == i:
c += 1
break
j = prefix[j]
return c
def extcount(n, dset, prefix):
c = cyclecount(prefix)
return sum(stirling1(n - len(prefix), n - d - c) for d in dset)
def unrank(n, dset, rnk):
assert rnk >= 0
choices = set(range(n))
prefix = []
while choices:
for i in sorted(choices):
prefix.append(i)
count = extcount(n, dset, prefix)
if rnk < count:
choices.remove(i)
break
del prefix[-1]
rnk -= count
else:
assert False
return tuple(prefix)
def rank(n, dset, perm):
assert n == len(perm)
rnk = 0
prefix = []
choices = set(range(n))
for j in perm:
choices.remove(j)
for i in sorted(choices):
if i < j:
prefix.append(i)
rnk += extcount(n, dset, prefix)
del prefix[-1]
prefix.append(j)
return rnk
def degree(perm):
return len(perm) - cyclecount(perm)
def test(n, dset):
for (rnk, perm) in enumerate(perm for perm in itertools.permutations(range(n)) if degree(perm) in dset):
assert unrank(n, dset, rnk) == perm
assert rank(n, dset, perm) == rnk
test(7, {2, 3, 5})