J'ai une liste de listes qui est
my_list=[[9, 10, 1], [1, 7, 5, 6, 11], [0, 4], [4, 2, 9]]
Je veux trier cette liste pour qu'elle ressemble à ceci:
result=[[0, 4], [4, 2, 9],[9, 10, 1], [1, 7, 5, 6, 11]]
Les conditions sont les suivantes: 1. La liste doit commencer par l'élément contenant zéro. 2. Le dernier élément d'une liste doit être le même que le premier élément de la liste suivante et ainsi de suite. 3. Les éléments à l'intérieur des sous-listes doivent être dans le même ordre que la liste d'origine.
Je vous remercie.
4 réponses
Vous pouvez vérifier chaque permutation de votre liste, s'il s'agit d'une permutation valide. Il pourrait être possible d'écrire un algorithme plus efficace, mais celui-ci ne suppose pas qu'il existe exactement une solution possible.
from itertools import permutations
my_list=[[9, 10, 1], [1, 7, 5, 6, 11], [0, 4], [4, 2, 9]]
def sortCheck(a):
if a[0][0] != 0:
return False
for i in range(0, len(a) - 1):
if a[i][-1] != a[i+1][0]:
return False
return True
result_list = []
for permutation in permutations(my_list):
if sortCheck(permutation):
result_list.append(list(permutation))
La solution rapide consiste à créer un dict qui mappe les nombres aux sous-listes en fonction du premier élément:
dct = {sublist[0]: sublist for sublist in my_list}
# {0: [0, 4], 9: [9, 10, 1], 1: [1, 7, 5, 6, 11], 4: [4, 2, 9]}
Et puis, en commençant par le numéro 0, en recherchant la prochaine sous-liste qui doit être ajoutée dans le dict:
result = []
num = 0 # start with the sublist where the first element is 0
while True:
try:
# find the sublist that has `num` as the first element
sublist = dct[num]
except KeyError:
# if there is no such sublist, we're done
break
# add the sublist to the result and update `num`
result.append(sublist)
num = sublist[-1]
Cela s'exécute en temps O(n) linéaire et donne les résultats attendus:
[[0, 4], [4, 2, 9], [9, 10, 1], [1, 7, 5, 6, 11]]
Pas une très belle implémentation, mais ça marche:
my_list=[[9, 10, 1], [1, 7, 5, 6, 11], [0, 4], [4, 2, 9]]
new_list = []
index = 0
while my_list:
index = [item[0] for item in my_list].index(index)
item = my_list[index]
del my_list[index]
new_list.append(item)
index = item[-1]
print(new_list)
Un ValueError est levé lorsqu'aucune sous-liste ne correspond au critère
def sortList(list)
hash = {}
list.each do |value|
hash[value[0]] = value
end
key = 0
sorted = []
list.each do |k|
item = hash[key.to_i]
key = item[-1]
sorted << item
end
sorted
end