对元素进行随机排列，使得任何元素都不应出现在其原始索引处

我有一个对象元素列表

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

随机排列元素来源列表这样，任何元素都不应该出现在其原始索引处（在来源列表) in 结果列表.

例如，在来源列表C 位于索引 2，因此它一定不能位于以下索引中的索引 2结果列表

到目前为止，我已经研究过混乱维基 http://rosettacode.org/wiki/Permutations/Derangements#Java，但 algo 给了我可能的安排，而我只需要一个。

您可以使用费希尔-耶茨洗牌 http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_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 生成所有排列，并且我们仅使排列无效 -每一次调整都是可以实现的.
• The probability to get a dearrangement is 1/e¹, this means you are going to need (1-1/e)^-1 ~=1.56 shuffles on the average case, which means this algorithm runs in O(n) expected time complexity.

(1) 精神错乱的数量 http://en.wikipedia.org/wiki/Derangement#Counting_derangements is int(n!/e + 1/2)，这意味着数组发生重新排列的概率为(n!/e + 1/2)/n! ~= 1/e，对于较大的值n.