Der Akt, komplett mit dem Fuß eines anderen zu ringen. Lass uns Pokemon Shiritori! --Qiita
In dem Kommentar heißt es: "Ich denke, es ist schwierig, wenn Sie es nicht in ein Optimierungsproblem stecken." Ich schrieb.
Die Logik ist genau die gleiche wie in den Artikeln, die ich in der Vergangenheit geschrieben habe. Schauen Sie also bitte dort nach. Ich habe nach dem längsten Sendernamen in Python - Qiita gesucht
Das allein hat keinen Trick, also bin ich von nutzlos </ del> Python 2 zu Python 3 gewechselt.
Außerdem wurde die Regelung an die des ersten Artikels angepasst (geändert, um zwischen trüben und halbtrüben Punkten zu unterscheiden).
Ich werde die im ersten Artikel eingeführten Daten verwenden. (Alle 890 Tiere) https://github.com/towakey/pokedex/blob/master/pokedex.json
shiritori.py
#!/usr/bin/env python3
# modules
import sys
import itertools
import collections
import pulp
import json
#Normalisierte Tabelle
#Kleinbuchstaben->Großbuchstabe
regtable = dict(zip("Ayeo", "Aiueoya Yuyo"))
#Quelle (Anfang) und Senke (Ende)
SOURCE = "s"
SINK = "t"
##Eine Funktion, die einen geschlossenen Pfad durch einen bestimmten Punkt findet
##Die gefundenen gesperrten Straßen werden von den Rändern entfernt(Wenn nicht gefunden, lassen Sie es wie es ist)
def one_cycle(edges, start):
path = [start]
#Suche nach Tiefenpriorität (Stapel)
#Zählen Sie die Zweige von Anfang an auf
stack = [e[1] for e, cnt in edges.items() if e[0] == start and cnt > 0]
while len(stack) > 0:
#Wählen Sie einen Zweig
e_new = (path[-1], stack[-1])
edges[e_new] -= 1
path.append(stack[-1])
#Beenden Sie, wenn Sie zum ursprünglichen Punkt zurückkehren
if stack.pop() == start:
return path
#Listen Sie die Zweige ab dem aktuellen Punkt auf
dest_avail = [e[1] for e, cnt in edges.items() if e[0] == e_new[1] and cnt > 0]
if len(dest_avail) == 0:
#Sackgasse:1 Schritt zurückspulen
edges[e_new] += 1
path.pop()
else:
#Ziele auflisten
stack += dest_avail
#Ich konnte keine gesperrte Straße finden
return None
##Nehmen Sie die gesperrte Straße Euler heraus
def euler_cycle(edges, start):
edges_tmp = edges.copy()
#Finden Sie zuerst eine gesperrte Straße:Tiefenprioritätssuche(edges_Der geschlossene Pfad von tmp wird entfernt)
cycle = one_cycle(edges_tmp, start)
assert cycle is not None
cycle_add = cycle
while len(edges_tmp) > 0:
#Wählen Sie die Punkte auf der gesperrten Straße aus, an denen sich die verbleibenden Zweige befinden
next_start = [v for v in set(cycle) if any(e[0] == v and cnt > 0 for e, cnt in edges_tmp.items())]
if len(next_start) == 0:
#Gib auf, weil es eine andere Verknüpfungskomponente gibt
break
else:
#Finden Sie eine andere gesperrte Straße
cycle_add = one_cycle(edges_tmp, next_start[0])
assert cycle_add is not None
#Verbinden Sie sich mit dem ursprünglichen Verschluss am ausgewählten Startpunkt
idx = cycle.index(next_start[0])
cycle = cycle[:idx] + cycle_add + cycle[idx+1:]
return cycle
#Initialisieren Sie den Solver und legen Sie Einschränkungen fest
def make_solver(edges, vertexes, constraints):
solver = pulp.LpProblem("Shiritori", pulp.LpMaximize)
#Der zu jedem Zweig fließende Fluss entspricht einer Variablen
#Ganzzahlige Variable
variables = dict((e, pulp.LpVariable(e, lowBound=0, cat="Integer")) for e in edges.keys())
#Zielfunktion:Maximaler Gesamtdurchfluss
solver += sum(variables.values())
#Einschränkungen
#1 Durchfluss von der Quelle und 1 von der Senke
solver += sum([variables[e] for e in edges if e[0] == SOURCE]) == 1
solver += sum([variables[e] for e in edges if e[1] == SINK]) == 1
#Die Summe des ausgehenden Flusses und des eingehenden Flusses für jeden Scheitelpunkt stimmt überein(s,Anders als t)
for v in vertexes:
solver += sum([variables[e] for e in edges if e[0] == v]) \
== sum([variables[e] for e in edges if e[1] == v])
#Durchflussmengenbegrenzung
for e, maxflow in edges.items():
solver += 0 <= variables[e] <= maxflow
#Hinzufügen von Einschränkungen für die Verzweigungsbegrenzungsmethode
#"Es gibt einen oder mehrere Übergänge von einem im Zyklus enthaltenen Punkt zu einem anderen Punkt."
for cons in constraints:
solver += sum(variables[e] for e in cons) >= 1
return solver, variables
def main():
with open("pokedex.json", "r") as f:
pokedex = json.load(f)
pokemons = []
for p in pokedex:
#Lesen normalisieren
yomi_norm = "".join([regtable.get(c, c) for c in p["name"]])
if yomi_norm[-1] == "- -": yomi_norm = yomi_norm[:-1]
#Zur Zeit von Nidoran ♂, Nidoran ♀
yomi_norm = yomi_norm.replace("♂", "männlich")
yomi_norm = yomi_norm.replace("♀", "Weiblich")
#Beim Polygon 2
yomi_norm = yomi_norm.replace("2", "Tsu")
#Zum Zeitpunkt des Polygons Z.
yomi_norm = yomi_norm.replace("Z", "Zet")
pokemons.append((p["name"], yomi_norm, p["id"]))
##Erstellen eines Diagramms zum Rasieren
#Zweigliste (und Nummer):Gerichteter Graph
#Erstellen Sie auch eine Liste für jeden Zweig (erstes und letztes Zeichen)
edges = collections.defaultdict(int)
edges_pokemon = collections.defaultdict(set)
for name, yomi_norm, pokedex_id in pokemons:
t = (yomi_norm[0], yomi_norm[-1])
edges[t] += 1
edges_pokemon[t].add((name, pokedex_id))
#Quelle hinzufügen und synchronisieren
vertexes = set(itertools.chain(*edges.keys()))
for v in vertexes:
edges[(SOURCE, v)] = 1
edges[(v, SINK)] = 1
# *****
#Lösen Sie mit Integer-Programmierung als Maximum-Flow-Problem
length_tmp = 0
solution_tmp = None
constraints = []
while True:
solver, variables = make_solver(edges, vertexes, constraints)
solver.solve()
if solver.status != pulp.constants.LpStatusOptimal:
#Es gibt keine solche Lösung:Die aktuelle Lösung ist die endgültige Lösung
break
#Ausgenommen der Zweig, der aus s kommt, und der Zweig, der in t geht,
#Länge des Drucks (unter der Annahme, dass keine Sprünge vorhanden sind) (Anzahl der Wörter)
length_upper = int(pulp.value(solver.objective)+0.01) - 2
# *****
#Verarbeiten Sie das Ergebnis
#Listen Sie die zu verwendenden Zweige auf
#Der Einfachheit halber t->Fügen Sie den Pfad von s hinzu und halten Sie ihn geschlossen
#edges_sub = dict(itertools.ifilter(lambda _, sol: sol > 0,
# ((e, variables[e].value()) for e in edges.keys())))
edges_sub = dict((e, variables[e].value()) for e in edges.keys() if variables[e].value() > 0)
edges_sub[(SINK, SOURCE)] = 1
#Finde Euler geschlossen (fest auf s eingestellt, da du überall anfangen kannst)
cycle = euler_cycle(edges_sub, SOURCE)
# cycle: s -> X1 -> ... -> Xn -> t ->In s von X1 bis Xn->Die Nummer ist len(cycle)-4
length_lower = len(cycle) - 4
sys.stderr.write("{0}/{1} ".format(length_lower, length_upper))
if length_lower == length_upper:
#Verkettetes Diagramm
print("Verkettetes Diagramm", file=sys.stderr)
if length_tmp < length_lower:
#Lösungsupdate
length_tmp = length_lower
solution_tmp = cycle
#Bestätigt durch die aktuelle Lösung
break
else:
#Kein verketteter Graph
#Wenn Sie die Lösung nicht aktualisieren können, sind Sie fertig
print("Nicht verbundenes Diagramm", file=sys.stderr)
if length_upper <= length_tmp:
break
if length_tmp < length_lower:
#Zumindest habe ich eine bessere Lösung gefunden als die aktuelle
length_tmp = length_lower
solution_tmp = cycle
print("Versuchen Sie eine neue Lösung zu finden", file=sys.stderr)
#Ab dem nächsten Mal "gibt es einen oder mehrere Übergänge von im Zyklus enthaltenen Punkten zu anderen Punkten."
#Die Bedingung wurde hinzugefügt
vertexes_cycle = [v for v in vertexes if v in cycle]
vertexes_outofcycle = [v for v in vertexes if v not in cycle]
#Zählen Sie solche Übergänge auf
list_added_edges = [e for e in itertools.product(vertexes_cycle, vertexes_outofcycle) if e in edges]
if len(list_added_edges) == 0:
#Wenn es von Anfang an keinen solchen Übergang gibt, endet er
break
constraints.append(list_added_edges)
# *****
##In Liste konvertieren
print("Anzahl der Pokémon", length_tmp, file=sys.stderr)
for e1, e2 in zip(solution_tmp[1:-3], solution_tmp[2:-2]):
#Wählen Sie ein Pokemon aus und geben Sie es aus, das für die angegebenen ersten und letzten Zeichen gilt
used = edges_pokemon[(e1, e2)].pop()
print("{0} {1} {2:03d} {3}".format(e1, e2, used[1], used[0]))
if __name__ == "__main__":
main()
Es gibt nicht immer einen Weg, die längsten Shitori zu machen. Das Folgende ist ein Beispiel für den längsten Druck.
Pef 684 Pelo Puff
Farbton 795 Feroche
Eco 300 Eneko
Copo 875 Coo Lippo
Popo 016 Poppo
Poma 393 Poccama
Gemacht 851 Maruyakude
Deci 719 Diancy
Shii 773 Silvadi
Eva 826 Iolb
Buki 197 Blacky
Kiwa 764 Kuwawa
Wako 189 Watakko
Kodo 620 Kojondo
Doto 887 Drapart
Toga 365 Todozerga
Guy 058 Guardy
Ite 074 Ishitsubute
Theo 223 Teppo
Ome 277 Oosbame
Mema 469 Mega Yamma
Mami 069 Madatsubomi
Mitsu 150 Miu Zwei
Akupunkturpunkt 213 Akupunkturpunkt
Bora 306 Boss Godra
Rata 020 Rata
Tama 102 Tamatama
Maki 056 Mankey
Kipi 010 Caterpy
Phi Phi 035 Phi Phi
Pisi 036 Pixie
Ferida 090 Shelder
Dao 051 Doug Trio
Ome 021 Onisuzume
Mege 072 Meno Quallen
Gega 094 Genger
Rassel 105 Rassel
Raw 026 Light Chu
Bis 071 Utsubot
Maut 777 Togedemaru
Lula 124 Rougela
Roh 243 Raiko
Wui 059 Windig
Gute Nacht
Gut 557 Ishizumai
Iku 095 Iku
Kuna 044 Kusa Hana
Nasa 043 Nazonokusa
Sago 222 Sunnygo
Goki 067 Gorki
Kiki 203 Kirin Riki
Kiri 192 Kimawari
Lido 005 Eidechse
Dodo 084 Dodo
Doge 073 Dok Quallen
Gega 658 Geckouga
Gala 115 Garula
Las 754 Larantes
SK 123 Streik
Kuma 204 Kunugi Dama
Mata 296 McNosita
Tabo 273 Tanebo
Boss 642 Bolzenverlust
Suku 435 Suka Panzer
Kuto 169 Crobat
Werfen Sie 468 Togekiss
Sumi 121 Star Me
Mim 413 Minomadam
Schlamm 508 Moland
Dora 436 Dora Spiegel
Las 381 Latios
Sumi 406 Subomy
Michi 412 Minomucci
Chim 308 Charlem
Mudo 397 Mukubird
Dora 532 Dokkoler
Ruth 645 Landros
Spa 097 Schläfer
Paa 484 Parkia
Ada 617 Aguilder
Daki 539 Dageki
Kia 318 Kivania
Am 482 Agnom
Muru 238 Mouture
Ruri 298 Ruri
Lima 217 Ringma
Mad 756 Machade
Dochi 339 Dojotchi
Chim 421 Cherim
Muru 396 Muckle
Lupa 272 Runpapa
Pow 086 Pow Wow
Upa 194 Upa
Pato 047 Parasect
Toku 176 Togetic
Kuto 303 Kuchito
Topi 175 Togepy
Piyu 172 Pichu
Yushi 361 Yukiwarashi
Shira 117 Seedra
Ruth 380 Latias
Sp 434 Skampoo
Puru 592 Pururiru
Lua 249 Lugia
Ad 348 Armald
Dochi 886 Dronchi
Chi Chi 170 Jeong Chi
Chita 152 Chicorita
Tatsu 870 Tyrate
Tsutsukera 731 Tsutsukera
Ruth 280 Lars
Sp 096 Schlaf
Pra 142 Ptera
Ruth 370 Liebe Cass
Sua 015 Speer
Ama 283 Ametama
Mad 802 Marshadow
Dom 294 Dogome
Muma 200 Muuma
Mad 268 Mayurd
Doo 085 Dodrio
Ota 139 Omster
Tatsu 116 Tatsu
Tour 614 Thun Bär
Amo 255 Achamo
Moco 877 Morpeco
Koku 054 Kodak
Kubu 098 Club
Buba 126 Buba
Bada 323 Bakuda
Daz 476 Dy Nose
Zuto 041 Zubat
Toto 118 Tosakinto
Maut 011 Transel
Lula 792 Lunaara
Ruth 131 Laplace
Sua 769 Snubber
Atsushi 159 Alligatoren
Tsuya 495 Tsutaja
Yama 193 Yan Yanma
Mama 264 Massenbär
Mago 219 Magcalgo
Goya 076 Goronha
Yama 661 Yayakoma
Mashi 156 Magmarashi
Shira 561 Symboler
Raki 113 Glück
Kia 281 Kirlia
Aw 119 Azumaou
Uki 185 Usokki
Textur 278 Camome
Meco 551 Megroco
Kota 019 Collata
Tama 862 Tachifu Saguma
Mashi 655 Mafoxy
Kronleuchter Shira 609
Laa 045 Rafflesia
Abo 023 Abo
Boda 373 Bowmanda
Doug 275 Darting
Guga 207 Griger
Spur 537 Gamageroge
Gera 657 Gekogashira
Lara 608 Lampler
Rad 409 Rampard
Doya 885 Drameshiya
Yaya 854 Yabacha
Yade 850 Yakude
Dene 702 Dedenne
Nema 800 Necrozuma
Mani 739 Mackencani
Nibi 725 Nyaby
Bini 494 Victorini
In der Nähe von 700 Nymphia
Ayu 841 Apprew
Yumi 872 Yuki Hami
Miyu 778 Mimikyu
Yuko 478 Yukimenoko
Koff 619 Kojofu
Fube 669 Flavebe
Beba 859 Belover
Bani 871 Bachin Uni
Nima 431 Nyalmar
Maca 686 Maeika
Turtle 833 Cam Turtle
Meta 648 Meloetta
Octopus 852 Tatakko
Kaffee 580 Koalhee
Hika 829 Himenka
Turtle 834 Kajirigame
Meva 636 Meralba
Baya 710 Bucketcha
Yam 674 Yan Cham
Muna 890 Mugen Dyna
Nai 598 Natrey
Iko 744 Ivanko
Kori 527 Koromori
Lille 605 Wrigley
Reza 384 Wrack Uza
Zata 889 Die Magenta
Bambus 590 Tamagetake
Keso 265 Chemusso
Soo 791 Solgaleo
Oge 861 Oronge
Holen Sie sich 649 Genosect
Tra 364 Todogler
Ratte 310 Leibold
Werfen Sie 641 Torneros
Suda 849 Stringer
Daka 554 Dharmacca
Manschette 786 Kapu Tetefu
Fude 543 Fushide
Ded 225 geliefert
Doco 749 Dorobanco
Kori 528 Kokoromori
Hinten 470 Leafia
Aa 823 Rüstung Gaa
Ag 799 Akji King
Guya 768 Gusokumusha
Yaki 512 Yanacky
Kima 760 Kiteruguma
Mayo 618 Magyo
Yoshi 746 Yoshi
Sina 770 Shirodesuna
Naki 538 Nageki
Kigo 610 Kibago
Goda 812 Gorilander
Daro 524 Dangoro
Rom 479 Rotom
Muna 518 Mushana
Nara 328 Knuckler
Ratte 814 Rabbi Fuß
Werfen Sie 357 Tropius
Subi 843 Schlangenschlange
Viva 329 Vibrava
Bao 550 Baslao
Omo 752 Onishizu Spinne
Mou 873 Mosnow
Udo 793 Utsuroid
Dode 748 Dohideide
Deu 181 Denryu
Uu 845 Uu
Uu 692 Udeppou
Uchi 438 Uchi
Chiki 616 Chobo Maki
Kisa 286 Kinogassa
Saya 844 Sadaija
Yami 302 Yami Lami
Mimi 504 Minezumi
Mini 415 Mitsu Honig
Nizo 061 Nyorozo
Zor 570 Zoroa
Ayo 763 Amarjo
Yori 506 Yoteri
Lilu 447 Liol
Lulu 701 Lucable
Luo 404 Luxio
Odo 611 Onondo
Doro 691 Doramidro
Rod 407 Ros Raid
Doa 549 Dredia
Ako 762 Amamaiko
Koshi 401 Koroboshi
Shimo 751 Shizukumo
Moyu 529 Mogru
Yuo 460 Yukinoo
Oshi 234 Odoshishi
Schiff 682 Shushup
Puga 564 Protoga
Gas 689 Gamenodes
Suna 581 Swanna
Naro 287 Namakero
Untere 315 Roselia
Aji 761 Amakaji
Jigo 783 Jarango
Gobe 446 Gobe
Vor 153 Lorbeerblatt
Fute 425 Fute
Teya 797 Tekkaguya
Yag 199 Yad King
Gua 471 Gracia
Asche 736 Agojimushi
Shiko 667 Shiko
Koshi 664 Kofukimushi
Shigo 589 Chevalgo
Goyo 293 Gonyonyo
Yoku 164 Yornozuku
Kune 827 Kusune
Nera 775 Nekora
Lai 309 Lacrai
Ize 314 Ilmise
Zeka 523 Zebraika
Kate 688 Kametete
Ted 597 Tessed
Dotsu 533 Dotekkotsu
Tsude 805 Tunde Tunde
Deda 050 Digda
Daki 503 Daikenki
Kiko 285 Pilz
Koshi 767 Kosokumushi
Hirsch 585 Shikijika
Schlüssel 083 Camonegi
Gimo 860 Gimo
Mobo 465 Mojumbo
Bole 708 Boclay
Leva 165 Ladyba
Bab 325 Spring Boo
Buta 136 Booster
Samen 531 Tabunne
Neyu 755 Nemash
Yuri 459 Yuki Kaburi
Lira 345 Lira
Radi 260 Lag groß
Jiko 782 Jaraco
Photoshop 304 Cocodora
Ruth 579 Rankles
Skorpion 451 Skorpion
Piku 440 Pimpuku
Qui 707 Cleffi
Im 221 Innomu
Muna 517 Munna
Birne 771 Namakobushi
Shima 522 Shima
Mau 594 Mamanbow
Umu 220 Ulim
Muji 429 Muumaji
Jibi 496 Janobi
Bima 100 Billiri Dama
Machi 556 Malakacchi
Chino 573 Chiracino
Nochi 206 Nokochi
Cine 548 Chuline
Neo 178 Natio
Ochi 161 Otachi
Chico 509 Choroneko
Koku 402 Korotok
Spinne 690 Kuzmo
Moko 180 Mokoko
Koku 403 Kolink
Kuyu 541 Kurumayu
Yushi 480 Yukushi
Simi 492 Shaimi
Mim 856 Mim Brim
Muku 398 Muku Hawk
Kur 488 Creseria
Anu 730 Achilleine
Numa 759 Nuikoguma
Mähne 439 Mähne
Nein 177 Nati
Il 717 Ibertal
Luo 448 Lucario
Ochi 162 Otachi
Chibu 499 Chaobu
Buta 693 Broster
Tata 458 Tamanta
Tashi 363 Tamazarashi
Shiga 342 Shizariger
Gato 444 Gabite
Werfen Sie 411 Trideps
Sume 276 Subame
Meka 586 Mebukijika
Schlüssel 798 Kamitsurugi
Guido 681 Gilgard
Hund 454 Sklog
Guna 262 Graena
Birne 103 Nassie
Shizu 134 Duschen
Zugu 559 Zurugu
Guru 210 Grand Bull
Führen Sie 745 Lugargan aus
Recommended Posts