Листинг порядка n элементов в k-категориях

Question

У меня есть n событий {v1, ..., vn}, которые будут возникать в течение определенного времени {t1, ..., tk}, где k < = n (могут возникнуть множественные в то же время), и мне нужно указать каждый способ, которым это может произойти.

Например, если у нас было 2 события, я мог бы:

{v1 < v2}, {v2 < v1} (2 раза)

{v1 = v2} (1 раз)

Если бы мы имели 3 события, я мог бы иметь все 6 упорядоченности с 3 различными временами, плюс

{v1 = v2 < v3}, {v1 = v3 < v2}, {v2 = v3 < v1}, { v1 < v2 = v3}, {v2 < v1 = v3}, {v3 < v1 = v2} (2 раза)

{v1 = v2 = v3} (1 раз)

Так что я на самом деле не нужны все возможные группировки, так как {v1 = v2 < v3} эквивалентно, например, {v2 = v1 < v3}.

Я думал, что мне нужно сгенерировать все перестановки n событий для случая, когда k = n в любом случае, что у меня есть способ, поэтому, возможно, я мог бы создать возможные категории поверх этого и затем обрезать дубликаты, но я не уверен, как проверить, например, что {v3 = v4 = v2 < v1 = v6 < v5} - это дубликат того, что мы приняли ранее эффективно.

Возможно, вы можете быть более систематичным при работе в списке перестановок и выяснить, как удалить дубликаты без повторной проверки с тем списком, который мы заархивировали до сих пор?

Я понимаю, что это не будет работать в разумные сроки даже для умеренно большого количества событий, но я хотел бы сделать это как можно выше, 6 будет хорошо, 8 или 10 еще лучше.

Я использую MATLAB, но я готов преследовать любой язык, который кто-то может предложить как оптимальный для такой проблемы, и любые советы по общей методологии языка-агностики очень приветствуются и оцениваются.

Answer 1

Вот один подход (код следующим образом):

Генерация перестановок v1…vn с помощью любого стандартного алгоритма (есть п перестановок, очевидно!). Для каждой перестановки vp1…vpn перечислить все возможные формулы:

vp1 R1 vp2 R2 vp3 … Rn-1 vpn

где Ri всегда может быть <, а также может быть = если pi < pi+1.

Например, если п 3:

v1 v2 v3: v1 < v2 < v3; v1 < v2 = v3; v1 = v2 < v3; v1 = v2 = v3 
v1 v3 v2: v1 < v3 < v2; v1 = v3 < v2 
v2 v1 v3: v2 < v1 < v3; v2 < v1 = v3 
v2 v3 v1: v2 < v3 < v1; v2 = v3 < v1 
v3 v1 v2: v3 < v1 < v2; v3 < v1 = v2 
v3 v2 v1: v3 < v2 < v1 

Вы можете сделать перечисление отношений рекурсивно (что было эффективно, как я это сделал выше, вручную).

Редактировать: Это Sloane sequence A000670, ссылка содержит множество возможных полезных ссылок. При n = 9 счет равен 7087261, что кажется чрезвычайно практичным; для n = 10, это 102247563, что легко находится в рамках современных вычислений на рабочем столе. (Однако я не знаю о Matlab).

Вот реализация питон:

def rels(perm): 
    if len(perm) == 1: 
    yield perm 
    else: 
    for p in rels(perm[1:]): 
     yield (perm[0], '<') + p 
     if perm[0] < perm[1]: 
     yield (perm[0], '=') + p 

def orders(n): 
    return reduce(lambda a,b:a+b, 
       [[i for i in rels(p)] for p in itertools.permutations(range(n))]) 

>>> print '\n'.join(map(repr,[o for o in orders(4)])) 
(0, '<', 1, '<', 2, '<', 3) 
(0, '=', 1, '<', 2, '<', 3) 
(0, '<', 1, '=', 2, '<', 3) 
(0, '=', 1, '=', 2, '<', 3) 
(0, '<', 1, '<', 2, '=', 3) 
(0, '=', 1, '<', 2, '=', 3) 
(0, '<', 1, '=', 2, '=', 3) 
(0, '=', 1, '=', 2, '=', 3) 
(0, '<', 1, '<', 3, '<', 2) 
(0, '=', 1, '<', 3, '<', 2) 
(0, '<', 1, '=', 3, '<', 2) 
(0, '=', 1, '=', 3, '<', 2) 
(0, '<', 2, '<', 1, '<', 3) 
(0, '=', 2, '<', 1, '<', 3) 
(0, '<', 2, '<', 1, '=', 3) 
(0, '=', 2, '<', 1, '=', 3) 
(0, '<', 2, '<', 3, '<', 1) 
(0, '=', 2, '<', 3, '<', 1) 
(0, '<', 2, '=', 3, '<', 1) 
(0, '=', 2, '=', 3, '<', 1) 
(0, '<', 3, '<', 1, '<', 2) 
(0, '=', 3, '<', 1, '<', 2) 
(0, '<', 3, '<', 1, '=', 2) 
(0, '=', 3, '<', 1, '=', 2) 
(0, '<', 3, '<', 2, '<', 1) 
(0, '=', 3, '<', 2, '<', 1) 
(1, '<', 0, '<', 2, '<', 3) 
(1, '<', 0, '=', 2, '<', 3) 
(1, '<', 0, '<', 2, '=', 3) 
(1, '<', 0, '=', 2, '=', 3) 
(1, '<', 0, '<', 3, '<', 2) 
(1, '<', 0, '=', 3, '<', 2) 
(1, '<', 2, '<', 0, '<', 3) 
(1, '=', 2, '<', 0, '<', 3) 
(1, '<', 2, '<', 0, '=', 3) 
(1, '=', 2, '<', 0, '=', 3) 
(1, '<', 2, '<', 3, '<', 0) 
(1, '=', 2, '<', 3, '<', 0) 
(1, '<', 2, '=', 3, '<', 0) 
(1, '=', 2, '=', 3, '<', 0) 
(1, '<', 3, '<', 0, '<', 2) 
(1, '=', 3, '<', 0, '<', 2) 
(1, '<', 3, '<', 0, '=', 2) 
(1, '=', 3, '<', 0, '=', 2) 
(1, '<', 3, '<', 2, '<', 0) 
(1, '=', 3, '<', 2, '<', 0) 
(2, '<', 0, '<', 1, '<', 3) 
(2, '<', 0, '=', 1, '<', 3) 
(2, '<', 0, '<', 1, '=', 3) 
(2, '<', 0, '=', 1, '=', 3) 
(2, '<', 0, '<', 3, '<', 1) 
(2, '<', 0, '=', 3, '<', 1) 
(2, '<', 1, '<', 0, '<', 3) 
(2, '<', 1, '<', 0, '=', 3) 
(2, '<', 1, '<', 3, '<', 0) 
(2, '<', 1, '=', 3, '<', 0) 
(2, '<', 3, '<', 0, '<', 1) 
(2, '=', 3, '<', 0, '<', 1) 
(2, '<', 3, '<', 0, '=', 1) 
(2, '=', 3, '<', 0, '=', 1) 
(2, '<', 3, '<', 1, '<', 0) 
(2, '=', 3, '<', 1, '<', 0) 
(3, '<', 0, '<', 1, '<', 2) 
(3, '<', 0, '=', 1, '<', 2) 
(3, '<', 0, '<', 1, '=', 2) 
(3, '<', 0, '=', 1, '=', 2) 
(3, '<', 0, '<', 2, '<', 1) 
(3, '<', 0, '=', 2, '<', 1) 
(3, '<', 1, '<', 0, '<', 2) 
(3, '<', 1, '<', 0, '=', 2) 
(3, '<', 1, '<', 2, '<', 0) 
(3, '<', 1, '=', 2, '<', 0) 
(3, '<', 2, '<', 0, '<', 1) 
(3, '<', 2, '<', 0, '=', 1) 
(3, '<', 2, '<', 1, '<', 0)