Исключение комбинаций с дубликатами на основе ключевой функции

Question

Я хочу перебирать подпоследовательности списка, но у меня есть понятие уникальности, определяемое внешней функцией, и я хочу игнорировать комбинации, которые имеют несколько элементов с одинаковым значением в функция.

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

import itertools 

names = ["Anabel", 
     "Alison", 
     "Avery", 
     "Abigail", 
     "Aimee", 
     "Alice", 
     "Bethany", 
     "Beatrice", 
     "Claudia", 
     "Carolyn", 
     "Diane", 
     "Dana"] 

f = lambda x : x[0] 

for i in itertools.combinations(names, 3): 
    if ((f(i[0]) != f(i[1])) and 
     (f(i[0]) != f(i[2])) and 
     (f(i[1]) != f(i[2]))): 
     print i 

То, что я на самом деле делаю здесь перебирает все возможные комбинации из 3 имен, и выбрасывая те, которые этого не делают, что, конечно, медленнее, чем перебирают все комбинации из 3 имен. Есть ли способ, который будет на самом деле быстрее? Создать итератор, который исключает те, которые я хочу пропустить в первую очередь?

Answer 1

Да, возможно, одно решение, о котором я мог думать, требует создания словаря, объединяющего f(value) и фактических имен в качестве словаря. Здесь я буду использовать iteration_utilities.groupedby, но это легко сделать, используя collections.defaultdict (я покажу это в нижней части ответа).

>>> from iteration_utilities import groupedby 
>>> equivalent = groupedby(names, f) 
>>> equivalent 
{'A': ['Anabel', 'Alison', 'Avery', 'Abigail', 'Aimee', 'Alice'], 
'B': ['Bethany', 'Beatrice'], 
'C': ['Claudia', 'Carolyn'], 
'D': ['Diane', 'Dana']} 

Затем перебирать комбинации (отсортированные) ключей в этом словаре, а затем использовать itertools.product делать итерации над всеми именами для каждого префикса:

import itertools 

for comb in itertools.combinations(sorted(equivalent), 3): 
    for uniquecomb in itertools.product(*[equivalent[i] for i in comb]): 
     print(uniquecomb) 

sorted используется, потому что в противном случае порядок появления не будет детерминированным между прогонами.

---

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

def unique_combs(names, f): 
    equivalent = groupedby(names, f) 

    for comb in itertools.combinations(sorted(equivalent), 3): 
     for uniquecomb in itertools.product(*[equivalent[i] for i in comb]): 
      pass 

def unique_combs_original(names, f): 
    for i in itertools.combinations(names, 3): 
     if ((f(i[0]) != f(i[1])) and 
       (f(i[0]) != f(i[2])) and 
       (f(i[1]) != f(i[2]))): 
      pass 

names = ["Anabel", "Alison", "Avery", "Abigail", "Aimee", "Alice", 
     "Bethany", "Beatrice", 
     "Claudia", "Carolyn", 
     "Diane", "Dana"] 

f = lambda x : x[0] 

%timeit unique_combs(names, f)   # 10000 loops, best of 3: 59.4 µs per loop 
%timeit unique_combs_original(names, f) # 1000 loops, best of 3: 417 µs per loop 

Но масштабируется намного лучше, если есть много чтобы быть отвергнутыми комбинации:

names = names * 10 # more duplicates 

%timeit unique_combs(names, f)   # 100 loops, best of 3: 9.74 ms per loop 
%timeit unique_combs_original(names, f) # 1 loop, best of 3: 577 ms per loop 

---

Я упомянул defaultdict вместо groupedby, для полноты он может быть создан как thi s:

from collections import defaultdict 

>>> names = ["Anabel", "Alison", "Avery", "Abigail", "Aimee", "Alice", 
...   "Bethany", "Beatrice", 
...   "Claudia", "Carolyn", 
...   "Diane", "Dana"] 

>>> equivalent = defaultdict(list) 
>>> for name in names: 
...  equivalent[f(name)].append(name) 

>>> equivalent 
defaultdict(list, 
      {'A': ['Anabel', 'Alison', 'Avery', 'Abigail', 'Aimee', 'Alice'], 
      'B': ['Bethany', 'Beatrice'], 
      'C': ['Claudia', 'Carolyn'], 
      'D': ['Diane', 'Dana']}) 

Answer 2

Вы можете использовать combinations, groupby и product из itertools для следующих Однострочник:

[p for c in combinations((tuple(g) for _, g in groupby(names, lambda x: x[0])), 3) 
     for p in product(*c)] 

В вышеуказанных groupby групп имена, основанные на первую букву и возвращает Iterable из (key, group) кортежей. Каждый group является итерируемым, который затем преобразуется в кортеж, так что его можно многократно повторять. Обратите внимание, что это предполагает, что имена, начинающиеся с одной буквы, находятся рядом друг с другом в списке. Если это не так, вы можете сортировать имена перед использованием groupby.

Вот пример groupby сам по себе:

>>> groups = list(tuple(g) for _, g in groupby(names, lambda x: x[0])) 
>>> groups 
[('Anabel', 'Alison', 'Avery', 'Abigail', 'Aimee', 'Alice'), ('Bethany', 'Beatrice'), ('Claudia', 'Carolyn'), ('Diane', 'Dana')] 

Далее результат группы приведены в combinations, который будет возвращать все подпоследовательности из групп с 3-х элементов в них:

>>> combs = list(combinations(groups, 3)) 
>>> combs 
[(('Anabel', 'Alison', 'Avery', 'Abigail', 'Aimee', 'Alice'), ('Bethany', 'Beatrice'), ('Claudia', 'Carolyn')), (('Anabel', 'Alison', 'Avery', 'Abigail', 'Aimee', 'Alice'), ('Bethany', 'Beatrice'), ('Diane', 'Dana')), (('Anabel', 'Alison', 'Avery', 'Abigail', 'Aimee', 'Alice'), ('Claudia', 'Carolyn'), ('Diane', 'Dana')), (('Bethany', 'Beatrice'), ('Claudia', 'Carolyn'), ('Diane', 'Dana'))] 

Наконец каждый комбинация распакована и перешла на product, что приведет к декартовому изделию для данных групп:

>>> result = list(p for c in combs for p in product(*c)) 
>>> result[0] 
('Anabel', 'Bethany', 'Claudia') 
>>> len(result) 
80