python - 如何为 N 个骰子生成 "Go First"骰子？

Question

背景

如此处所述http://www.ericharshbarger.org/dice/#gofirst_4d12 , “先走”骰子是一组四个骰子，每个都有唯一的编号，因此:

• 任何两个或更多骰子都不会出现平局。
• 针对该组中的任何其他骰子掷出的任何骰子与该骰子“赢/输”的机会均等。

这里是提到的四个骰子的编号:

DICE COUNT: 4
FACE COUNT: 12
D1: 1,8,11,14,19,22,27,30,35,38,41,48
D2: 2,7,10,15,18,23,26,31,34,39,42,47
D3: 3,6,12,13,17,24,25,32,36,37,43,46
D4: 4,5, 9,16,20,21,28,29,33,40,44,45

(via)

问题

我不擅长数学。我很难过。鉴于上述信息，我希望能够在给定多个骰子的情况下生成整数列表(“骰子”)。这样，示例输出可能看起来像这样(格式化，python 控制台) :

    >>> generate_dice(players=4)
    [[1,8,11,14,19,22,27,30,35,38,41,48],
     [2,7,10,15,18,23,26,31,34,39,42,47],
     [3,6,12,13,17,24,25,32,36,37,43,46],
     [4,5,9,16,20,21,28,29,33,40,44,45]]    

这里的边数只是为了示例目的而选择的，因为它与给定的另一个示例相匹配。每个骰子的“公平性”正是我所追求的。

我向你保证这不是家庭作业。这只是一个坚定的极客，对一个看似微不足道的谜题感到恼火，这个谜题不会让我一个人呆着……而且出于某种原因，我似乎无法正确解决。

我确定这里涉及一些相对简单的数学和基本算法，而这正是我要寻找的。如果这对您来说很明显，我应该搜索什么术语？因为对我来说，它不是。

理想的解决方案是使用 Python，但我也可以很好地阅读 PHP、Javascript 和一些 Ruby。

Answer 1

这是一个(计算上的)难题。乍一看，每个骰子的预期值都相同是不够的(尽管奇怪的是，在您给出的示例中)。每个骰子必须“赢得”每个骰子元素点积的所有实例的 50%。

事实上，这篇文章提到一位数学家“手工”生成了您给出的示例，这让我更愿意建议以下蛮力方法:

import itertools

nplayers=4
nsides=2
max_number=8

assert nplayers*nsides <= max_number
assert nsides % 2 == 0 #otherwise x^x (dot product) is not even, so half_wins_fairness always fails

iterations=[]
def half_wins_fairness( dice1,dice2 ):
    dice1_wins= map( lambda x: x[0]>x[1], itertools.product(dice1,dice2) )
    dice_wins_prob= float(sum(dice1_wins))/len(dice1_wins)
    #probs.append(dice_wins_prob)
    return dice_wins_prob==0.5

def fair( all_dice ):
    all_fair= True
    for d1,d2 in itertools.combinations( all_dice, 2):
        if not half_wins_fairness(d1,d2):
            all_fair=False
    return all_fair

for i,dice_pattern in enumerate(itertools.permutations(range(max_number), nplayers*nsides)):
    #cut dice pattern into dices
    dice= [dice_pattern[p*nsides:(p+1)*nsides] for p in range(nplayers)]
    if fair(dice):
        print dice
        iterations.append(i)

def discrete_derivative(l):
    last=0
    for i,x in enumerate(l):
        tmp= x
        l[i]=x-last
        last=tmp

#discrete_derivative(iterations)
#import pylab
#pylab.plot(iterations)
#pylab.show()

这里的复杂度是 n^n，所以这本身只能解决非常少的 n 玩家和 n 边的问题。但是，通过取消对注释行的注释，您可以检查骰子在点积迭代中的公平性图，它似乎有很多模式，表明可以使用多种启发式方法来加速此搜索，甚至可能找到一个通用的解决方案。

编辑

更改了改进图形的代码。这里有一些图片，以防有人特别擅长发现模式。

nplayers=2, nsides=2, max_number=8 nplayers=2, nsides=4, max_number=8 nplayers=4, nsides=2, max_number=8

一些初步观察:

1. 它是对称的
2. “最干净”的图表似乎是在以下情况下生成的 max_number % (nplayers*nsides) == 0