Python -列表上的简单算法任务(求职面试的标准问题)

Question

有2个输入列表L和M，例如：

L =  ['a',     'ab',  'bba']
M = ['baa', 'aa',  'bb']

如何获得两个非空的输出表U和V，使得：''.join(U) == ''.join(V)) is True，U中的每个元素都在L中，V中的每个元素都在M中？

例如，上面两个输入列表的一种可能的解决方案是：

U=['bba', 'ab', 'bba', 'a']
V=['bb', 'aa', 'bb', 'baa']

因为

 'bbaabbbaa' == 'bbaabbbaa' is True

和every element of ['bba', 'ab', 'bba', 'a'] is in ['a', 'ab', 'bba']

和every element of ['bb', 'aa', 'bb', 'baa'] is in ['baa', 'aa', 'bb']

1)创建一个算法，它将找到至少一个解(U和V)。

2)它能在O(n)的n=len(L+M)中求解吗？

:wq

Answer 1

你在寻找什么--所有(可数不清的)可能的解决方案？“最短的”(通过某种度量)非空解决方案，或者相等的最短解决方案的集合，或者...？

因为，如果任何解决方案都可以，则将U和V都设置为[]满足所有规定的条件，并且启动O(1)；-)。

编辑：好的，那么，开个玩笑，这里有一个很好的对称解决方案来打印可计数的无限非空解决方案中的前十个：

import itertools as it
import collections

L = ['a', 'ab', 'bba']
M = ['baa', 'aa', 'bb']

def cmbs(L=L, M=M):
  Ucans = collections.defaultdict(list)
  Vcans = collections.defaultdict(list)
  sides = (L, Vcans, Ucans), (M, Ucans, Vcans)
  for i in it.count(1):
    for k, (G, Ocans, Tcans) in enumerate(sides):
      for u in it.product(G, repeat=i):
        j = ''.join(u)
        if j in Ocans:
          for samp in Ocans[j]:
            result = samp, u
            yield result[1-k], result[k]
        Tcans[j].append(u)

if __name__ == '__main__':
  for x, y in it.islice(cmbs(), 10):
    print x, y, ''.join(x), ''.join(y)

它会发出

('a', 'a') ('aa',) aa aa
('bba', 'a') ('bb', 'aa') bbaa bbaa
('a', 'a', 'a', 'a') ('aa', 'aa') aaaa aaaa
('a', 'a', 'bba', 'a') ('aa', 'bb', 'aa') aabbaa aabbaa
('a', 'ab', 'a', 'a') ('aa', 'baa') aabaa aabaa
('a', 'ab', 'bba', 'a') ('aa', 'bb', 'baa') aabbbaa aabbbaa
('bba', 'a', 'a', 'a') ('bb', 'aa', 'aa') bbaaaa bbaaaa
('bba', 'ab', 'a', 'a') ('bb', 'aa', 'baa') bbaabaa bbaabaa
('bba', 'ab', 'bba', 'a') ('bb', 'aa', 'bb', 'baa') bbaabbbaa bbaabbbaa
('bba', 'a', 'bba', 'a') ('bb', 'aa', 'bb', 'aa') bbaabbaa bbaabbaa

我不确定O(N)在一个有无数个解的问题的上下文中是什么意思--这里的N应该是什么？！-)

编辑2：更改为使用(默认)列表的字典，以确保即使相同的联接字符串可以从一个输入集合中以>1种方式生成(该条件在样本输入中没有出现，因此样本输出不受影响)，它也可以找到所有的解决方案；例如，如果L为['a', 'aa']，则任何a >1的联接字符串都可以通过多种方式生成--当前解决方案将在此类联接字符串与为M生成的字符串匹配时以多种方式发出所有这些解决方案，而前一个解决方案仅发出其中之一。

Answer 2

这是我的尝试！我认为它能找到所有的解决方案。

from itertools import product 
m = 5   # top limit of elements in output lists
sumsets = lambda s1, s2: s1 | s2

for u in reduce(sumsets, [set(product(L, repeat=i)) for i in  range(1, m+1)]):
    for v in reduce(sumsets, [set(product(M, repeat=i)) for i in  range(1, m+1)]):
            if ''.join(u) == ''.join(v):
                print u, v  

输出: U、V

('a', 'a', 'a', 'a') ('aa', 'aa')
('a', 'a') ('aa',)
('a', 'a', 'bba', 'a') ('aa', 'bb', 'aa')
('bba', 'a', 'a', 'a') ('bb', 'aa', 'aa')
('bba', 'a') ('bb', 'aa')
('bba', 'ab', 'a', 'a') ('bb', 'aa', 'baa')
('a', 'ab', 'a', 'a') ('aa', 'baa')
('a', 'ab', 'bba', 'a') ('aa', 'bb', 'baa')
('bba', 'ab', 'bba', 'a') ('bb', 'aa', 'bb', 'baa')
('bba', 'a', 'bba', 'a') ('bb', 'aa', 'bb', 'aa')

Answer 3

这就是众所周知的Post Correspondence Problem，正如其他人所说的那样，它是不可决定的。