Python:(采样与替换):从集合中提取不同 N 元组集合的有效算法

Question

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

我

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

一个 N 元组

A 被称为与另一个 N 元组 B 不同，当且仅当：

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

注意：对于此算法，如果 2 元组（对）包含相同的元素，则将其视为相似/相同，即 （x，y） 被视为与 （y，x） 相同。

这是一个（可能的变体）经典的骨灰盒问题。该算法的简单（伪代码）实现将是类似于

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）。

实际上，正如马克·拜尔斯指出的那样，还有第二个变量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 给出的定义是不正确的。由于这一发现，我已经更新了我的定义，并引入了一个新的差异性指标。

Answer 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。

Answer 2

这是算法的一个简单实现。我也不是理论家，但我喜欢算法。我认为这个简单的实现是 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)

Answer 3

假设你的意思是 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禁止的对你不能再使用