[python] リストの重複を許した共通部分を求めたい

Question

言語はpython3.xです。
A=["a","b","b","c"], B=["b","b","c","d"]の共通部分をsetやら＆やらを使って求めると{"b","c"}となります。
しかし私がほしいのは["b","b","c"]というように重複を許した共通部分なんです。
どうやったらこのような重複を許した共通部分が求められるでしょうか。
ほかの例） A=["a","a","a","a","b","b","c","d"]
B=["a","a","a","b","c","c"]
求めたい奴["a","a","a","b","c"]

Answer 1

要素の順序が失われてもよければ collections.Counter を利用できます。

from collections import Counter
A = ["a","b","b","c"]
B = ["b","b","c","d"]
C = list((Counter(A) & Counter(B)).elements())
print(C)

Answer 2

けっこうごちゃごちゃしている感じになってしまいましたが、こんなのでしょうか？

import functools
a = ["a", "a", "a", "a", "b", "b", "c", "d"]
b = ["a", "a", "a", "b", "c", "c"]
print(functools.reduce(lambda t, x: (t[0] + [x], [y for i, y in enumerate(t[1])
    if i != t[1].index(x)]) if x in t[1] else t, a, ([], b))[0])

aとbを書き換えないようにするため、reduceを使って、aの要素を追加した新しい配列を作りながら、bからは削除した新しい配列を作る、そしてタプルで渡していくという処理をしています。

Answer 3

厳密でなくてもよければdifflibを使ってみるとか。

import difflib

a = 'a a a a b b c d'.split()
b = 'a a a b c c'.split()
c = [x[2:] for x in difflib.ndiff(a, b) if x[0] == ' ']
print('a =', a)
print('b =', b)
print('c =', c)

#output:
# a = ['a', 'a', 'a', 'a', 'b', 'b', 'c', 'd']
# b = ['a', 'a', 'a', 'b', 'c', 'c']
# c = ['a', 'a', 'a', 'b', 'c']

Answer 4

もっとシンプルに書けるかもしれませんが、importなしで。

1. ソート済みの共通項(set)を作る
2. 1をイテレートして、その要素と同じものをa, bから取り出す(aa, bbとする)
3. aaとbbの要素の少ない方を採用する

def f(a, b):
  result = []
  for i in sorted(set(a + b)):
    aa = [x for x in a if x == i]
    bb = [x for x in b if x == i]
    result += aa if len(aa) < len(bb) else bb
  return result

a=["a","b","b","c"]
b=["b","b","c","d"]
print(f(a, b))
# ['b', 'b', 'c']

a=["a","a","a","a","b","b","c","d"]
b=["a","a","a","b","c","c"] 
print(f(a, b))
# ['a', 'a', 'a', 'b', 'c']

上のを全部、内包表記に押し込めたバージョン。

def f(a, b):
    return [item for nested in
            [min([x for x in a if x == i],
                 [x for x in b if x == i], key=len)
            for i in sorted(set(a + b))] for item in nested]