[RUBY] Une histoire sur la recherche de la compression la plus longue d'un groupe de mots donné en ignorant le pistolet de calcul du montant

Aperçu

J'ai essayé d'écrire un programme pour résoudre le problème de compression le plus long de Ruby sans trop réfléchir, mais la quantité de calcul est devenue trop grande et elle est devenue inutile, alors je vais donner un service commémoratif. Pour les programmes utiles, par exemple, l'article suivant sera utile.

• J'ai essayé de faire un programme qui cherche le plus long squeeze-Qiita

Détails

Enregistrez le groupe de mots dans words.txt. À ce stade, le code de caractère est ** Shift JIS ** [^ 2].

words.txt

Gorira
pomme
Panda
Rappa

[^ 2]: pour éviter les caractères déformés.

la mise en oeuvre

Étape 1: enregistrer le groupe de mots dans un tableau

shiritori.rb

#Enregistrer les mots dans un tableau
words = readlines(chomp: true)
p words

Résultat de l'exécution à l'invite de commande

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

Étape 2: Enregistrez le groupe de mots et le début / la fin de chaque mot dans un hachage

shiritori.rb

#Enregistrer les mots dans un tableau
words = readlines(chomp: true)

#Enregistrez le groupe de mots et le début / la fin de chaque mot dans un hachage
words_ht = {}
words.each {|word|
    words_ht[word] = [word[0],word[word.length-1]]
}

p words_ht

Résultat de l'exécution à l'invite de commande

>type words.txt | ruby shiritori.rb
{"Gorira"=>["Aller", "Et al."], "RiんAller"=>["Ri", "Aller"], "Panda"=>["Pennsylvanie", "Est"], "Et al.っPennsylvanie"=>["Et al.", "Pennsylvanie"]}

Étape 3: Trouvez la séquence d'ordre complet du groupe de mots et enregistrez celui qui est têtu dans le hachage avec le nombre de mots.

shiritori.rb

#Enregistrer les mots dans un tableau
words = readlines(chomp: true)

#Enregistrez le groupe de mots et le début / la fin de chaque mot dans un hachage
words_ht = {}
words.each {|word|
    words_ht[word] = [word[0],word[word.length-1]]
}

#Trouvez la séquence d'ordre complet du groupe de mots et enregistrez celui qui est têtu dans le hachage avec le nombre de mots.
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

Résultat de l'exécution à l'invite de commande

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

Étape 4: Sortez celui avec le plus grand nombre de mots dans Shiritori

shiritori.rb

#Enregistrer les mots dans un tableau
words = readlines(chomp: true)

#Enregistrez le groupe de mots et le début / la fin de chaque mot dans un hachage
words_ht = {}
words.each {|word|
    words_ht[word] = [word[0],word[word.length-1]]
}

#Trouvez la séquence d'ordre complet du groupe de mots et enregistrez celui qui est têtu dans le hachage avec le nombre de mots.
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
}

#Produit celui avec le plus grand nombre de mots en Shiritori
p shiritoris.max { |a, b| a[1] <=> b[1] }

Résultat de l'exécution à l'invite de commande

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

Montant du calcul

Puisque le programme ci-dessus trouve la séquence complète de mots, il calcule au moins $ n! $ Pour chaque $ n $ de mots. Par conséquent, si $ n $ est grand, il est complètement inutile. En fait, si vous calculez avec 151 Pokémon dans le livre d'images de Can Tho

\log_{10}151!\fallingdotseq264.94

Le montant du calcul est de 10 $ ^ {264,94} \ falldotseq8,7 \ times10 ^ {264} $ ou plus [^ 1]. [^ 1]: C'est trop gros pour venir avec une épingle, mais c'est un nombre ridicule étant donné qu'un nombre infini équivaut à 10 à la 68e puissance.

Bonus: implémenté en Python

Si vous écrivez un programme similaire à celui ci-dessus en Python, par exemple: Notez que Python n'utilise pas de tableaux comme clés de hachage.

shiritori.py

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

#Enregistrer les mots dans un tableau
wordsfile = codecs.open('words.txt', 'r', 'utf-8')
words = wordsfile.read().split()

#Enregistrez le groupe de mots et le début / la fin de chaque mot dans un hachage
words_ht = {}
for word in words:
    words_ht[word] = [word[0],word[len(word)-1]]

#Recherchez l'ordre complet du groupe de mots et enregistrez la liste avec le nombre de mots du tableau.
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]

#Produit celui avec le plus grand nombre de mots en Shiritori
print(max(shiritoris))

words.txt

Raton laveur
Chat
Renard
Petit cochon

Résultat de l'exécution à l'invite de commande

>python shiritori.py
['Chat', 'Petit cochon', 'Raton laveur', 'Renard']