神秘圣诞老人 - 生成“有效”排列 [英] Secret Santa - Generating 'valid' permutations

问题描述

我的朋友邀请我家玩神秘圣诞老人，在这里我们应该借鉴了很多与放大器的游戏;玩'圣诞老人'的作用，为组中的朋友。

My friends invited me home to play the game of Secret Santa, where we are supposed to draw a lot & play the role of 'Santa' for a friend in the group.

所以，我们写我们所有的名字，并选择一个名称随机。如果我们任何人有自己的名字摘下来，然后我们重新洗牌，并一遍接名结束（其理由是，一个不能被自己圣诞老人）。

So, we write all our names and pick a name randomly. If any of us ends up having their own name picked, then we reshuffle and pick names all over again (the rationale being that one can not be one's own Santa).

有我们七个人同时玩，所以我想最后的圣诞老人分配作为一个置换（1：7）到自身，但有一些限制

There are seven of us while playing so I thought of the final 'Santa-allocation' as a permutation of (1:7) onto itself, with some restrictions.

我想请我们如何能在特定的或任何编程语言，甚至一种算法使用各种数学思想：

I would like to invite various ideas about how we could use Mathematica in particular or any programming language or even an algorithm to:

• 列表/打印出所有的有效圣诞老人分配
• 在具有可扩展性，作为朋友一起玩神秘圣诞老人的数量增长

推荐答案

我提出这样的：

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}

忽略的code透明性，这可快几倍犹言：

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, Null}

这篇关于神秘圣诞老人 - 生成“有效”排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！