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.

-2
bhawesh sah 14 avril 2018 à 16:42

4 réponses

Meilleure réponse

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))
0
Niklas Mertsch 14 avril 2018 à 13:58

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]]
1
Aran-Fey 14 avril 2018 à 15:18

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

0
sciroccorics 14 avril 2018 à 14:08
    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
0
Imre Raudsepp 14 avril 2018 à 14:31