Алгоритм генерации всех предзаказов / слабых порядков размера n

Question

Я ищу эффективный на полпути алгоритм, который при заданном входном наборе генерирует из него все общие отношения предварительного заказа (или, что то же самое, все слабые порядки). Вы также можете назвать все это преференциальным расположением n помеченных элементов.

Я уже пытался реализовать это, сначала генерируя все перестановки размера n, а затем сворачивая подпоследовательности их с помощью '~', но это очень неэффективно из-за большого количества дубликатов, и я также пропустил некоторые результаты. Размер задается числами Фубини 1, 1, 3, 13, 75, 541, 4683, 47293, 545835, ... (OEIS номер A000670) и быстро растет с n. Мне нужны только первые несколько, скажем, пока n=8.

Пример: для A={a, b, c} с n=3 результат составляет 13 предзаказов:

b> a> c, b> a ~ c, b> c> a, b ~ c> a, c> b> a, c> a ~ b, c> a> b, a ~ c> b, a> c> b, a> b ~ c, a> b> c, a ~ b> c, a ~ b ~ c

Answer 1

Не слишком сложно. В Python 3:

import itertools

def weakorders(A):
    if not A:  # i.e., A is empty
        yield []
        return
    for k in range(1, len(A) + 1):
        for B in itertools.combinations(A, k):  # i.e., all nonempty subsets B
            for order in weakorders(set(A) - set(B)):
                yield [B] + order

Вызвать, например, list(weakorders(range(8))),