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

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，因此它不能出现在中的索引 2 结果列表

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

Answer 1

洗牌，得到所有索引不变的元素，然后轮换所有这些错误元素的位置。

Answer 2

这对我有用：

var SourceList = new List<string>()
{
    "Obj_A", "Obj_B", "Obj_C", "Obj_D", "Obj_E", "Obj_F", "Obj_G",
}; 

var rnd = new Random();

var ResultList =
    Enumerable
        // create an exceedingly long sequence for retries
        .Repeat(0, int.MaxValue)
        // select and randomly order all of the indices of `SourceList`
        .Select(_ => Enumerable.Range(0, SourceList.Count)
            .OrderBy(x => rnd.Next())
            .ToArray())
        // Discard the indices if they have any matching positions
        .Where(x => !x.Where((y, i) => y == i).Any())
        // only take one successful set of indices
        .Take(1)
        // flatten the list of lists to a list
        .SelectMany(x => x)
        // select the elements from `SourceList` from their index positions
        .Select(x => SourceList[x])
        // convert to list
        .ToList();

.OrderBy(x => rnd.Next()) 的使用产生了统一的排序（没有偏见）——我过去已经证实了这一点。

Answer 3

您可以将 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 的大值，数组是重新排列的概率是 (n!/e + 1/2)/n! ~= 1/e。

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

Shuffle element such that, no element should come at its original index

c#

random

algorithm

shuffle

permutation