[PYTHON] Eine Geschichte über das Finden des längsten Drucks einer bestimmten Wortgruppe durch Ignorieren der Pistole für den Berechnungsbetrag

Überblick

Ich habe versucht, ein Programm zu schreiben, um das längste Squeeze-Problem in Ruby zu lösen, ohne zu viel nachzudenken, aber der Rechenaufwand wurde zu groß und nutzlos, sodass ich einen Gedenkgottesdienst geben werde. Für nützliche Programme ist beispielsweise der folgende Artikel hilfreich.

• Ich habe versucht, ein Programm zu erstellen, das die längste Squeeze-Qiita sucht

Einzelheiten

Speichern Sie die Wortgruppe in words.txt. Zu diesem Zeitpunkt lautet der Zeichencode ** Shift JIS ** [^ 2].

words.txt

Gorira
Apfel
Panda
Rappa

[^ 2]: Um verstümmelte Zeichen zu vermeiden.

Implementierung

Schritt 1: Speichern Sie die Wortgruppe in einem Array

shiritori.rb

#Speichern Sie Wörter in einem Array
words = readlines(chomp: true)
p words

Ausführungsergebnis an der Eingabeaufforderung

>type words.txt | ruby shiritori.rb
["Gorira", "Apfel", "Panda", "Rappa"]

Schritt 2: Speichern Sie die Wortgruppe und den Anfang / das Ende jedes Wortes in einem Hash

shiritori.rb

#Speichern Sie Wörter in einem Array
words = readlines(chomp: true)

#Speichern Sie die Wortgruppe und den Anfang / das Ende jedes Wortes in einem Hash
words_ht = {}
words.each {|word|
    words_ht[word] = [word[0],word[word.length-1]]
}

p words_ht

Ausführungsergebnis an der Eingabeaufforderung

>type words.txt | ruby shiritori.rb
{"Gorira"=>["Gehen", "Et al."], "RiんGehen"=>["Ri", "Gehen"], "Panda"=>["Pa", "Ist"], "Et al.っPa"=>["Et al.", "Pa"]}

Schritt 3: Finden Sie die vollständige Reihenfolge der Wortgruppe und speichern Sie die hartnäckige im Hash zusammen mit der Anzahl der Wörter.

shiritori.rb

#Speichern Sie Wörter in einem Array
words = readlines(chomp: true)

#Speichern Sie die Wortgruppe und den Anfang / das Ende jedes Wortes in einem Hash
words_ht = {}
words.each {|word|
    words_ht[word] = [word[0],word[word.length-1]]
}

#Suchen Sie die vollständige Reihenfolge der Wortgruppe und speichern Sie die hartnäckige im Hash zusammen mit der Anzahl der Wörter.
shiritoris = {}
words.permutation(words.length) {|perm|
    shiritori = []
    n = 0
    while (n < perm.length-1 && words_ht[perm[n]][1] == words_ht[perm[n+1]][0]) do
        n += 1
    end
    for i in 0..n do
        shiritori += [perm[i]]
    end

    shiritoris[shiritori] = shiritori.length
}

p shiritoris

Ausführungsergebnis an der Eingabeaufforderung

>type words.txt | ruby shiritori.rb
{["Gorira"]=>1, ["Gorira", "Rappa"]=>2, ["Gorira", "Rappa", "Panda"]=>3, ["Apfel", "Gorira"]=>2, ["Apfel", "Gorira", "Et al.
Pappa", "Panda"]=>4, ["Apfel"]=>1, ["Panda"]=>1, ["らPappa"]=>1, ["らPappa", "Panda"]=>2}

Schritt 4: Geben Sie das mit der größten Anzahl von Wörtern in Shiritori aus

shiritori.rb

#Speichern Sie Wörter in einem Array
words = readlines(chomp: true)

#Speichern Sie die Wortgruppe und den Anfang / das Ende jedes Wortes in einem Hash
words_ht = {}
words.each {|word|
    words_ht[word] = [word[0],word[word.length-1]]
}

#Suchen Sie die vollständige Reihenfolge der Wortgruppe und speichern Sie die hartnäckige im Hash zusammen mit der Anzahl der Wörter.
shiritoris = {}
words.permutation(words.length) {|perm|
    shiritori = []
    n = 0
    while (n < perm.length-1 && words_ht[perm[n]][1] == words_ht[perm[n+1]][0]) do
        n += 1
    end
    for i in 0..n do
        shiritori += [perm[i]]
    end

    shiritoris[shiritori] = shiritori.length
}

#Gibt das mit der größten Anzahl von Wörtern in Shiritori aus
p shiritoris.max { |a, b| a[1] <=> b[1] }

Ausführungsergebnis an der Eingabeaufforderung

>type words.txt | ruby shiritori.rb
[["Apfel", "Gorira", "Rappa", "Panda"], 4]

Berechnungsbetrag

Da das obige Programm die vollständige Reihenfolge der Wortgruppen findet, berechnet es mindestens $ n! $ Für die Anzahl der Wörter $ n $. Wenn $ n $ groß ist, ist es daher völlig nutzlos. In der Tat, wenn Sie mit 151 Pokemon im Can Tho Bilderbuch rechnen

\log_{10}151!\fallingdotseq264.94

Die Berechnungsmenge beträgt $ 10 ^ {264.94} \ fallenddotseq8.7 \ times10 ^ {264} $ oder mehr [^ 1]. [^ 1]: Es ist zu groß, um einen Stift zu finden, aber es ist eine lächerliche Zahl, wenn man bedenkt, dass 1 unendliche Zahl 10 nach der 68. Potenz ist.

Bonus: In Python implementiert

Wenn Sie in Python ein ähnliches Programm wie oben schreiben, zum Beispiel: Beachten Sie, dass Python keine Arrays als Hash-Schlüssel verwendet.

shiritori.py

# -*- coding: utf-8 -*-
import codecs
import itertools

#Speichern Sie Wörter in einem Array
wordsfile = codecs.open('words.txt', 'r', 'utf-8')
words = wordsfile.read().split()

#Speichern Sie die Wortgruppe und den Anfang / das Ende jedes Wortes in einem Hash
words_ht = {}
for word in words:
    words_ht[word] = [word[0],word[len(word)-1]]

#Suchen Sie die vollständige Reihenfolge der Wortgruppe und speichern Sie die Liste zusammen mit der Anzahl der Wörter im Array.
wperms = list(itertools.permutations(words, len(words)))
shiritoris = []
for wperm in wperms:
    shiritori = []
    n = 0
    while (n < len(wperm)-1 and words_ht[wperm[n]][1] == words_ht[wperm[n+1]][0]):
        n += 1
    for i in range(0, n+1):
        shiritori += [wperm[i]]

    shiritoris += [shiritori]

#Gibt das mit der größten Anzahl von Wörtern in Shiritori aus
print(max(shiritoris))

words.txt

Waschbär
Katze
Fuchs
Schweinchen

Ausführungsergebnis an der Eingabeaufforderung

>python shiritori.py
['Katze', 'Schweinchen', 'Waschbär', 'Fuchs']