合并独特元素的序列
Merge sequences of unique elements
我正在尝试合并多个序列，如下例所示：
x = ['one', 'two', 'four']
y = ['two', 'three', 'five']
z = ['one', 'three', 'four']
merged = ['one', 'two', 'three', 'four', 'five']
给定的序列都是相同的、无重复序列（未给出）的子序列。如果无法确定顺序 - 如示例中的 'four' 和 'five'，也可以颠倒 - 任何一种解决方案都可以。
这个问题类似于多序列比对，但我怀疑有一个（算法上）更简单的解决方案，因为它更受限制（没有重复项，没有交叉边）。例如。当从所有元素的并集开始时，我只需要对元素进行排序——但我似乎找不到一种合适的方法来从输入序列中推断出基本顺序。
示例在 Python 中，所需的解决方案也是，但问题是一般算法性质的。
这是一个非常低效的方法，应该可以满足您的要求：
w = ['zero', 'one']
x = ['one', 'two', 'four']
y = ['two', 'three', 'five']
z = ['one', 'three', 'four']
def get_score(m, k):
v = m[k]
return sum(get_score(m, kk) for kk in v) + 1
m = {}
for lst in [w,x,y,z]:
for (i,src) in enumerate(lst):
if src not in m: m[src] = []
for (j,dst) in enumerate(lst[i+1:]):
m[src].append(dst)
scored_u = [(k,get_score(m,k)) for k in m]
scored_s = sorted(scored_u, key=lambda (k,s): s, reverse=True)
for (k,s) in scored_s:
print(k,s)
输出：
('zero', 13)
('one', 12)
('two', 6)
('three', 3)
('four', 1)
('five', 1)
该方法首先构建一个映射 m，其中键是列表的术语，值是被发现具有 的术语列表钥匙.
所以在这种情况下，m 看起来像：
{
'three': ['five', 'four'],
'two': ['four', 'three', 'five'],
'four': [],
'zero': ['one'],
'five': [],
'one': ['two', 'four', 'three', 'four']
}
从那里，它计算每个键的分数。得分由跟随它的元素的得分总和加上 1 来定义。
所以
get_score(m, 'four') = 1
get_score(m, 'five') = 1
# and thus
get_score(m, 'three') = 3 # (1(four) + 1(five) + 1)
它对输入列表中找到的每个元素执行此操作（在我的例子中 w,x,y,z）并计算总分，然后按分数降序排序。
我说这个效率低，因为这个get_score可以被记忆，所以你只需要确定一个键的分数一次。您可能会通过回溯来做到这一点——计算值为空列表的键的分数，然后向后工作。在当前的实现中，它多次确定某些键的分数。
注意：所有这些保证元素的分数不会低于它 "is expected" 的分数。例如，添加
v = ['one-point-five', 'four']
混合会将 one-point-five 放在列表中的 four 上方，但由于您只引用它一次，在 v 中，没有足够的上下文来做更好的工作。
你的问题是关于离散数学中的关系，你的数组中的所有组合对都具有 传递关系 在一起，这意味着 if a>b and b>c then a>c。因此，您可以创建以下列表，因此在长度为 5 的集合中，最小元素应该在这些对中的 4 个中——如果我们有这样数量的对。所以首先我们需要创建这些由第一个元素分组的对，为此我们可以使用 itertools 模块中的 groupby 和 chain 函数：
>>> from itertools import combinations,chain,groupby
>>> from operator import itemgetter
>>> l1= [list(g) for _,g in groupby(sorted(chain.from_iterable(combinations(i,2) for i in [x,y,z])),key=itemgetter(0))]
[[('one', 'four'), ('one', 'four'), ('one', 'three'), ('one', 'two')], [('three', 'five'), ('three', 'four')], [('two', 'five'), ('two', 'four'), ('two', 'three')]]
因此，如果我们有 len 4 ,3 ,2, 1 的组，那么我们就找到了答案，但如果我们没有找到这样的序列，我们可以反向执行前面的计算以找到我们的元素如果我们找到一个关系组 len 4 它是最大的数字并且 ...!
>>> l2= [list(g) for _,g in groupby(sorted(chain.from_iterable(combinations(i,2) for i in [x,y,z]),key=itemgetter(1)),key=itemgetter(1))]
[[('two', 'five'), ('three', 'five')], [('one', 'four'), ('two', 'four'), ('one', 'four'), ('three', 'four')], [('two', 'three'), ('one', 'three')], [('one', 'two')]]
因此我们可以执行以下操作：
注意我们需要用set(zip(*i)[1])得到我们特定元素与之相关的元素集合，然后用len计算这些元素的数量。
>>> [(i[0][0],len(set(zip(*i)[1]))) for i in l1]
[('one', 3), ('three', 2), ('two', 3)]
>>> [(i[0][1],len(set(zip(*i)[0]))) for i in l2]
[('five', 2), ('four', 3), ('three', 2), ('two', 1)]
在第一部分我们找到了 4,2,3 所以现在我们只需要找到它可能是 four or five 的 1。现在我们进入第二部分我们需要找到一个长度的序列4 or 3 four 是 3 所以找到第 4 个元素因此第 5 个元素应该是 five.
编辑：作为一种更优雅、更快捷的方式，您可以使用 collections.defaultdict 来完成这项工作：
>>> from collections import defaultdict
>>> d=defaultdict(set)
>>> for i,j in chain.from_iterable(combinations(i,2) for i in [x,y,z]) :
... d[i].add(j)
...
>>> d
defaultdict(<type 'set'>, {'three': set(['four', 'five']), 'two': set(['four', 'five', 'three']), 'one': set(['four', 'two', 'three'])})
>>> l1=[(k,len(v)) for k,v in d.items()]
>>> l1
[('three', 2), ('two', 3), ('one', 3)]
>>> d=defaultdict(set)
>>> for i,j in chain.from_iterable(combinations(i,2) for i in [x,y,z]) :
... d[j].add(i) #create dict reversely
...
>>> l2=[(k,len(v)) for k,v in d.items()]
>>> l2
[('four', 3), ('five', 2), ('two', 1), ('three', 2)]
为了完整起见，这就是我最终解决问题的方式：
正如@DSM所指出的，这个问题与拓扑排序有关。那里有第三方模块，例如。 toposort（普通 Python，无依赖项）。
序列需要转换成映射格式，类似于其他答案中的used/suggested。 toposort_flatten() 然后做剩下的：
from collections import defaultdict
from toposort import toposort_flatten
def merge_seqs(*seqs):
'''Merge sequences that share a hidden order.'''
order_map = defaultdict(set)
for s in seqs:
for i, elem in enumerate(s):
order_map[elem].update(s[:i])
return toposort_flatten(dict(order_map))
以上面的例子：
>>> w = ['zero', 'one']
>>> x = ['one', 'two', 'four']
>>> y = ['two', 'three', 'five']
>>> z = ['one', 'three', 'four']
>>> merge_seqs(w, x, y, z)
['zero', 'one', 'two', 'three', 'five', 'four']
我正在尝试合并多个序列，如下例所示：
x = ['one', 'two', 'four']
y = ['two', 'three', 'five']
z = ['one', 'three', 'four']
merged = ['one', 'two', 'three', 'four', 'five']
给定的序列都是相同的、无重复序列（未给出）的子序列。如果无法确定顺序 - 如示例中的 'four' 和 'five'，也可以颠倒 - 任何一种解决方案都可以。
这个问题类似于多序列比对，但我怀疑有一个（算法上）更简单的解决方案，因为它更受限制（没有重复项，没有交叉边）。例如。当从所有元素的并集开始时，我只需要对元素进行排序——但我似乎找不到一种合适的方法来从输入序列中推断出基本顺序。
示例在 Python 中，所需的解决方案也是，但问题是一般算法性质的。
这是一个非常低效的方法，应该可以满足您的要求：
w = ['zero', 'one']
x = ['one', 'two', 'four']
y = ['two', 'three', 'five']
z = ['one', 'three', 'four']
def get_score(m, k):
v = m[k]
return sum(get_score(m, kk) for kk in v) + 1
m = {}
for lst in [w,x,y,z]:
for (i,src) in enumerate(lst):
if src not in m: m[src] = []
for (j,dst) in enumerate(lst[i+1:]):
m[src].append(dst)
scored_u = [(k,get_score(m,k)) for k in m]
scored_s = sorted(scored_u, key=lambda (k,s): s, reverse=True)
for (k,s) in scored_s:
print(k,s)
输出：
('zero', 13)
('one', 12)
('two', 6)
('three', 3)
('four', 1)
('five', 1)
该方法首先构建一个映射 m，其中键是列表的术语，值是被发现具有 的术语列表钥匙.
所以在这种情况下，m 看起来像：
{
'three': ['five', 'four'],
'two': ['four', 'three', 'five'],
'four': [],
'zero': ['one'],
'five': [],
'one': ['two', 'four', 'three', 'four']
}
从那里，它计算每个键的分数。得分由跟随它的元素的得分总和加上 1 来定义。
所以
get_score(m, 'four') = 1
get_score(m, 'five') = 1
# and thus
get_score(m, 'three') = 3 # (1(four) + 1(five) + 1)
它对输入列表中找到的每个元素执行此操作（在我的例子中 w,x,y,z）并计算总分，然后按分数降序排序。
我说这个效率低，因为这个get_score可以被记忆，所以你只需要确定一个键的分数一次。您可能会通过回溯来做到这一点——计算值为空列表的键的分数，然后向后工作。在当前的实现中，它多次确定某些键的分数。
注意：所有这些保证元素的分数不会低于它 "is expected" 的分数。例如，添加
v = ['one-point-five', 'four']
混合会将 one-point-five 放在列表中的 four 上方，但由于您只引用它一次，在 v 中，没有足够的上下文来做更好的工作。
你的问题是关于离散数学中的关系，你的数组中的所有组合对都具有 传递关系 在一起，这意味着 if a>b and b>c then a>c。因此，您可以创建以下列表，因此在长度为 5 的集合中，最小元素应该在这些对中的 4 个中——如果我们有这样数量的对。所以首先我们需要创建这些由第一个元素分组的对，为此我们可以使用 itertools 模块中的 groupby 和 chain 函数：
>>> from itertools import combinations,chain,groupby
>>> from operator import itemgetter
>>> l1= [list(g) for _,g in groupby(sorted(chain.from_iterable(combinations(i,2) for i in [x,y,z])),key=itemgetter(0))]
[[('one', 'four'), ('one', 'four'), ('one', 'three'), ('one', 'two')], [('three', 'five'), ('three', 'four')], [('two', 'five'), ('two', 'four'), ('two', 'three')]]
因此，如果我们有 len 4 ,3 ,2, 1 的组，那么我们就找到了答案，但如果我们没有找到这样的序列，我们可以反向执行前面的计算以找到我们的元素如果我们找到一个关系组 len 4 它是最大的数字并且 ...!
>>> l2= [list(g) for _,g in groupby(sorted(chain.from_iterable(combinations(i,2) for i in [x,y,z]),key=itemgetter(1)),key=itemgetter(1))]
[[('two', 'five'), ('three', 'five')], [('one', 'four'), ('two', 'four'), ('one', 'four'), ('three', 'four')], [('two', 'three'), ('one', 'three')], [('one', 'two')]]
因此我们可以执行以下操作：
注意我们需要用set(zip(*i)[1])得到我们特定元素与之相关的元素集合，然后用len计算这些元素的数量。
>>> [(i[0][0],len(set(zip(*i)[1]))) for i in l1]
[('one', 3), ('three', 2), ('two', 3)]
>>> [(i[0][1],len(set(zip(*i)[0]))) for i in l2]
[('five', 2), ('four', 3), ('three', 2), ('two', 1)]
在第一部分我们找到了 4,2,3 所以现在我们只需要找到它可能是 four or five 的 1。现在我们进入第二部分我们需要找到一个长度的序列4 or 3 four 是 3 所以找到第 4 个元素因此第 5 个元素应该是 five.
编辑：作为一种更优雅、更快捷的方式，您可以使用 collections.defaultdict 来完成这项工作：
>>> from collections import defaultdict
>>> d=defaultdict(set)
>>> for i,j in chain.from_iterable(combinations(i,2) for i in [x,y,z]) :
... d[i].add(j)
...
>>> d
defaultdict(<type 'set'>, {'three': set(['four', 'five']), 'two': set(['four', 'five', 'three']), 'one': set(['four', 'two', 'three'])})
>>> l1=[(k,len(v)) for k,v in d.items()]
>>> l1
[('three', 2), ('two', 3), ('one', 3)]
>>> d=defaultdict(set)
>>> for i,j in chain.from_iterable(combinations(i,2) for i in [x,y,z]) :
... d[j].add(i) #create dict reversely
...
>>> l2=[(k,len(v)) for k,v in d.items()]
>>> l2
[('four', 3), ('five', 2), ('two', 1), ('three', 2)]
为了完整起见，这就是我最终解决问题的方式：
正如@DSM所指出的，这个问题与拓扑排序有关。那里有第三方模块，例如。 toposort（普通 Python，无依赖项）。
序列需要转换成映射格式，类似于其他答案中的used/suggested。 toposort_flatten() 然后做剩下的：
from collections import defaultdict
from toposort import toposort_flatten
def merge_seqs(*seqs):
'''Merge sequences that share a hidden order.'''
order_map = defaultdict(set)
for s in seqs:
for i, elem in enumerate(s):
order_map[elem].update(s[:i])
return toposort_flatten(dict(order_map))
以上面的例子：
>>> w = ['zero', 'one']
>>> x = ['one', 'two', 'four']
>>> y = ['two', 'three', 'five']
>>> z = ['one', 'three', 'four']
>>> merge_seqs(w, x, y, z)
['zero', 'one', 'two', 'three', 'five', 'four']