0

アイテムのセットがあり、そこからDISSIMILARタプルを選択します（非類似のタプルの定義については後で詳しく説明します）。セットには潜在的に数千のアイテムが含まれる可能性がありますが、通常は数百のアイテムしか含まれません。

元のセットからN個のアイテムを選択してNタプルを形成できるようにする一般的なアルゴリズムを作成しようとしています。選択したNタプルの新しいセットはDISSIMILARである必要があります。

NタプルAは、次の場合にのみ、別のNタプルBとは異なると言われます。

  • Aで発生するすべてのペア（2タプル）はBには表示されません

注：このアルゴリズムでは、2タプル（ペア）が同じ要素を含む場合、つまり（x、y）が（y、x）と同じであると見なされる場合、2タプル（ペア）はSIMILAR/IDENTICALと見なされます。

これは（可能なバリエーションの）古典的な壺問題です。このアルゴリズムの些細な（擬似コード）実装は、次のようなものになります。

def fetch_unique_tuples(original_set, tuple_size):
    while True:
        # randomly select [tuple_size] items from the set to create first set
        # create a key or hash from the N elements and store in a set
        # store selected N-tuple in a container
        if end_condition_met:
            break

これがこれを行う最も効率的な方法ではないと思います-私はアルゴリズム理論家ではありませんが、このアルゴリズムの実行時間はO（n）ではないと思います-実際、おそらくOである可能性が高いです（n！）。そのようなアルゴを実装するより効率的な方法があり、できれば時間をO（n）に短縮する方法があるかどうか疑問に思います。

実際、Mark Byersが指摘したように、m選択されている要素の数のサイズである2番目の変数があります。これ（つまりm）は通常2から5の間です。

例に関して、これは典型的な（短縮されていますが）例です：

original_list = ['CAGG', 'CTTC', 'ACCT', 'TGCA', 'CCTG', 'CAAA', 'TGCC', 'ACTT', 'TAAT', 'CTTG', 'CGGC', 'GGCC', 'TCCT', 'ATCC', 'ACAG', 'TGAA', 'TTTG', 'ACAA', 'TGTC', 'TGGA', 'CTGC', 'GCTC', 'AGGA', 'TGCT', 'GCGC', 'GCGG', 'AAAG', 'GCTG', 'GCCG', 'ACCA', 'CTCC', 'CACG', 'CATA', 'GGGA', 'CGAG', 'CCCC', 'GGTG', 'AAGT', 'CCAC', 'AACA', 'AATA', 'CGAC', 'GGAA', 'TACC', 'AGTT', 'GTGG', 'CGCA', 'GGGG', 'GAGA', 'AGCC', 'ACCG', 'CCAT', 'AGAC', 'GGGT', 'CAGC', 'GATG', 'TTCG']


# Select 3-tuples from the original list should produce a list (or set) similar to:

    [('CAGG', 'CTTC', 'ACCT')
     ('CAGG', 'TGCA', 'CCTG')
     ('CAGG', 'CAAA', 'TGCC')
     ('CAGG', 'ACTT', 'ACCT')
     ('CAGG', 'CTTG', 'CGGC')
     ....
     ('CTTC', 'TGCA', 'CAAA')
    ]

[[編集]]

実際、出力例を作成する際に、UNIQUENESSに対して以前に与えた定義が正しくないことに気づきました。この発見の結果として、定義を更新し、代わりにDISSIMILARITYの新しいメトリックを導入しました。

4

3 に答える 3

1

これは、アルゴリズムの簡単な実装です。私も理論家ではありませんが、アルゴリズムが大好きです。この単純な実装は O(n^m) であると思います。ここで、m はディメンション + 組み合わせの何かであり、O(n!) 未満である必要があります。

def combine(elements,n=3):
    from itertools import combinations,product,ifilter

    hashes=[]
    combs=[]
    for p in combinations(elements,n):
        if len(set(p)) == 3 and not any(i in hashes for i in [sorted(i) for i in combinations(p,2)]):
            combs.append(p)
            hashes.extend([sorted(i) for i in combinations(p,2)])
    return combs

elements = ['CAGG', 'CTTC', 'ACCT', 'TGCA', 'CCTG', 'CAAA', 'TGCC', 'ACTT', 'TAAT', 'CTTG', 'CGGC', 'GGCC', 'TCCT', 'ATCC', 'ACAG', 'TGAA', 'TTTG', 'ACAA', 'TGTC', 'TGGA', 'CTGC', 'GCTC', 'AGGA', 'TGCT', 'GCGC', 'GCGG', 'AAAG', 'GCTG', 'GCCG', 'ACCA', 'CTCC', 'CACG', 'CATA', 'GGGA', 'CGAG', 'CCCC', 'GGTG', 'AAGT', 'CCAC', 'AACA', 'AATA', 'CGAC', 'GGAA', 'TACC', 'AGTT', 'GTGG', 'CGCA', 'GGGG', 'GAGA', 'AGCC', 'ACCG', 'CCAT', 'AGAC', 'GGGT', 'CAGC', 'GATG', 'TTCG']
print combine(elements)
于 2012-04-06T12:08:30.237 に答える
1

別のアプローチ、つまり組み合わせの組み合わせを試しました。それはかなり迅速に動作するようです：

def fetch_unique_tuples(original_set, tuple_size):
    from itertools import combinations

    good = []
    used = []
    for i in combinations(original_set,tuple_size):
        lst = list([tuple(sorted(j)) for j in combinations(i,2)])
        if not any(l in used for l in lst):
            used.extend(lst)
            good.append(tuple(sorted(i)))
    return sorted(good)

elements = ['CAGG', 'CTTC', 'ACCT', 'TGCA', 'CCTG', 'CAAA', 'TGCC', 'ACTT', 'TAAT', 'CTTG', 'CGGC', 'GGCC', 'TCCT', 'ATCC', 'ACAG', 'TGAA', 'TTTG', 'ACAA', 'TGTC', 'TGGA', 'CTGC', 'GCTC', 'AGGA', 'TGCT', 'GCGC', 'GCGG', 'AAAG', 'GCTG', 'GCCG', 'ACCA', 'CTCC', 'CACG', 'CATA', 'GGGA', 'CGAG', 'CCCC', 'GGTG', 'AAGT', 'CCAC', 'AACA', 'AATA', 'CGAC', 'GGAA', 'TACC', 'AGTT', 'GTGG', 'CGCA', 'GGGG', 'GAGA', 'AGCC', 'ACCG', 'CCAT', 'AGAC', 'GGGT', 'CAGC', 'GATG', 'TTCG']
uniques = fetch_unique_tuples(elements, 3)
print len(uniques)

len() の機能を失いたくない場合は、簡単にジェネレーターに変換できます。

edit : すべてのタプルと最終的なリストをアルファにするために sorted() を追加しました。

于 2012-04-06T19:26:03.890 に答える
0

M 個の N タプルのセットがペアごとに異なる必要があることを意味すると仮定すると、グラフを使用して「禁止された」ペアを追跡することが道のりのようです。

import random
def select_tuples(original, N, M):
  used = {}
  first = random.sample(original, N)
  updateUsed(used, first)
  answer = [first]
  for i in xrange(M):
    notFound = True
    while notFound:
      remaining = set(original)
      thisTuple = []
      for j in xrange(N):
        if not remaining:
          break
        candidate = random.choice(remaining)
        remaining.remove(candidate)
        for adjacent in used[candidate]:
          remaining.remove(adjacent)
      else:
        notFound = False
    answer.append(thisTuple)
    updateUsed(used, thisTuple)
  return answer

def updateUsed(used, selected):
  for x in selected:
    if x not in used:
      used[x] = []
    for y in selected:
      if y != x:
        used[x].append(y)

これはO(MN^2) 私が思うようなものです。Mタプルのそれぞれについて、N*(N-1)/2もう使用できない禁止されたペアを導入しているので、それよりもはるかにうまくできるとは思えません。

于 2012-04-06T21:07:23.523 に答える