python - 如何为 N 骰子生成“先行”骰子？

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

（通过）

问题

我讨厌数学。我难住了。鉴于上述信息，我希望能够在给定多个骰子的情况下生成整数列表（“骰子”）。这样，示例输出可能如下所示（格式化，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

这是一个（计算上）困难的问题。乍一看，每个骰子的预期值相同是不够的（尽管奇怪的是，在您给出的示例中）。每个 die 必须在每个 die 元素的点积的所有实例的 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 的数量非常少。但是，通过取消注释注释行，您可以检查骰子沿点积迭代的公平性图，该图似乎有很多模式，这表明可以使用几种启发式方法来加快搜索速度，甚至可能找到一个通用的解决方案。

编辑

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

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 时，似乎生成了“最干净”的图表

Answer 2

作为记录，这个答案codegolf有一个简单的算法，似乎至少在骰子上的边数是偶数的任何时候都有效：https ://codegolf.stackexchange.com/a/7238/5376

def generate_dice(count, sides = 12):
  dice = []
  for i in range(count):
    dice.append([])

  value = 0
  for sindex in range(sides):
    if sindex % 2:
      for dindex in range(count):
        value += 1
        dice[dindex].append(value)
    else:
      for dindex in reversed(range(count)):
        value += 1
        dice[dindex].append(value)
  return dice