python: ordena una lista en una lista anidada por coincidencia de cadena sin función ordenada

Me pregunto cómo ordenar una lista como tal:

list_1 = ['apple', 'grape', 'orange', 'orange', 'apple', 'grape', 'apple']

a esto:

list_1 = [['apple', 'apple', 'apple'], ['grape', 'grape'], ['orange', 'orange']]

Solo usando un algoritmo sin procesar en lugar de cualquier función de clasificación.

La razón es que usaré este algoritmo junto con una función que hace coincidir las cadenas según la similitud del texto porque las cadenas que estoy clasificando no son las mismas, y confiar en cualquier función de clasificación no me permitiría para usar esa funcion

¡Cualquier orientación y ayuda es muy apreciada!

Answer

Suponiendo que su función de similitud de palabras es transitiva, puede agregar progresivamente palabras al grupo al que pertenecen, agregando nuevos grupos a medida que avanza para las palabras que no encuentran ninguna similitud:

def groupWords(L,isSimilar=lambda a,b:a==b):
    result = []
    for word in L:                         # for each word in list
        for group in result:               # find a similar word group
            if isSimilar(word,group[0]):   
                group.append(word)         # add to the group
                break
        else:
            result.append([word])          # new group if no match
    return result

producción:

list_1 = ['apple', 'grape', 'orange', 'orange', 'apple', 'grape', 'apple']

list_2 = groupWords(list_1)

print(list_2)
[['apple', 'apple', 'apple'], ['grape', 'grape'], ['orange', 'orange']]

Puede proporcionar la función con su propia función de verificación de similitud o hacerla parte del ciclo directamente

Tenga en cuenta que, si su verificación de similitud no es transitiva, las palabras irán al primer grupo coincidente y el resultado dependerá del orden de entrada.

Puede utilizar este tipo de algoritmo. Primero clasifique la lista usando cualquier algoritmo de clasificación, usemos la clasificación de burbuja por ahora. Luego cuente la frecuencia de todos los elementos y guárdelo en un diccionario y luego vuelva a convertirlo en una lista anidada. Así que puedes hacer algo como esto:

def bubble_sort(ls):
    swapped = True
    while swapped:
        swapped = False
        for i in range(len(ls) - 1):
            if ls[i] > ls[i + 1]:
                # Swap the elements
                ls[i], ls[i + 1] = ls[i + 1], ls[i]
                swapped = True
    return ls

def nest(ls):
    ls2 = {}
    res = []
    for i in ls:
        if i in ls2:
            ls2[i] += 1
        else:
            ls2[i] = 1
    i = 0
    while i<len(ls):
        res.append([ls[i]]*ls2[ls[i]])
        i+=ls2[ls[i]]
    return res

print(nest(bubble_sort(['apple', 'grape', 'orange', 'orange', 'apple', 'grape', 'apple'])))

Para ordenar esta lista puede ejecutar este código:

list_1 = ['apple', 'grape', 'orange', 'orange', 'apple', 'grape', 'apple']
list_1.sort()

dictionary = {}
for item in list_1:
    if item not in dictionary:
        dictionary[item] = 1
    else:
        dictionary[item] += 1

list_1 = []
for word in dictionary:
    list_2 = [word]*dictionary[word]
    list_1.append(list_2)

print(list_1)

Esto produce

[['apple', 'apple', 'apple'], ['grape', 'grape'], ['orange', 'orange']]

La segunda línea de código es opcional, puede eliminarla si no necesita que la última lista esté en orden alfabético.