3

特定の形式のイベントを使用して空間を生成したい。小さな例で問題を説明しましょう。

イベント a、b、c、d、e、f があるとします。これらのイベントで構成される入力として、3 つの長さのシーケンスがあります。これらのシーケンスから、長さ 6 (イベント数) のシーケンスを生成したいのですが、シーケンス内に要素が繰り返されることはありません。つまり、すべてのイベントが 1 回だけ使用されます。6 つの長さのシーケンスは、いくつかの規則を満たす必要があります。(例で説明)

例：

Input: 
list1:['a','b','c']
list2:['c','d','e']
list3:['b','c','d']
list4:['a','c','g']
list5:['f','g','e']

List1 は、6 長のシーケンスで a の後に b と c が続き、b の後に c が来る、つまり順序​​が変わるとシーケンスも変わることを示しています。同様に List2 は、d と e が c の後に続き、e が d の後に来ることを示しています。すべてのリストが取得され、ルールが記録されます。これらのシーケンスからすべてのルールを抽出した後、ルールに従う 6 つの長さのシーケンスを生成する必要があります。例として;

私たちの場合（簡単にするために）、入力がList1、List2、およびList3であるとしましょう

Input: 
list1:['a','b','c']
list2:['c','d','e']
list3:['b','c','d']

次に、これらのリストの結果は次のとおりです。

['a','b','c','d','e']: 抽出されたこれら 3 つのリストからのすべての規則に従います。たとえば、b と c は a の後に続き、d と e は c の後に続き、c と d は b の後に続きます。ここからの重要な注意: c が a の後に来る必要がある場合、それらは出力シーケンス (6 長さ) で隣接している必要はありません。

6 長のシーケンスが常に存在するとは限りません。まず、そのようなシーケンスが少なくとも 1 つ存在することを確認する必要があります。そうでない場合、アルゴリズムは false を返す必要があります。例として; 入力が Lis1、Lis2、Lis3、Lis4、および Lis5 であると仮定します。

Input: 
list1:['a','b','c']
list2:['c','d','e']
list3:['b','c','d']
list4:['a','c','g']
list5:['e','g','b']

a => b => c => g => b b はそれ自身の後に来ることができないので、それは不可能です。

これらのシーケンスを Python で生成するアルゴリズムが必要です。これまでのところ、効率的なアルゴリズムを考えることができなかったので、今のところコードはありません。より長いシーケンスを見つけるのにも非常に効率的である必要があります。

質問が明確でない場合は、今すぐお問い合わせください。

ありがとう

4

2 に答える 2

3

出発点は次のとおりです。

import networkx as nx
from itertools import tee, izip

list1 = ['a','b','c']
list2 = ['c','d','e']
list3 = ['b','c','d']

g = nx.DiGraph()
for items in [list1, list2, list3]:
    a, b = tee(items)
    next(b)
    g.add_edges_from(izip(a, b))

print nx.topological_sort(g)
# ['a', 'b', 'c', 'd', 'e']

グラフにサイクルが含まれている場合、これは例外を発生させます...

于 2013-08-25T14:02:14.173 に答える
1

モデルを有向非巡回グラフとして構築できます。networkx python ライブラリは、すべてのグラフを処理します。

ランダムな 6 要素シーケンスを生成するには、可能なすべてのシーケンスを列挙し、後で 6 要素を持つシーケンスからランダムに選択します。

（お粗末だが機能する）アルゴリズムのスケッチ：

  1. Jon の例から始めます - グラフを作成し、グラフが DAG であることを確認します
  2. P はノードのベクトルで、最初は空です
  3. グラフからランダムなノードを選択し、そのノードを P に追加します
  4. ランダムな隣接ノードを選択する
  5. 新しいノードを P に追加します
  6. P が目的の長さ (10 または 20 など) の場合、P は有効な結果です。
  7. それ以外の場合は 4 へ
于 2013-08-25T14:03:17.947 に答える