найти и обновить дубликаты в списке списков - PullRequest
Новая
       11

найти и обновить дубликаты в списке списков

2 голосов
/ 18 июля 2011

Я ищу Pythonic способ решить следующую проблему. У меня есть (я думаю, что это) рабочее решение, но оно имеет сложные средства управления потоком и просто не «красиво». (В основном, решение C ++)

У меня есть список списков. Каждый список содержит несколько элементов различных типов (возможно, 10 элементов в списке). Общий порядок списков не имеет значения, но порядок элементов в любом отдельном списке важен. (т.е. я не могу это изменить).

Я хочу пометить дубликаты, добавив дополнительное поле в конец отдельного списка. Однако в этом случае список «дубликатов» - это список, который имеет равные значения в нескольких предварительно выбранных полях, но не во всех полях (нет «истинных» дубликатов).

Например: если это были исходные данные из списка из 5 пунктов, а дубликат определяется как имеющий равные значения в первом и третьем полях: 

['apple', 'window', 'pear', 2, 1.55, 'banana']
['apple', 'orange', 'kiwi', 3, 1.80, 'banana']
['apple', 'envelope', 'star_fruit', 2, 1.55, 'banana']
['apple', 'orange', 'pear', 2, 0.80, 'coffee_cup'] 
['apple', 'orange', 'pear', 2, 3.80, 'coffee_cup']

Первый, четвертый и пятый списки будут дубликатами, и поэтому все списки должны быть обновлены следующим образом: 

['apple', 'window', 'pear', 2, 1.55, 'banana', 1]
['apple', 'orange', 'kiwi', 3, 1.55, 'banana', 0]
['apple', 'envelope', 'star_fruit', 2, 1.55,'banana', 0]
['apple', 'orange', 'pear', 2, 3.80, 'coffee_cup', 2]  
['apple', 'orange', 'pear', 2, 3.80, 'coffee_cup', 3]

Спасибо за любую помощь или направление. Я думаю, что это выходит за рамки книги Обучающего Python.

Ответы [ 3 ]

3 голосов
/ 18 июля 2011 
from collections import defaultdict

lists = [['apple', 'window', 'pear', 2, 1.55, 'banana'],
['apple', 'orange', 'kiwi', 3, 1.80, 'banana'],
['apple', 'envelope', 'star_fruit', 2, 1.55, 'banana'],
['apple', 'orange', 'pear', 2, 0.80, 'coffee_cup'],
['apple', 'orange', 'pear', 2, 3.80, 'coffee_cup']]

dic = defaultdict(int)
fts = []
for lst in lists:
    first_third = lst[0], lst[2]
    dic[first_third] += 1
    if dic[first_third] == 2: fts.append(first_third)
    lst.append(dic[first_third])

for lst in lists:
    if (lst[0], lst[2]) not in fts:
        lst[-1] -= 1

print(lists)

Редактировать: Спасибо, Утдемир. first_third = lst[0], lst[2] правильно, а не first_third = lst[0] + lst[2]

Edit2: изменены имена переменных для ясности.

Edit3: изменен, чтобы отразить то, что действительно хотел оригинальный постер, и его обновленный список. Не очень, желаемые изменения просто добавлены.

1 голос
/ 18 июля 2011

Лучше всего сначала отсортировать список, используя itemgetter(), чтобы выбрать поля для сопоставления как key.Это приведет к тому, что все совпадающие ключевые поля появятся вместе, чтобы их можно было легко сравнить и пометить.Например, сортировка для сопоставления первого и третьего полей будет такой: 

lst.sort(key=itemgetter(0, 2))

Сравнение каждого элемента с его предшественником прямое.

Хорошо, вот полное решение (использует itemgetter и groupby): 

from operator import itemgetter
from itertools import groupby

def tagdups(input_seq, tag, key_indexes):
    keygetter = itemgetter(*key_indexes)
    sorted_list = sorted(input_seq, key=keygetter)
    for key, group in groupby(sorted_list, keygetter):
        group_list = list(group)
        if len(group_list) <= 1:
            continue
        for item in group_list:
            item.append(tag)
    return sorted_list

А вот примерный тестовый прогон, чтобы показать использование: 

>>> samp = [[1,2,3,4,5], [1,3,5,7,7],[1,4,3,5,8],[4,3,2,7,5],[1,6,3,7,4]]
>>> tagdups(samp, 'dup', (0,2))
[[1, 2, 3, 4, 5, 'dup'], [1, 4, 3, 5, 8, 'dup'], [1, 6, 3, 7, 4, 'dup'], [1, 3, 5, 7, 7], [4, 3, 2, 7, 5]]
0 голосов
/ 18 июля 2011

Вот мое решение (закомментированный код): 

import itertools

l = [
        ['apple', 'window', 'pear', 2, 1.55, 'banana'],
        ['apple', 'orange', 'kiwi', 3, 1.80, 'banana'],
        ['apple', 'envelope', 'star_fruit', 2, 1.55, 'banana'],
        ['apple', 'orange', 'pear', 2, 0.80, 'coffee_cup'],
        ['apple', 'orange', 'pear', 2, 3.80, 'coffee_cup']
    ]

#Here you can select the important fields 
key = lambda i: (i[0],i[2])

l.sort(key=key)
grp = itertools.groupby(l, key=key)
#Look at itertools documentation
grouped = (list(j) for i,j in grp)

for i in grouped:
    if len(i) == 1:
        i[0].append(0)
    else: #You want duplicates to start from 1
        for pos, item in enumerate(i, 1):
            item.append(pos)

#Just a little loop for flattening the list
result = [] 
for i in grouped:
    for j in i:
        result.append(j)

print(result)

Выход: 

[['apple', 'orange', 'kiwi', 3, 1.8, 'banana', 0],
 ['apple', 'window', 'pear', 2, 1.55, 'banana', 1],
 ['apple', 'orange', 'pear', 2, 0.8, 'coffee_cup', 2],
 ['apple', 'orange', 'pear', 2, 3.8, 'coffee_cup', 3],
 ['apple', 'envelope', 'star_fruit', 2, 1.55, 'banana', 0]]
...