c# - 随机排列元素，使得任何元素都不应出现在其原始索引处

Question

我有一个对象元素列表

SourceList    ResultList (Expected)

Obj_A                 Obj_F

Obj_B                 Obj_C

Obj_C                 Obj_G

Obj_D                 Obj_B

Obj_E                 Obj_A

Obj_F                 Obj_B

Obj_G                 Obj_E

随机播放 SourceList 中的元素，这样，任何元素都不应出现在其原始索引处(在 SourceList 中)在 ResultList 中。

例如，在 SourceList 中，C 在索引 2 处，因此它不能出现在 ResultList 中的索引 2 处强>

到目前为止，我已经调查了Dearrangement Wiki ，但算法给了我可能的安排，我只需要一个。

Answer 1

您可以使用 fisher-yates shuffle作为一个黑盒子，重复打乱你的数组，直到你的结果是一个重新排列。

伪代码:

while true:
     arr = [1,2,...,n]
     shuffle(arr)
     flag = true
     for i from 0 to n:
        if arr[i] == i: //not a dearrangement
           flag = false 
     if flag == true: //it's a dearrangement
        break

shuffle(arr): //fisher yates
    for i from 0 to n:
       j = rand(i,n)
       swap(arr,i,j)

这种方法的特性:

• 这保证是统一且无偏的，因为每个有效的重新排列 在每次迭代中获得完全相同的选择几率。
• 由于 Fisher-Yates 生成所有排列，而我们仅使重新排列无效 - 每个重新排列都是可实现的。
• 获得重新排列的概率是 1/e¹，这意味着在平均情况下您将需要 (1-1/e)^-1 ~=1.56 次洗牌，这意味着此算法以O(n) 预期时间复杂度 运行。

---

(1) The number of dearrangements是int(n!/e + 1/2)，这意味着一个数组被重新排列的概率是(n!/e + 1/2)/n! ~= 1/e，对于较大的 n 值。