algorithm - secret 圣诞老人-生成 'valid'排列

我的 friend 邀请我回家玩“ secret 圣诞老人”游戏，在游戏中我们应该吸引很多人并为小组中的 friend 扮演“圣诞老人”的角色。

因此，我们写下所有名称并随机选择一个名称。如果我们当中有人最终选择了自己的名字，那么我们将改组并重新选择名字(理由是人们不能成为自己的圣诞老人)。

我们比赛时有七个人，所以我认为最终的“圣诞老人分配”是对(1:7)本身的排列，但有一些限制。

我想就如何特别使用Mathematica或任何编程语言甚至算法来提出各种想法:

列出/打印所有“有效”圣诞老人分配

随着玩“ secret 圣诞老人”的 friend 数量的增加，可扩展性

最佳答案

我建议:

f[s_List] := Pick[#, Inner[SameQ, #, s, Nor]] & @ Permutations@s

f @ Range @ 4

{{2, 1, 4, 3}, {2, 3, 4, 1}, {2, 4, 1, 3}, {3, 1, 4, 2}, {3, 4, 1, 2},
 {3, 4, 2, 1}, {4, 1, 2, 3}, {4, 3, 1, 2}, {4, 3, 2, 1}}

This is significantly faster than Heike's function.

f @ Range @ 9; //Timing
secretSanta[9]; //Timing

{0.483, Null}

{1.482, Null}

Ignoring transparency of code, this can be made several times faster still:

f2[n_Integer] := With[{s = Range@n},
    # ~Extract~
       SparseArray[Times@@BitXor[s, #] & /@ #]["NonzeroPositions"] & @ Permutations@s
  ]

f2[9]; //Timing

{0.162，空}

关于algorithm - secret 圣诞老人-生成 'valid'排列，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8609644/