Python 迭代问题！

Question

我有这段代码，它应该从列表n1和n2中删除共同的字母。但是当我运行这段代码时，它只运行一次，即仅从n1和n2中删除'a'，而没有删除'k'。

只是为了澄清，此代码应始终仅适用于两个单词。

name1 = "abdjek"
name2 = "doarhsnk"

n1l = list(name1)
n2l = list(name2)

for i in range(len(n1l)):
   for j in range(len(n2l)):
         if n1l[i] == n2l[j]:
               n1l.pop(i)
               n2l.pop(j)
               n1l.append('0')
               n2l.append('1')

等一下，对于上面的两个名字似乎可以工作，但是当我有name1 =“naveen”和name2 =“darshana”时，它就不起作用了！

- oktapodi

---

当我运行这个程序时，它会产生预期的结果，即n1l = ['b', 'j', 'e', '0', '0', '0']和n2l = ['o', 'r', 'h', 's', 'n', '1', '1', '1']。 - Jakob Borg

我刚刚将它粘贴到我的Python解释器中，它似乎可以实现你想要的功能（删除重复字母并添加0或1以保持列表长度相同）。不过，这不是我会使用的算法。 - Carl Norum

你可以使用集合运算符更高效地完成这个任务。 - recursive

有更多Pythonic的方法来做这件事。我会改变的最明显的事情是：1.字符串实际上是字符序列，所以您不需要显式创建列表。2.for ch in aString:然后使用ch比for i in range(len(aString)):然后使用aString[i]更受欢迎。 - Tyler

如果name1中有3个字母出现，而name2中只有1个呢？它们都被删除吗？ - MAK

@MAK 只需删除第一个实例。 - oktapodi

Answer 1

我建议采取一个更简单的方法：

def removecommon(name1, name2):
  common = set(name1).intersection(name2)
  res1 = ''.join(n for n in name1 if n not in common)
  res2 = ''.join(n for n in name2 if n not in common)
  return res1, res2

n1, n2 = removecommon('naveen', 'darshana')
print n1, n2

按需发出vee drsh。

编辑：由于OP现在指定（在评论中 - 请记得编辑您的问题，哦OP！）他实际上只想删除每个单词中每个常见字母的第一个出现，所需的算法当然完全不同。一个简单的方法（如果单词的长度不太高，则可行）：

def removefirstcommon(name1, name2):
  common = set(name1).intersection(name2)
  n1 = list(name1)
  for c in common: n1.remove(c)
  n2 = list(name2)
  for c in common: n2.remove(c)
  return ''.join(n1), ''.join(n2)

更为复杂的方法（对于普通长度的单词而言速度较慢）对于极长的单词来说却更快（因为下面这个方法是O（N），而前者是O（N平方））：

def removefirstcommonlongwords(name1, name2):
  common = set(name1).intersection(name2)
  def mustrem(c, copycom):
    res = c not in copycom
    copycom.discard(c)
    return res
  cop = set(common)
  n1 = [c for c in name1 if mustrem(c, cop)]
  n2 = [c for c in name2 if mustrem(c, common)]
  return ''.join(n1), ''.join(n2)

- Alex Martelli

---

@Alex Martelli 感谢您提供这种新的方法，但我还有一个问题，我只想删除第一次匹配的内容，我需要得到“veen”和“darsha”的输出。我不想删除所有的“n”和“a”。 - oktapodi

@Prabhu，您如何从“darshana”中删除a和n的第一次出现以获得“darsha”？ “drshaa”似乎遵循“删除第一次出现”的规则。请澄清一下？ - Alex Martelli

Answer 2

更符合Python风格的做法是使用set和列表推导。

name1 = "naveen"; name2 = "darshana"

name1_set=set(name1)
name2_set=set(name2)

clean1=[x for x in  name1 if x not in name2_set]
clean2=[x for x in name2 if x not in name1_set]

clean1.extend(['0']*(len(name1)-len(clean1)))
clean2.extend(['1']*(len(name2)-len(clean2)))

print clean1,clean2

set 提供了O(1)的查找功能，因此使整个过程更快，将其从O(N^2)降至O(N)。

编辑：考虑到您后来的评论中出现次数的问题，这是更新后的版本。

name1 = "naveen"; name2 = "darshana"

count1={}
count2={}


for x in name1:
    count1[x]=count1.get(x,0)+1

for x in name2:
    count2[x]=count2.get(x,0)+1

def remove_dups(name,count,null):
    clean=[]
    for x in name:
        if count.get(x,0):
            count[x]-=1
        else:
            clean.append(x)
    clean.extend([null]*(len(name)-len(clean)))
    return clean

clean1=remove_dups(name1,count2,'0')
clean2=remove_dups(name2,count1,'1')

print clean1,clean2

它使用 dict 来记录出现次数。每当一个字符被删除时，另一个名称的相应计数会减少。复杂度仍为 O(N)。

它打印出 ['v', 'e', 'e', 'n', '0', '0'] 和 ['d', 'r', 's', 'h', 'a', 'a', '1', '1']。这是您想要的吗？

- MAK

---

set 接受一个可迭代对象，因此 set('foo') 可以工作，无需转换为中间列表。 - Mike Graham

@Mike：没错，忘了字符串已经可迭代了。回答已更新，谢谢。 - MAK

Answer 3

这在我的电脑上可以运行。也就是说，如果我加入打印语句：

name1 = "abdjek"
name2 = "doarhsnk"

n1l = list(name1)
n2l = list(name2)

print "Lists before loop:"
print n1l
print n2l

for i in range(len(n1l)):
    for j in range(len(n2l)):
        if n1l[i] == n2l[j]:
           n1l.pop(i)
           n2l.pop(j)
           n1l.append('0')
           n2l.append('1')

print "Lists after loop:"
print n1l
print n2l

删除了字符'a'、'd'和'k':

> python test.py 
Lists before loop:
['a', 'b', 'd', 'j', 'e', 'k']
['d', 'o', 'a', 'r', 'h', 's', 'n', 'k']
Lists after loop:
['b', 'j', 'e', '0', '0', '0']
['o', 'r', 'h', 's', 'n', '1', '1', '1']

- Andrew Walker

---

好的，我认为它可以运行...但是当我有 name1 = "naveen" name2 = "darshana"它不起作用！！ - oktapodi

Answer 4

你的代码很可能会失败，因为你从列表中的任何位置弹出常见字母，但是将替换值（“0”和“1”）添加到列表的末尾。它们应该分别位于位置i和j。

因此，循环应该像这样：

for i in range(len(n1l)):
   for j in range(len(n2l)):
         if n1l[i] == n2l[j] and n1l[i] not in ("0", "1"):
               print "common letter ", n1l[i]
               # Replace i-th and j-th element
               n1l[i] = "0"
               n2l[j] = "1"

无论如何，还有更多“Pythonic”的方法，这些方法已经在其他答案中展示过了。

编辑：已测试并且也适用于name1 =“naveen” / name2 =“darshana”。

- AndiDog

Answer 5

这里有一些非常（在我看来相当优雅）的代码，可以在O(n)时间内运行。如果单词1中有N个字母x，则它会从单词2中删除前N个x（反之亦然）- 我认为这就是你想要的，但我可能错了。

from collections import defaultdict

def build(s, chars_s, chars_t):
    """Return characters of s, with duplicate characters from t removed."""
    for i, char in enumerate(s):
        indexes_s, indexes_t = chars_s[char], chars_t[char]
        if len(indexes_s) > len(indexes_t) and i >= indexes_s[len(indexes_t)]:
            yield char

def rm_dup(a, b):
    """Pairwise remove duplicate letters in a and b."""
    chars_a, chars_b = defaultdict(list), defaultdict(list)
    for i, char in enumerate(a): chars_a[char].append(i)
    for i, char in enumerate(b): chars_b[char].append(i)
    return (''.join(build(a, chars_a, chars_b)),
            ''.join(build(b, chars_b, chars_a)))

print rm_dup('naveen', 'darshana')

- user97370

Answer 6

你的代码可能无法按照你的期望工作，因为它正在删除成对的字母。例如，当你看到一个a时，你会从单词中删除两个a...

- Bear