岩石剪刀任意奇数元素

Question

如何有效地为n个元素创建一个摇滚剪纸游戏,其中n是任何奇数> = 3.

换句话说,我想要n个元素的非传递完全排序,使得每个元素大于(n-1)/ 2个其他元素,并且每个元素小于(n-1)/ 2个其他元素.

Answer 1

假设您的商品编号为0,1,2,...,n-1.

项目i击败项目j iff i - j (mod n) > (n-1)/2.

换句话说,您可以旋转列表,使您选择的项目位于列表的中间:

i - (n-1) / 2, ..., i-2, i-1, i, i+1, i+2, ..., i + (n-1) / 2

然后项目i击败列表中它下面的所有项目.

i vs j的矩阵看起来像这样:

  0 1 2 3 4
0 - L L W W
1 W - L L W
2 W W - L L
3 L W W - L
4 L L W W -

这不是唯一的可能性,但它可能是最简单的.您可以构建符合这些规则的任何矩阵:

• 对角线上的所有值均为零.
• 其他值为1或-1(赢,输).
• 它是一个倾斜的对称矩阵.
• 它在每行和每列中都有(n-1)/ 2个胜负.

这是另一个更复杂的例子:

  0 1 2 3 4
0 - L W W L
1 W - W L L
2 L L - W W
3 L W L - W
4 W W L L -

或者用另一种方式表达:

0 beats 2 and 3.
1 beats 0 and 2.
2 beats 3 and 4.
3 beats 1 and 4.
4 beats 0 and 1.

在该示例中,可以重新标记项目以给出与先前游戏中相同的逻辑.我怀疑这一点是否一般.