Сравнение двух списков на нахождение элементов которые соответствуют правилам

#python #алгоритм #python_3.x #list

Вопрос заключается в том, что например у меня есть два списка:

lst1 = ['1', '2' , '3' , '4']
lst2 = ['123', '234' , '345' , '334']


Как мне найти такие элементы во втором списке, которые включают в себя только те
элементы, которые есть в первом, но, если в первом списке есть одна единица, то например
элемент "112" с второго списка не подходит.

Tо есть результатом программы должен быть 

ls3 = ['123', '234']


'345' - не подошло потому что там есть элемент "5" которого нет в первом списке

'334' - не подошло потому что там есть два элемента "3", а в первом списке элемент
"3" есть только один
    

Ответы

Ответ 1

Если известно как определить, можно ли составить строку word из заданных символов
chars, используя каждый символ в chars не более его числа повторений (известен can_build(word,
chars) предикат), то задача сводится к:

result = list(filter(can_build, lst2))


или более читаемо:

result = [word for word in lst2 if can_build(word)]


где can_build использует chars = lst1 внутри.

Если бы требовалось использовать все символы из chars, тогда это была бы проверка
является ли word анаграммой chars, к примеру: "просветитель" можно получить перестановкой
букв "терпеливость". Можно использовать похожие решения, когда точное равенство заменено
на "не более".

can_build() можно реализовать, найдя является ли word мультимножество подмножеством
chars мультимножества. Если бы все символы в chars и word были уникальны, то 

can_build = set("1234").issuperset


collections.Counter реализует идею множества, в котором элементы могут повторяться,
то есть мультимножества. Как показано в элегантном решении в ответе @Timofey Bondarev,
эту коллекцию можно использовать чтобы реализовать can_build:

can_build = lambda word, chars=Counter(lst1): not (Counter(word) - chars)


Можно реализовать тот же алгоритм вручную, не используя collections.Counter. 

from collections import defaultdict

def Counter(letters):
    counts = defaultdict(int)
    for letter in letters:
        counts[letter] += 1
    return counts

chars_count = Counter(chars)

def can_build(word):
    return all(chars_count[char] >= count for char, count in Counter(word).items())


Можно использовать простой список, если все символы принадлежат какому-либо алфавиту,
тогда так как chars всё время один и тот же, то можно закэшировать chars.count значения.
Например, если chars может содержать только цифры 0-9:

from string import digits

chars_count = [(digit, chars.count(digit)) for digit in digits]

def can_build(word):
    return all(word.count(digit) <= count for digit, count in chars_count)


это O(N * M) решение (M=len(digits)—размер алфавита), в отличии от O(N) решения,
использующего Counter(). Если алфавит нефиксированный: alphabet = set(word), тогда
это O(N**2) (квадратичный) алгоритм. Если alphabet фиксированный как в примере, то
это O(N) (линейное) решение. Для небольшого алфавита, например, для boolean цифр (alphabet=(0,1))
или ДНК-строк (alphabet="GTAC"), это решение могло быть даже быстрее решения с Counter().

Ещё пример применения: если word, chars это числа, представленные их простыми множителями
(например: (2,2,3) представляет 12, (5,7) представляет 35), тогда can_build() отвечает
на вопрос является ли word делителем chars, то есть верно ли что: chars % word == 0.


  Q: как реализовать код, если избавиться от условия о том, что элемент должен повторяться
столько раз сколько его есть в первом списке???


Уже ответ в этом предположении работает. Иначе это был бы случай с анаграммами: количество
повторений совпадает. Решения с Counter() и с <=, >= НЕ требуют, чтобы элемент повторялся
"столько раз сколько его есть в первом списке" (можно меньше).

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

can_build = set(lst1).issuperset


как уже упомянуто выше.


Ответ 2

Эту проблему можно решить, используя стандартный класс для мультимножества Counter:

from collections import Counter

lst1 = ['1', '2' , '3' , '4']
lst2 = ['123', '234' , '345' , '334']

base = Counter(lst1)
result = [s for s in lst2 if not (Counter(s) - base)]


Условие not (Counter(s) - base) проверяет то, что в мультимножестве s не больше элементов,
чем в base


Ответ 3

[l2 for l2 in lst2 if all(l2.count(l) <= lst1.count(l) for l in set(l2))]


Ответ 4

#!/usr/bin/env python3.4
# -*- coding: utf-8 -*-
lst1 = ['1', '2' , '3' , '4']
lst2 = ['123', '234' , '345' , '334']
S1 = set(lst1)
S2 = set(lst2)
S3 = set()
for x in S2:
    if set(x) <= S1: S3.add(x)
lst3 = list(S3)
for x in lst3:
    for y in x:
        if x.count(y) > 1:
            count = lst3.index(x)
            continue
lst3.pop(count)
print(lst3)


Если просто по логике вещей, без особых премудростей. Чуток знать о множествах (из
школы), циклы и списки. Ответ ['123', '234']


Ответ 5

Решение выше, конечно более коротко, но по человечески можно сделать так:

список = ['1', '2', '3', '4']
список2 = ['123', '234', '345', '34']

результат = []
for сочетание in список2:
    временный_список = список[:]  # копия списка
    for цифра in сочетание:
        if цифра in временный_список:
            временный_список.remove(цифра)  # чтобы не более одной проверки на число
        else:
            break
    else: результат.append(сочетание)

print(результат)


===================== RESTART: C:\Python 3.5\задачка.py =====================
['123', '234', '34']