J'ai un ensemble de morbes valides possibles, je peux utiliser pour diviser un texte (si possible). p> Comment puis-je diviser un texte donné en utilisant ces Les morceaux tels que le résultat seront optimisés (minimisés) en termes de nombre de morceaux résultants? p> Suite Test forte> p> if __name__ == "__main__":
import random
import sys
random.seed(1)
# 1) Testing robustness
examples = []
sys.stdout.write("Testing correctness...")
N = 50
large_number = "3141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481"
for i in range(100):
for j in range(i):
choices = random.sample(range(i), j)
examples.append((choices, large_number))
for (choices, large_number) in examples:
get_it_done(choices, large_number)
sys.stdout.write("OK")
# 2) Testing correctness
examples = [
# Example1 ->
# Solution ['012345678910203040506070', '80', '90', '100', '200', '300', '400', '500', '600', '700', '800', '900']
(
[
"0", "1", "2", "3", "4", "5", "6", "7", "8", "9",
"10", "20", "30", "40", "50", "60", "70", "80", "90",
"100", "200", "300", "400", "500", "600", "700", "800", "900",
"012345678910203040506070"
],
"0123456789102030405060708090100200300400500600700800900"
),
# Example2
## Solution ['100']
(
["0", "1", "10", "100"],
"100"
),
# Example3
## Solution ['101234567891020304050', '6070809010020030040050', '0600700800900']
(
[
"10", "20", "30", "40", "50", "60", "70", "80", "90",
"012345678910203040506070",
"101234567891020304050",
"6070809010020030040050",
"0600700800900"
],
"10123456789102030405060708090100200300400500600700800900"
),
# Example4
### Solution ['12', '34', '56', '78', '90']
(
[
"12", "34", "56", "78", "90",
"890",
],
"1234567890"
),
# Example5
## Solution ['12', '34']
(
[
"1", "2", "3",
"12", "23", "34"
],
"1234"
),
# Example6
## Solution ['100', '10']
(
["0", "1", "10", "100"],
"10010"
)
]
score = 0
for (choices, large_number) in examples:
res = get_it_done(choices, large_number)
flag = "".join(res) == large_number
print("{0}\n{1}\n{2} --> {3}".format(
large_number, "".join(res), res, flag))
print('-' * 80)
score += flag
print(
"Score: {0}/{1} = {2:.2f}%".format(score, len(examples), score / len(examples) * 100))
# 3) TODO: Testing optimization, it should provide (if possible)
# minimal cases
4 Réponses :
Utilisation de la programmation dynamique, vous pouvez construire une liste (l0, l1, l2, ... ln-1) code>, où n code> est le nombre de caractères de votre String d'entrée et LI code> est le nombre minimum de morceaux que vous devez arriver au caractère i code> de la chaîne d'entrée. La structure générale ressemblerait comme suit: choices = ["0","1","10","100"]
text = "10010"
algorithm step content of minValues
0 1 2 3 4
---------------------------------------------------------
initialize (∞, ∞ , ∞ , ∞ , ∞ )
i = 0, c = "1" (1 "1", ∞ , ∞ , ∞ , ∞ )
i = 1, c = "0" (1 "1", 2 "0", ∞ , ∞ , ∞ )
i = 1, c = "10" (1 "1", 1 "10", ∞ , ∞ , ∞ )
i = 2, c = "0" (1 "1", 1 "10", 2 "0", ∞ , ∞ )
i = 2, c = "100" (1 "1", 1 "10", 1 "100", ∞ , ∞ )
i = 3, c = "1" (1 "1", 1 "10", 1 "100", 2 "1", ∞ )
i = 4, c = "0" (1 "1", 1 "10", 1 "100", 2 "1", 3 "0" )
i = 4, c = "10" (1 "1", 1 "10", 1 "100", 2 "1", 2 "10")
Je regarde le cas où l'entrée [0..i] ne peut pas être composée des choix, et cela semble être correct. Vous ignorez simplement le suffixe inutilisable jusqu'à ce que vous arriviez à quelque chose qui puisse la composer à une fois plus tard. Et si le problème n'est pas solvable, nous savons qu'en comparant la réponse finale reconstruite avec la chaîne d'entrée. D'accord?
@BPL: une implémentation facile (sans la trie) serait la suivante: Pour chaque choix C Cochez la suivante: est le dernier caractère de C = entrée [ i] , le second dernier = entrée [I-1] et ainsi de suite jusqu'à ce que C est complètement consommé.
@Kenny YES, chaîne partielle qui ne peut pas être composée séjour au ∞ . Un moyen plus facile de vérifier si la chaîne entière est composable vérifie minvalues [n-1] pour ∞ .
@Nico Une chaîne pourrait ne pas être compostible quelque part au milieu, mais peut avoir un préfixe compostible et un suffixe. Il semble que cela soit non détecté jusqu'à la reconstruction finale (qui ne correspondra pas à la chaîne d'entrée). Mais cela obtient toujours la réponse, +1
@Bpl: Il pourrait y avoir une solution avec un arbre suffixe modifié, mais je n'ai pas de bonne idée pour cela. Un arbre suffixe est également une trie comme je l'ai suggéré pour la récupération de suffixe. Alors peut-être que vous pourriez avoir les deux structures ensemble de manière intelligente. Mais je ne sais pas.
@Kenny the Minvalues indique le nombre de morceaux que vous devez composer entrée [0..i] (c'est-à-dire le préfixe jusqu'à i i ). Par conséquent, si une entrée n'est pas ∞, vous savez que le préfixe correspondant est composable. Minvalues [N-1] correspond au préfixe jusqu'au dernier caractère, c'est-à-dire à la chaîne d'entrée complète. S'il s'agit d'un numéro valide, vous savez que la chaîne d'entrée complète peut être composée.
Mais vous ne le mettez à la mettre à jour que pour les candidats qui sont un suffixe correspondant. Oh ... je vois maintenant. Cela laissera «non» là-bas, mais la plus tard, attrapez les matchs précédents dans la recherche sur I-Len (candidat). Il est donc plus facile de détecter «insoluble» que je pensais.
def find_shortest_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
return path
if start not in graph:
return None
shortest = None
for node in graph[start]:
if node not in path:
newpath = find_shortest_path(graph, node, end, path)
if newpath:
if not shortest or len(newpath) < len(shortest):
shortest = newpath
return shortest
def get_it_done(choices, number):
mapping = {}
graph = {}
for choice in choices:
if choice in number:
_from = number.index(choice)
_to = _from + len(choice)
mapping.setdefault((_from, _to), choice)
items = sorted(mapping.items(), key=lambda x: x[0])
for _range, value in items:
_from, _to = _range
graph.setdefault(_from, []).append(_to)
start = 0
end = _range[1] #this is hack, works only in python 2.7
path = find_shortest_path(graph, start, end)
ranges = [tuple(path[i:i+2]) for i in range(len(path) - 1)]
if len(ranges) == 1:
items = sorted(choices, key=len, reverse=True)
number_length = len(number)
result = ''
for item in items:
result += item
if len(result) == number_length:
return result
return [mapping[_range] for _range in ranges]
if __name__ == "__main__":
examples = [
# Example1 ->
# Solution ['012345678910203040506070', '80', '90', '100', '200', '300', '400', '500', '600', '700', '800', '900']
(
[
"0", "1", "2", "3", "4", "5", "6", "7", "8", "9",
"10", "20", "30", "40", "50", "60", "70", "80", "90",
"100", "200", "300", "400", "500", "600", "700", "800", "900",
"012345678910203040506070"
],
"0123456789102030405060708090100200300400500600700800900"
),
## Example2
## Solution ['100']
(
["0", "1", "10", "100"],
"100"
),
## Example3
## Solution ['101234567891020304050', '6070809010020030040050', '0600700800900']
(
[
"10", "20", "30", "40", "50", "60", "70", "80", "90",
"012345678910203040506070",
"101234567891020304050",
"6070809010020030040050",
"0600700800900"
],
"10123456789102030405060708090100200300400500600700800900"
),
### Example4
### Solution ['12', '34', '56', '78', '90']
(
[
"12", "34", "56", "78", "90",
"890",
],
"1234567890"
),
## Example5
## Solution ['12', '34']
(
[
"1", "2", "3",
"12", "23", "34"
],
"1234"
),
# Example6
## Solution ['100', '10']
(
["0", "1", "10", "100"],
"10010"
)
]
score = 0
for (choices, large_number) in examples:
res = get_it_done(choices, large_number)
flag = "".join(res) == large_number
print("{0}\n{1}\n{2} --> {3}".format(
large_number, "".join(res), res, flag))
print('-' * 80)
score += flag
print(
"Score: {0}/{1} = {2:.2f}%".format(score, len(examples), score / len(examples) * 100))
get_it_done function creates at first mapping, where keys are occurency ranges of each choice in a number. Then sorts it by first item in each key of mapping dict. Next step is creating graph. Then using find_shortest_path function, we can find the shortest path to build result in the most optimal way. So at the end we can use mapping again, to return choices according to their ranges. If there is one range, we have situation when all numbers consists the same two values, so rules are different. We can collect numbers direct from choices (sorted descending) until length of the result will be the same as length of a number.
def find_shortest_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
return path
if start not in graph:
return None
shortest = None
for node in graph[start]:
if node not in path:
newpath = find_shortest_path(graph, node, end, path)
if newpath:
if not shortest or len(newpath) < len(shortest):
shortest = newpath
return shortest
def get_it_done(choices, number):
mapping = {}
graph = {}
for choice in choices:
if choice in number:
_from = number.index(choice)
_to = _from + len(choice)
mapping.setdefault((_from, _to), choice)
items = sorted(mapping.items(), key=lambda x: x[0])
for _range, value in items:
_from, _to = _range
graph.setdefault(_from, []).append(_to)
start = 0
end = _range[1] #this is hack, works only in python 2.7
path = find_shortest_path(graph, start, end)
ranges = [tuple(path[i:i+2]) for i in range(len(path) - 1)]
if len(ranges) == 1:
return [mapping[(start, graph[start][-1])]]
return [mapping[_range] for _range in ranges]
if __name__ == "__main__":
examples = [
# Example1 ->
# Solution ['012345678910203040506070', '80', '90', '100', '200', '300', '400', '500', '600', '700', '800', '900']
(
[
"0", "1", "2", "3", "4", "5", "6", "7", "8", "9",
"10", "20", "30", "40", "50", "60", "70", "80", "90",
"100", "200", "300", "400", "500", "600", "700", "800", "900",
"012345678910203040506070"
],
"0123456789102030405060708090100200300400500600700800900"
),
## Example2
## Solution ['100']
(
["0", "1", "10", "100"],
"100"
),
## Example3
## Solution ['101234567891020304050', '6070809010020030040050', '0600700800900']
(
[
"10", "20", "30", "40", "50", "60", "70", "80", "90",
"012345678910203040506070",
"101234567891020304050",
"6070809010020030040050",
"0600700800900"
],
"10123456789102030405060708090100200300400500600700800900"
),
### Example4
### Solution ['12', '34', '56', '78', '90']
(
[
"12", "34", "56", "78", "90",
"890",
],
"1234567890"
),
## Example5
## Solution ['12', '34']
(
[
"1", "2", "3",
"12", "23", "34"
],
"1234"
)
]
for (choices, large_number) in examples:
res = get_it_done(choices, large_number)
print("{0}\n{1}\n{2} --> {3}".format(
large_number, "".join(res), res, "".join(res) == large_number))
print('-' * 80)
Ceci est une copie 1: 1 de l'algorithme d'origine @turkus, quelle est la signification de cela?
Désolé, la mise en œuvre est un peu hacky. Mais je pense que cela retourne toujours la réponse optimale. (N'a-tu pas proposé, cependant.) C'est une implémentation rapide et complète en python et renvoie les bonnes réponses pour tous les cas d'utilisation proposés.
L'algorithme est récursif et fonctionne comme suit:
Lorsque l'algorithme est effectué, tous les chemins possibles (et les celles qui ne sont pas possibles, c'est-à-dire qu'aucune correspondance à la fin) aurait dû être traversée exactement une fois.
pour effectuer l'étape 2 efficacement, Je construisai un arbre Patricia pour les choix afin que les morceaux possibles correspondant au début du texte puisse être levé rapidement. Je suppose que la complexité est quelque chose comme o (l * N * journal (c)) où L est la longueur du texte, n est la taille du vocabulaire et c est le nombre de choix.
Oui, merci pour la remarque. Aucune idée de la façon dont le 6ème test pourrait être supprimé ... mais cela fonctionne comme prévu sur le dernier cas.
La solution naïve semble commencer par le plus grand de vos morceaux et la rechercher dans la chaîne. Si vous le trouvez, divisez la ficelle dans les deux sous-chaînes de chaque côté, puis considérez de manière récursive ces chaînes.
Était ma première pensée aussi, mais je ne suis pas sûr que si cela est garanti de produire la solution optimale. Il pourrait être possible de remplacer une pièce avec 1 morceaux de taille longue et de 2 courts et 2 moyens de taille moyenne. Dans ce cas, cet algorithme ne produirait pas la solution optimale.
L'algorithme gourmand créera généralement une bonne solution, sinon la solution optimale. La bonne chose est que c'est simple à mettre en œuvre. Vous pouvez probablement obtenir une solution optimale avec une programmation dynamique, mais cela pourrait prendre un certain temps. La solution optimale pourrait en fait être calculée.
Par morceaux, vous voulez dire des substrings ou des jetons? Ma première pensée était la compression de texte (codes Huffman) si vous êtes autorisé à faire vos propres jetons (sans préfixes), mais cela ne correspond pas vraiment à la question. Je suis d'accord sur la programmation dynamique probable, mais c'est un sujet assez large.
Le premier commentaire, de @patrickhaughauga a donné l'idée de base.