Объединить последовательности уникальных элементов

Question

Я пытаюсь объединить несколько последовательностей, как в следующем примере:

x = ['one', 'two', 'four'] 
y = ['two', 'three', 'five'] 
z = ['one', 'three', 'four'] 

merged = ['one', 'two', 'three', 'four', 'five'] 

Приведенные все последовательности подпоследовательность же, дублируют свободную последовательность (которая не является данный). Если порядок не может быть определен - как в случае с 'four' и 'five' в примере, который также может быть инвертирован - любое решение в порядке.

Проблема напоминает множественное выравнивание последовательностей, но я подозреваю, что существует (алгоритмически) более простое решение, поскольку оно более ограничено (без дубликатов, без пересекающихся границ). Например. когда я начинаю с объединения всех элементов, мне нужно будет только упорядочить элементы, но я не могу найти достойный способ вывести базовый порядок из входных последовательностей.

Пример в Python и желаемое решение также будет, но проблема имеет общий алгоритмический характер.

Answer 1

Вот очень неэффективный метод, который должен делать то, что вы хотите:

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 может быть сохранен в памяти, так что вам нужно было только определить счет ключа один раз. Вы, скорее всего, сделаете это с помощью backtracking - вычислите десятки ключей, где значение было пустым, и работайте назад. В текущей реализации он несколько раз определяет счет для некоторых ключей.

Примечание: Все это гарантирует, что оценка элемента не будет ниже, чем там, где она «ожидается». Например, добавление

v = ['one-point-five', 'four'] 

В смесь поместит one-point-five выше four в списке, но так как вы только ссылаться на него один раз, в v, там не хватает контекста, чтобы сделать лучшую работу.

Answer 2

Ваша проблема заключается в соотношении в дискретной математике, что все пары комбинаций в ваших массивах имеют переходное отношение вместе это значение if a>b and b>c then a>c.поэтому вы можете создать следующие списки, поэтому в наборе с длиной 5 наименьший элемент должен быть в 4 из этих пар (если у нас есть такое количество пар для одного), так что сначала нам нужно создать эти пары, которые обрабатываются первым элементом для этой цели мы можем использовать groupby и chain функции из модуля itertools:

>>> 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, так что теперь нам просто нужно найти 1, что его может быть four or five .now мы идем на вторую часть, что мы должны найти последовательность с длиной 4 or 3, что four - 3, так что 4-й элемент найден таким образом, 5-й элемент должен быть five.

Edit: как более элегантный и быстрый способ вы можете сделать работу с 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)] 

Answer 3

Просто для полноты картины, это то, как я в конечном итоге решение проблемы:

Как было отмечено @DSM, эта проблема относится к топологической сортировке. Там есть сторонние модули, например. toposort (простой Python, без зависимостей).

Последовательности должны быть преобразованы в формат отображения, аналогичный тому, который использовался и использовался в других ответах. 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']