3

次の例のように、いくつかのシーケンスをマージしようとしています。

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

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

指定されたシーケンスはすべて、同じ重複のないシーケンス (指定されていません) のサブシーケンスです。'four'および例のように順序を決定できない場合は、'five'逆にすることもできますが、どちらの解決策でも問題ありません。

この問題は複数の配列アラインメントに似ていますが、より制限されている (重複がない、交差エッジがない) ため、(アルゴリズム的に) より簡単な解決策があると思います。例えば。すべての要素の結合から開始する場合、要素を並べ替えるだけで済みますが、入力シーケンスから基になる順序を推測する適切な方法を見つけることができないようです。

例はPythonであり、望ましい解決策もあるでしょうが、問題は一般的なアルゴリズムの性質です。

4

3 に答える 3

2

これは、あなたが望むことをするべき非常に非効率的な方法です:

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)

出力：

('ゼロ', 13)
('1', 12)
('2', 6)
('3', 3)
('4', 1)
('5', 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これはメモ化される可能性があり、キーのスコアを一度だけ決定する必要があるため、これは非効率的です。これは、おそらくバックトラッキングを介して行います。値が空のリストであるキーのスコアを計算し、逆方向に作業します。現在の実装では、いくつかのキーのスコアを複数回決定します。

注: これにより保証されるのは、要素のスコアが「期待される」場所よりも低くならないということだけです。たとえば、

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

Into the mix はリストone-point-fiveの上に配置fourされますが、 で 1 回しか参照していvないため、より良い仕事をするための十分なコンテキストがありません。

于 2015-04-04T21:59:39.373 に答える
1

完全を期すために、これが私が問題を解決した方法です。

@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']
于 2015-04-05T22:19:26.290 に答える
0

あなたの問題は、配列内のすべての組み合わせのペアが一緒に推移的な関係if a>b and b>c then a>cを持っているという離散数学の関係に関するものです。そのため、次のリストを作成できます。したがって、長さ 5 のセットでは、最小の要素はこれらのペアのうちの 4 つに含まれる必要があります。そのため、最初の要素でグループ化されたこれらのペアを最初に作成する必要があります。これにより、moduleから関数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)]

four or five最初の部分で4,2,34 or 3 を見つけたので、次は 1 を見つけるだけfourですしたがって、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)]
于 2015-04-04T22:19:59.763 に答える