Sie können auch Kombinationsoptimierung verwenden, um festzustellen, ob Sie Mahjong spielen können. Der Einfachheit halber werde ich nur überlegen, ob es sich um eine erhabene Form handelt (ein Spatzenkopf und drei Gesichter). Darüber hinaus ist Makiko ebenfalls ausgeschlossen.
| Variablen | $ x_i \ in \ {0, 1 \} $ | $ x_i $: $ i $ Gibt an, ob der dritte Kandidat ausgewählt werden soll |
| Einschränkungen | $ \ sum_i {a_ {ij} x_i} = 1 ~ ~ \ forall j \ le 13 $ | $ a_ {ij} $: Gibt an, ob der $ i $ -te Kandidat 牌 $ j $ enthält weniger |
Dieses Problem ist ein Satzteilungsproblem.
python3
def calc(hai):
import pandas as pd
from itertools import combinations, product
from pulp import LpProblem, LpBinary, LpVariable, lpSum, value
cand = [] #Kandidat
a = pd.DataFrame(sorted(hai), columns=['v'])
b = a.v.value_counts()
for i in b[b >= 2].index: #Sparrow Head Candidate Creation
cand.extend(combinations(a[a.v == i].index, 2))
n2 = len(cand)
for i in b[b >= 3].index: #Erstellen Sie Gravurkandidaten
cand.extend(combinations(a[a.v == i].index, 3))
c = a.v.unique()
for i in range(len(c)-2): #Erstellung von Junko-Kandidaten
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() #Mathematisches Modell
v = [LpVariable('v%d'%i, cat=LpBinary) for i in range(len(cand))] #Variable
m += lpSum(v[:n2]) == 1 #Ein Spatzenkopf
d = [[] for _ in range(14)] #Liste der Kandidatennummern nach Kachel
for i, ca in enumerate(cand):
for j in ca:
d[j].append(v[i])
for i in d:
m += lpSum(i) == 1 #Alle Kacheln sind eins in jedem Kandidaten
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]
Lassen Sie uns tatsächlich berechnen.
python3
def show(n):
if n < 30:
return chr(ord('１')+n%10)+'Mantsubo'[n//10]
return 'Von Osten, Westen, Norden, Süden und Weiß'[n//2-16]
hai = [0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 8, 8] #14 Fliesen
for i in calc(hai):
for j in i: print(show(j))
print()
>>>
1 Mann
1 Mann
9 Mann
9 Mann
9 Mann
1 Mann
2 Mann
3 Mann
4 Mann
5 Mann
6 Mann
7 Mann
8 Mann
9 Mann
Ich konnte den Spatzenkopf und das Gesicht richtig finden.
das ist alles
Recommended Posts