Como posso gerar dados “Go First” para os dados?

9

Antecedentes

Como descrito aqui link , "Go First" Dice é um conjunto de quatro dados, cada um com numeração única, de modo que:

  • Qualquer jogada de dois ou mais dados nunca resultará em empate.
  • Qualquer dado lançado contra qualquer outro dado no set tem uma chance igual de "ganhar / perder" contra o dito dado.

Aqui está a numeração dos quatro dados mencionados:

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)

Pergunta

Eu fedo em matemática. Estou perplexo. Dada a informação acima, eu gostaria de ser capaz de gerar listas de inteiros ("dados"), dado um número de dados. Tal que, exemplo de saída pode parecer assim (formatado, console 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]]    

O número de lados aqui é escolhido apenas para fins de exemplo, porque corresponde ao outro exemplo dado. A "justiça" de cada dado é realmente o que eu procuro.

Garanto que isso não é lição de casa. Isto é simplesmente um nerd determinado, incomodado por um quebra-cabeça aparentemente trivial que simplesmente não me deixa em paz ... e, por algum motivo, parece que não consigo acertar.

Tenho certeza de que há alguma matemática relativamente trivial e um algoritmo básico envolvido aqui, e é isso que estou procurando. Que terminologia devo procurar, se isso é óbvio para você? Porque para mim, não é.

Idealmente, a solução seria em Python, mas eu também posso ler PHP, Javascript, algum Ruby, muito bem.

    
por anonymous coward 07.09.2012 в 23:44
fonte

2 respostas

5

Este é um problema difícil (computacionalmente). Não é suficiente, como pode parecer a princípio, que o valor esperado de cada dado seja o mesmo (embora seja curiosamente, no exemplo que você deu). É necessário que cada dado "ganhe" em 50% de todas as instâncias do produto escalar de cada elemento da matriz.

O fato de que o artigo refere que um matemático gerou o exemplo que você deu "à mão" me deixa um pouco mais confortável ao sugerir a seguinte abordagem de força bruta:

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()

A complexidade aqui é n ^ n, então isso, por si só, só resolve o seu problema para números muito baixos de nplayers e nsides. No entanto, descomentando as linhas comentadas, você pode inspecionar um gráfico da imparcialidade dos dados ao longo das iterações de produto de ponto, que parece ter muitos padrões, sugerindo que várias heurísticas podem ser usadas para acelerar essa pesquisa, ou talvez até mesmo encontrar uma solução geral.

EDITAR

alterou o código para gráficos aprimorados. Aqui estão algumas fotos, no caso de alguém ser particularmente adepto de identificar padrões.

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

Algumasobservaçõesiniciais:

  1. ésimétrico
  2. osgráficos"mais limpos" parecem ser gerados quando     max_number% (nplayers * nsides) == 0
por goncalopp 08.09.2012 / 23:53
fonte
0

Para o registro, essa resposta em codegolf tem um algoritmo simples que parece funcionar pelo menos a qualquer momento em que o número de lados nos dados for par: link

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
    
por anonymous coward 09.09.2012 / 03:29
fonte