algorithm - 排列从 1 到 100 的列表，使得对于任何索引 i，它映射到不等于 i 的 j

Question

在 python 中，什么是排列数字列表的优雅方法，使得对于所有元素，索引都不相同？

例如，[1,2,3] --> [3,1,2] 好[1,2,3] --> [1,3,2] 不正常。因为 1 映射到同一个 1。

有什么好的简单代码可以实现这一点？

Answer 1

这是一个遍历所有这些的迭代器。

#! /usr/bin/env python

def derangements (v):
    n = len(v)
    #print(("entering", v))
    if 0 == n:
        yield []
    elif 1 == n:
        pass # No derangements;
    elif 2 == n:
        # Special case not really needed.
        yield [v[1], v[0]]
    elif 3 == n:
        # Special case not really needed.
        yield [v[1], v[2], v[0]]
        yield [v[2], v[0], v[1]]
    else:
        for i in range(n-1):
            remaining = v[0:i] + v[i+1:n-1]
            # derangements where ith/last are a 2-cycle.
            for w in derangements(remaining):
                before = w[0:i]
                after = w[i:n-1]
                yield before + [v[n-1]] + after + [v[i]]
            # derangements where nth follows ith goes elsewhere
            for w in derangements(v[0:n-1]):
                before = w[0:i]
                after = w[i+1:n-1] if i < n-2 else []
                yield before + [v[n-1]] + after + [w[i]]


for d in derangements(range(5)):
    print(d)