J'ai une liste avec des nombres entiers comme:
output_l1 = [8,9] output_l2 = [3,4,2,4]
Mon but est de la découper dans le plus petit morceau répété. Donc:
l1 = [8,9,8,9,8,9,8], l2 = [3,4,2,4,3]
Le plus gros problème que les séquences ne se terminent pas complètement à chaque fois. Donc pas
'abcabcabc'
juste
'abcabcab'.
4 Réponses :
target = [8,9,8,9,8,9,8]
length = len(target)
result = []
results = [] * length
for j in range(1, length):
result = []
while len(result) < length:
for i in target[:j]:
result.append(i)
results.append(result)
final = []
for i in range(0, len(results)):
if results[i][:length] == target:
final.append(1)
else:
final.append(0)
if 1 in final:
solution = results[final.index(1)][:final.index(1)+1]
else:
solution = target
int(''.join(map(str, solution)))
'résultat: [8, 9]'.
Le code suivant est une refonte de votre solution qui résout certains problèmes:
Votre solution telle que publiée ne gère pas votre propre exemple 'abcabcab' .
Votre solution continue de traiter même après avoir trouvé un résultat valide, puis filtre les résultats valides et non valides. Au lieu de cela, une fois qu'un résultat valide est trouvé, nous le traitons et le renvoyons. Les résultats valides supplémentaires et les résultats non valides sont simplement ignorés.
Problème de @Boris concernant le retour de l'entrée s'il n'y a pas de motif répétitif.
print(*repeated_piece(l1), sep='')
print(''.join(map(str, repeated_piece(l1))))
Vous pouvez toujours utiliser:
% python3 test.py 89 3424 abc 123 %
si vous n'êtes pas à l'aise avec l'idiome Python 3 plus simple:
def repeated_piece(target):
target = list(target)
length = len(target)
for final in range(1, length):
result = []
while len(result) < length:
for i in target[:final]:
result.append(i)
if result[:length] == target:
return result[:final]
return target
l1 = [8, 9, 8, 9, 8, 9, 8]
l2 = [3, 4, 2, 4, 3]
l3 = 'abcabcab'
l4 = [1, 2, 3]
print(*repeated_piece(l1), sep='')
print(*repeated_piece(l2), sep='')
print(*repeated_piece(l3), sep='')
print(*repeated_piece(l4), sep='')
p >
Solution simple:
def get_unique_items_list(some_list):
new_list = []
for i in range(len(some_list)):
if not some_list[i] in new_list:
new_list.append(some_list[i])
return new_list
l1 = [8,9,8,9,8,9,8]
l2 = [3,4,2,4,3]
print(get_unique_items_list(l1))
print(get_unique_items_list(l2))
#### Output ####
# [8, 9]
# [3, 4, 2]
Merci, c'est super, mais le résultat l2 est faux. Parce que si vous répétez [3,4,2], l'élément suivant est 3, mais dans mon exemple, l'élément suivant est 4. Donc la bonne réponse est [3,4,2,4]
Vous voulez dire, vous voulez détecter la séquence complète ou le nombre de séquences au lieu de valeurs répétées de manière unique, n'est-ce pas?
Pouvez-vous partager quelques cas de test pour clarifier le problème?
J'aimerais le plus petit morceau, que vous répétiez et coupiez quelque part, vous obtenez la réponse. Par exemple: 19391 -> 1939 (car si vous continuez avec le premier élément, vous récupérerez le numéro d'origine, 13413413 -> 134, 11111 -> 1
shortest_repeating_sequence([4, 2, 7, 4, 6]) # no pattern [4, 2, 7, 4, 6] shortest_repeating_sequence([2, 3, 1, 2, 3]) # pattern doesn't repeat fully [2, 3, 1] shortest_repeating_sequence([2, 3, 1, 2]) # pattern doesn't repeat fully [2, 3, 1] shortest_repeating_sequence([8, 9, 8, 9, 8, 9, 8]) [8, 9] shortest_repeating_sequence([1, 1, 1, 1, 1]) [1] shortest_repeating_sequence([]) []
Veuillez fournir un code sur ce que vous avez essayé.
Je n'ai pas de code prometteur :(
@ TóthTamás Même le pseudo-code serait un début. Nous ne sommes pas là pour coder pour vous mais pour vous aider
Il convient de noter que vous pouvez résoudre ce problème bien mieux que O (n ^ 2). J'ai découvert une preuve vraiment remarquable de ce théorème que cette marge est trop petite pour contenir.
@Cireo. Je pense que j'en ai trouvé un aussi. Vous ne regardez pas par hasard la fréquence du premier élément, n'est-ce pas?
@MadPhysicist va dans la bonne direction, vous pouvez limiter considérablement l'espace de recherche
Copie possible de Trouver le cycle de répétition le plus court dans Word?