генерировать все уникальные тройки

Question

есть серия триплетов:

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

(может быть длиннее).Все они уникальны.

Q: Каков эффективный способ генерации всех возможных комбинаций этих триплетов, чтобы ни один из предметов, которые встречались ранее, не «встречался» снова?

Так, например, в этой последовательности ни один из триплетов не содержит элементов, которые встречались ранее:

[[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]]

Answer 1

Вы можете рекурсивно заполнять каждое число в списке триплетов по одному, следя за числами, которые каждое число видело в поле набора, и возвращать комбинацию, если ей удастся заполнить все числа.Используйте цикл while, чтобы продолжать делать это, пока не будет найдено больше комбинаций:

from copy import deepcopy

def unique(items, size=3):
    def find_unique(items, size, seen, filled):
        filled_set = set(item for group in filled for item in group)
        if len(filled_set) == len(items):
            return filled, seen
        candidates = items - filled_set
        if not filled or len(filled[-1]) == size:
            filled.append([])
        for incumbent in filled[-1]:
            candidates -= seen[incumbent]
        new_seen = deepcopy(seen)
        new_filled = deepcopy(filled)
        for candidate in candidates:
            for incumbent in new_filled[-1]:
                new_seen[incumbent].add(candidate)
            new_seen[candidate].update(filled[-1])
            new_filled[-1].append(candidate)
            combinations, real_seen = find_unique(items, size, new_seen, new_filled)
            if combinations:
                return combinations, real_seen
            del new_filled[len(filled):]
            del new_filled[-1][len(filled[-1]):]
            for incumbent in new_filled[-1]:
                new_seen[candidate].remove(incumbent)
                new_seen[incumbent].remove(candidate)
        return None, None

    combinations = [items]
    seen = {}
    for group in items:
        for item in group:
            seen.setdefault(item, set()).update(group)
    while True:
        combination, seen = find_unique(seen.keys(), size, seen, [])
        if not combination:
            break
        combinations.append(combination)
    return combinations

, чтобы:

unique([[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, 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]]]

Answer 2

Вы можете создать рекурсивную функцию:

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]]

Answer 3

ОК, это началось как комментарий, но он был слишком большим, чтобы быть полезным.

Прежде всего, по вашему определению, не существует уникальной комбинации.Позвольте мне объяснить:

Поскольку вы не хотите повторять любые 2 числа, которые уже появились в триплете, порядок, в котором они появляются, имеет значение и меняет комбинацию.

Пример, проясняющий ситуацию:

Учитывая, что вы начинаете с:

[[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, 10], [4, 8, 12], [7, 11, 15], [9, 14, 3],[ 2, 6, 13]]

(просто поменяйте 9 на 10 во второй комбинации).Это, однако, делает 1 и 5 снова непригодными для использования в том же триплете, поэтому в этой последовательности ваша вторая комбинация

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

не может появиться в моей последовательности.

Итак, как вы определяетеуникальным?В вашем определении есть проблема, я думаю.Я даже не уверен, что порядок имеет какое-либо значение для длины последовательности.

проверьте, не использовался ли этот триплет раньше

Если вы не заинтересованыв уникальной последовательности, а вы хотите, чтобы ваше ограничение применялось к последовательности и получало как можно больше комбинаций, тогда вышеприведенное не будет работатьВы должны проверить, содержатся ли 2 числа в триплете, если триплет ранее не появлялся.Ваш критерий не сможет определить, что комбинация

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

недопустима, хотя все триплеты раньше не появлялись.

Надеюсь, это поможет.В любом случае, если я что-то неправильно понял, внесите изменения.