我需要一种算法来找到我所说的“有序组合”(如果有的话,也许有人知道它的真实名称)。 当然,我已经尝试过自己提出一种算法,但我真的陷入困境。
它应该如何工作:
给定 2 个元素列表(不是集合,这里顺序很重要!),保证包含相同的元素,所有元素都是有序组合。 有序组合是 2 元组、3 元组、...n 元组(N 没有限制)元素,它们在两个列表中以相同的顺序出现。
- 一个元素完全有可能在列表中出现多次。
- 但保证一个列表中的每个元素在另一个列表中至少出现一次。
- 如果输出包含多次组合,没关系。
我不太确定这是否清楚,所以这里有多个例子: (列表1、列表2、预期结果、注释)
ASDF
ADSF
Result: AS, AD, AF, SF, DF, ASF, ADF
注意:ASD 不是有效结果,因为此组合的第二个列表中无法包含升序索引
ADSD
ASDD
Result: AD, AS, AD, DD, SD, ASD, ADD
注意:AD 出现两次,因为它可以从索引 1,2 和 1,4 以及第二个列表 1,3 和 1,4 中创建。但如果它只出现一次也是正确的。此外,D 按顺序在两个列表中出现两次,因此这也允许 ADD 作为有效组合。
SDFG
SDFG
Result: SD, SF, SG, DF, DG, FG, SDF, SFG, SDG, DFG, SDFG,
注意:相同的输入;所有组合都是可能的
ABCDEFG
GFEDCBA
Result: <empty>
注意:两个列表中不存在以相同顺序出现的组合
QWRRRRRRR
WRQ
Result: WR
注意:两组中唯一以相同顺序出现的组合是 WR
注释:
- 虽然这是一种与语言无关的算法,但我更喜欢包含 C# 或伪代码的答案,以便我能够理解它们。
- 我意识到较长的组合总是由较短的组合组成。示例:只有当 SD 和 DF 也可能时,SDF 才是有效结果。也许这有助于通过从较短的组合构建较长的组合来提高算法的性能。
- 速度在这里非常重要。这是实时使用的算法!
- 如果不清楚算法的工作原理,请发表评论。我将添加一个示例来澄清它。
- 也许这个问题已经为人所知并已解决,但我不知道它的正确名称。
最佳答案
我将这个问题描述为枚举两个字符串的公共(public)子序列。作为第一步,创建一个像这样的方法,它不确定地选择第一个字母并递归(Python,抱歉)。
def commonsubseqs(word1, word2, prefix=''):
if len(prefix) >= 2:
print(prefix)
for letter in set(word1) & set(word2): # set intersection
# figure out what's left after consuming the first instance of letter
remainder1 = word1[word1.index(letter) + 1:]
remainder2 = word2[word2.index(letter) + 1:]
# take letter and recurse
commonsubseqs(remainder1, remainder2, prefix + letter)
如果这个简单的解决方案对您来说不够快,那么可以按如下方式进行改进。对于这两个单词的每对后缀,我们预先计算递归调用列表。再次使用 Python:
def commonsubseqshelper(table, prefix, i, j):
if len(prefix) >= 2:
print(''.join(prefix))
for (letter, i1, j1) in table[i][j]:
prefix.append(letter)
commonsubseqshelper(table, prefix, i1, j1)
del prefix[-1] # delete the last item
def commonsubseqs(word1, word2):
table = [[[(letter, word1.index(letter, i) + 1, word2.index(letter, j) + 1)
for letter in set(word1[i:]) & set(word2[j:])]
for j in range(len(word2) + 1)] # 0..len(word2)
for i in range(len(word1) + 1)] # 0..len(word1)
commonsubseqshelper(table, [], 0, 0)
这个多项式时间预处理步骤将枚举速度提高到渐近最优。
关于查找 "ordered combinations"的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25576212/