0

我有一组项目，我想从中选择 DISSIMILAR 元组（稍后将详细介绍不同元组的定义）。该集合可能包含数千个项目，但通常仅包含数百个。

我正在尝试编写一个通用算法，该算法将允许我从原始集合中选择 N 个项目来形成一个 N 元组。新的一组选定的 N 元组应该是DISSIMILAR。

当且仅当：

  • 出现在 A 中的每一对（2 元组）都不会出现在 B 中

注意：对于这个算法，如果一个 2 元组（对）包含相同的元素，则认为它是 SIMILAR/IDENTICAL，即 (x,y) 被认为与 (y,x) 相同。

这是经典Urn Problem的（可能的变体） 。该算法的简单（伪代码）实现将类似于以下内容

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，即被选择元素数量的大小。这个（即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() 的功能，可以轻松转换为生成器。

编辑：添加了额外的 sorted() 以使所有元组和最终列表 alpha。

于 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 回答