两个列表中匹配元素的数量
我有很多组由两个字符串组成的集合。我想知道这两个字符串中有多少个字母是相同的。规则是，如果这两个字符串有共同的字母，就算得一分，字母的顺序是重要的，而且第一个字符串中的每个字母只能和第二个字符串中的一个字母匹配。所以在字符串 'aaaab' 和 'acccc' 中，只能得 1 分，因为在第二个字符串中只有一个 'a' 可以匹配。下面是一些例子：
aaabb bbaaa 5
aabbb bbbaa 5
aaabb aabbb 4
aaabb ccaaa 3
aaaaa bbbbb 0
ababa babab 4
aabcc babaf 3
abcde abfgh 2
bacde abdgh 3
希望这样能让你明白它是怎么工作的。
这是我能想到的最有效的代码，但它实在是太复杂了。我希望有人能想出更好的办法。
def Score(guess, solution):
guess = list(guess)
solution = list(solution)
c = 0
for g in guess:
if g in solution and g != "_":
c += 1
solution[solution.index(g)] = "_"
return c
这肯定不是最好的方法，但我还没能想出其他的。我试着用 Counter 创建一个算法，并做了 guess&solution，虽然能工作，但速度却慢得多。有没有人有好的主意？
相关问题：
6 个回答
和@sloth提到的概念一样，不过这里用的是try而不是if。
def Score(guess, solution):
solution = list(solution)
c = 0
for g in guess:
try:
solution.remove(g)
c += 1
except ValueError:
pass
return c
这里有一个很简单的解决方案，使用了Counter：
def proc(vals):
for s1, s2 in vals:
c1, c2 = Counter(s1), Counter(s2)
same = set(s1) & set(s2)
print s1, s2, sum(min(c1[c], c2[c]) for c in same)
其中 vals 看起来像这样：
vals = [('aaaaa', 'bbbbb'), ...]
这里是；
list_a = list("aabbb")
list_b = list("bbbaa")
list_c = set(list_b)
counter = 0
for i in list_c:
if i in list_b:
counter = list_a.count(i)
print "counter : %s element : %s" %(counter,i )
我只是想展示一下怎么计算共同的元素，你可以根据需要修改代码来计算总和。
你可以用NumPy以向量化的方式来实现这个！
import numpy as np
counts1 = np.bincount(np.array('aaadez', 'c').view(np.uint8), minlength=128)
counts2 = np.bincount(np.array('eeeedddddaa', 'c').view(np.uint8), minlength=128)
np.min((counts1, counts2), axis=0).sum()
counts1看起来是这样的：
array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 3, 0, 0, 1, 1, 0...])
这是一个用ASCII码索引的数组。非零元素出现在位置97、100和101，这些位置对应的字符是ASCII的'a'、'd'和'e'。接着我们进行成对的最小值计算，然后求和来得到分数（在这个例子中是4）。
这个解决方案的一个好处是，你可以对任意多个字符串应用它，效率不会降低，即使是很长的字符串也会很快，因为在Python中没有循环，只有在编译后的NumPy代码中有。
在编辑之前，我有一个类似但更慢、更复杂的解决方案，使用了Pandas和SciPy。这里是：
import scipy.stats
import numpy as np
import pandas
x1 = scipy.stats.itemfreq(np.array('aaade', 'c').view(np.uint8))
x2 = scipy.stats.itemfreq(np.array('bbacadde', 'c').view(np.uint8))
merged = pandas.merge(pandas.DataFrame(x1), pandas.DataFrame(x2), on=0)
np.sum(np.min(merged.values[:,1:], axis=1))
这样得到的是4.0。前两行将字符串转换为整数数组，并运行itemfreq()来统计每个字符出现的次数。在这个例子中，x1是：
arrray([[ 97., 3.],
[ 100., 1.],
[ 101., 1.]])
然后我们通过第0列将两个表连接起来，去掉在另一个表中不存在的字符：
0 1_x 1_y
0 97 3 2
1 100 1 2
2 101 1 1
最后我们只需进行一次最小值计算和求和，得到最终分数（在这个例子中是2+1+1）。
你可以通过直接使用 list 的 remove() 方法，而不是先用 index() 查找，来提高大约10%的速度。
另外，你也不需要把 guess 复制到一个 list 里。
def Score(guess, solution):
solution = list(solution)
c = 0
for g in guess:
if g in solution:
c += 1
solution.remove(g)
return c
*至少这是我在我的电脑上测量的结果