Пересечение двух списков в N раз

Question

У меня есть два списка (['a', 's', 'f', 'f', 's'], ['f', 'f', 'a', 's']). Требуемый выход: ['a','s','f','f']. Результат должен дать пересечение двух списков. Расположение символов в выходном списке соответствует порядку появления в первом списке ['a', 's', 'f', 'f', 's'].

Как это реализовать в python? Я уже делал это в N ** 2 раза. Возможно ли это сделать в N раз?
Мое текущее решение:

 
def com(string1, string2): 
    string2_list=list(string2) 
    store="" 
    for check in string1: 
     for i,v in enumerate(string2_list): 
      if v==check: 
       store=store+check 
       del(string2_list[i]) 
    return store 

Answer 1

встроенная операция пересечения Использование collections.Counter «s.

>>> l1, l2 = (['a', 's', 'f', 'f', 's'], ['f', 'f', 'a', 's']) 
>>> import collections 
>>> collections.Counter(l1) & collections.Counter(l2) 
Counter({'f': 2, 'a': 1, 's': 1}) 

Отсюда не трудно построить подходящий список:

>>> counter = collections.Counter(l1) & collections.Counter(l2) 
>>> out = list(counter.elements()) 
>>> print out 
['a', 's', 'f', 'f'] 

Или заказать по одному из списков:

>>> out = [] 
>>> for k in l1: 
...  if counter[k] > 0: 
...   counter[k] -= 1 
...   out.append(k) 
... 
>>> print out 
['a', 's', 'f', 'f'] 

Ожидается, что время O (N): создание счетчика ожидается O (N), а встречное пересечение также ожидается O (N).

Answer 2

Это работает с использованием счетчика из коллекций:

import collections 

a = ['a', 's', 'f', 'f', 's'] 
b = collections.Counter(['f', 'f', 'a', 's']) 

output = [] 
for x in a: 
    if b.get(x): 
     output.append(x) 
     b.subtract(x) 

print output 

Результат:

['a', 's', 'f', 'f'] 

Не 100% уверены в алгоритмической сложности здесь, но я думаю, что поиск в счетчике O(1) (hash based), который делает это O(n).

Answer 3

Отсортировать списки, которые предоставили вам: List1: "affss" List2: "affs". Затем используйте петлю цепочки, соответствующую

псевдокода (незначительные корректировки могут быть необходимы)

list1; 
list2; 
list3; //output list 
n = list1.length() //list1 length 
x = list2.length() //list2 length 
int i = 0; //list1 counter 
int j = 0; //list2 counter 
//go through both list simutainously and remove the lexographically smallest at every list1[i] != list2[j] 
while i != n and j != x 
    if list1[i] == list[j] 
     list3.add(list1(i)) 
     i++ 
     j++ 
    else 
     if list1[i]<=list[j] 
      i++; 
     else 
      j++ 
return list3 

Алгоритм Стоимость: Сортировки = O (nlgn) Использования слияния для удобства, или если вы можете получить ваши руки на рандомизированную сортировке, то быстрая сортировка ursually 3 раза быстрее, должно быть часть вашего питона Lib, если нет: http://randalgos.blogspot.dk/2012/03/randomized-quick-sort-in-python.html в то время как цикл будет принимать 2n на максимуме, оставив вас с:

O (nlgn) + 2n = O (nlgn)

Answer 4

Это создает словарь для поиска порядка в l1 пункта, а не индексного метода l1:

>>> from collections import Counter 
>>> l1, l2 = (['a', 's', 'f', 'f', 's'], ['f', 'f', 'a', 's']) 
>>> l1_to_index = {val: indx for indx, val in reversed(list(enumerate(l1)))} 
>>> sorted((Counter(l1) & Counter(l2)).elements(), key=lambda x: l1_to_index[x]) 
['a', 's', 'f', 'f'] 
>>>