Juger la finition du mahjong par l'optimisation des combinaisons

Introduction

Vous pouvez également utiliser Optimisation de combinaison pour déterminer si vous pouvez jouer au mahjong. Par souci de simplicité, je vais simplement examiner s'il s'agit d'une forme en relief (une tête de moineau et trois faces). De plus, Makiko est également exclue.

le terme

--Jantou: Deux tuiles identiques

  • Mentions: Junko, Kiko ou Mako --Shunz: Trois tuiles du même type disposées dans l'ordre
  • Manteaux: 3 mêmes tuiles --Kants: 4 mêmes tuiles
  • Forme de montée: 1 tête de moineau et 4 faces

Idées et formulation

--Il n'y a pas de fonction objective car on considère si la condition est satisfaite.

  • En utilisant les tuiles données, énumérez les combinaisons qui seront le fer de lance ou Junko ou Gravure, et faites-en des candidats. ――Choisissez bien un candidat pour que toutes les tuiles apparaissent exactement une fois. --Choisissez exactement une tête de moineau.
Variables $ x_i \ in \ {0, 1 \} $ $ x_i $: $ i $ Choix du troisième candidat
Contraintes $ \ sum_i {a_ {ij} x_i} = 1 ~ ~ \ forall j \ le 13 $ $ a_ {ij} $: si le $ i $ ème candidat contient 牌 $ j $ Moins

Ce problème est un problème de division fixe.

Exemple d'exécution par Python

--Mahjong tuiles Manz (0-8), Tsutsuko (Pins) (10-18), Swords (20-28), Kazehai (30,32,34, 36), je vais le représenter avec les nombres de Sangenpai (38,40,42). En faisant cela, Junko est toujours continu, et s'il est continu, il devient Junko. --Définissez une fonction calc qui prend 14 tuiles (variable hai) comme entrée et renvoie 5 têtes ou faces de moineau.

python3


def calc(hai):
    import pandas as pd
    from itertools import combinations, product
    from pulp import LpProblem, LpBinary, LpVariable, lpSum, value
    cand  = [] #Candidat
    a = pd.DataFrame(sorted(hai), columns=['v'])
    b = a.v.value_counts()
    for i in b[b >= 2].index: #Création d'un candidat tête de moineau
        cand.extend(combinations(a[a.v == i].index, 2))
    n2 = len(cand)
    for i in b[b >= 3].index: #Créer des candidats à la gravure
        cand.extend(combinations(a[a.v == i].index, 3))
    c = a.v.unique()
    for i in range(len(c)-2): #Création de candidats Junko
        if c[i+1] - c[i] == c[i+2] - c[i+1] == 1:
            cand.extend(product(a.index[a.v==c[i]],
                                a.index[a.v==c[i+1]],
                                a.index[a.v==c[i+2]]))
    m = LpProblem() #Modèle mathématique
    v = [LpVariable('v%d'%i, cat=LpBinary) for i in range(len(cand))] #variable
    m += lpSum(v[:n2]) == 1 #Une tête de moineau
    d = [[] for _ in range(14)] #Liste des numéros de candidats par tuile
    for i, ca in enumerate(cand):
        for j in ca:
            d[j].append(v[i])
    for i in d:
        m += lpSum(i) == 1 #Toutes les tuiles sont une dans n'importe quel candidat
    if m.solve() != 1: return None
    return [[a.v[j] for j in cand[i]] for i, vv in enumerate(v) if value(vv) > 0.5]

Calculons réellement.

python3


def show(n):
    if n < 30:
        return chr(ord('1')+n%10)+'Mantsubo'[n//10]
    return 'De l'est, de l'ouest, du nord et du sud'[n//2-16]

hai = [0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 8, 8] #14 tuiles
for i in calc(hai):
    for j in i: print(show(j))
    print()
>>>
1 homme
1 homme

9 Homme
9 Homme
9 Homme

1 homme
2 homme
3 homme

4 homme
5 Homme
6 Homme

7 Homme
8 Homme
9 Homme

J'ai pu trouver correctement la tête et le visage du moineau.

c'est tout

Recommended Posts