python - 生成所有独特的三元组

问题描述

有一系列的三元组：

[[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12],[13, 14, 15]]

（可以比这更长）。它们都是独一无二的。

问：生成这些三元组的所有可能组合的有效方法是什么，以使之前遇到的所有项目都不会再次“相遇”？

因此，例如在这个序列中，没有一个三元组包含之前遇到的任何项目：

[[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12],[13, 14, 15]]
[[1, 5, 9], [4, 8, 12], [7, 11, 15], [10, 14, 3],[2, 6, 13]]
[[1, 4, 7], [5, 8, 11], [9, 12, 15], [10, 13, 2],[14, 3, 6]]

但这一个行不通：

[[1, 5, 9], [4, 6, 12], [7, 11, 15], [10, 14, 3],[2, 8, 13]]

因为4和6从第二个三连音之前一直在同一个三连音中，特别[4, 5, 6]是在第一个记录中

我认为可以通过从初始序列中选择随机三元组来完成random.sample(l, 3)，然后检查这个三元组以前是否没有使用过，但它看起来效率很低，我想知道是否有更好的方法。

更新：：：

我意识到发布一个丑陋且低效的代码仍然有效，只是为了说明我在说什么：

import random
import itertools

z = list(range(1, 10))
group_size = 3
superset = list()



def check_not_met(x):
    for i in superset:
        if set(x).issubset(set(i)):
            return False
    return True


def check_not_anyone_met(x):
    for i in itertools.combinations(x, 2):
        if not check_not_met(i):
            return False
    return True


subsession_matrices = list()


def generating_subsession(seq):
    subglobal = list()
    while seq:
        x = a[-group_size:]
        if check_not_anyone_met(x):
            subglobal.append(x)
        else:
            return False
        del seq[-group_size:]
    return subglobal

for j in range(10000):
    a = z.copy()
    random.shuffle(a)
    subsession_matrix = generating_subsession(a)
    if not subsession_matrix:
        continue
    else:
        subsession_matrices.append(subsession_matrix)
        superset.extend(subsession_matrix)

print(subsession_matrices)

输出是：

[[3, 7, 1], [8, 2, 4], [6, 5, 9]]
[[8, 1, 9], [3, 5, 2], [7, 6, 4]]
[[3, 8, 6], [1, 4, 5], [7, 2, 9]]
[[8, 5, 7], [1, 2, 6], [3, 9, 4]]

标签： pythonrandomcombinatorics

您可以创建一个递归函数：

d = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12],[13, 14, 15]]
def create_triplet(nums, original, current = []):
  if len(current) == 3:
    yield sorted(current)
  else:
    for i in nums:
      yield from create_triplet(nums, original, current+[i])

_original = [d]
def triplets(source, current=[]):
  if len(current) == len(d):
     _original.append(current)
     yield current
  else:
     _flattened, seen = [i for b in current for i in b], []
     _options = list(create_triplet([i for i in source if i not in current], _original))
     for i in _options:
       if i not in seen and all(all(c not in b for c in i) for b in current) and all(i not in c for c in _original):
          _test = current+[i]
          if all(all(sum(h in c for h in i) < 2 for i in _test for c in b) for b in _original):
            yield from triplets(source, current=_test)
            seen.append(i)

_ = list(triplets([i for b in d for i in b]))
print(_original)

输出：

[[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12], [13, 14, 15]]
[[1, 4, 7], [2, 5, 8], [3, 10, 13], [6, 11, 14], [9, 12, 15]]
[[1, 5, 9], [2, 4, 10], [3, 6, 15], [7, 11, 13], [8, 12, 14]]
[[1, 6, 8], [2, 7, 14], [3, 9, 11], [4, 12, 13], [5, 10, 15]]
[[1, 10, 14], [2, 11, 15], [3, 4, 8], [5, 7, 12], [6, 9, 13]]

python - 生成所有独特的三元组

问题描述

解决方案

推荐阅读