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

Question

背景

如http://www.ericharshbarger.org/dice/#gofirst_4d12所述,"Go First"骰子是一组四个骰子,每个骰子都有唯一的编号,因此:

• 任何两个或更多骰子的掷骰都不会产生平局.
• 任何与模具中的任何其他模具相对的模具都有相同的机会"赢/输"所述模具.

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

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

(通过)

题

我很擅长数学.我很难过.鉴于上述信息,我希望能够在给定多个骰子的情况下生成整数列表("骰子").这样,示例输出可能看起来像这样(格式化,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,所以这本身只能解决你的nplayers和nsides数量非常少的问题.但是,通过取消注释注释行,您可以检查骰子沿着dot产品迭代的公平性图,这似乎有很多模式,表明可以使用几种启发式来加速此搜索,甚至可能找到一般解决方案.

编辑

改变了改进图形的代码.这里有一些照片,以防有人特别擅长发现模式.

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时,似乎会生成"最干净"的图形