Разделы набора с четным количеством элементов [дубликаты]

Есть ли эффективный способ перечислить все подразделения набора {1, ... , 2*n} на n пар?

Самая простая идея - перечислить все перестановки, а затем перестановка (a1, a2, ... , a8) означает деление {{a1,a2}, ... , {a7,a8}}. В этой ситуации есть 2^n * n! перестановок для каждого деления. Это O((2n)!).

Можно ли найти более эффективный способ?


algorithm discrete-mathematics
person Maciej Maciej Maciej    schedule 27.10.2015    source источник
comment
Перечислить пары несложно. Если вы допускаете соглашение о перемаркировке индексов наименьшими доступными значениями по порядку после извлечения пары, вы получаете плоскую (а не древовидную) серию выборов между kC2 элементами для k в (2*n до 2 шагов). 2). Затем вы можете сделать выбор, опускаясь от 2*n до 2, и прочитать исходные индексы вверх по цепочке на основе этих вариантов. Компромисс - O (n), а не O (1) время выбора. Позже я соберу код, возможно, для фактического ответа, если меня никто не опередит...   -  person BadZen    schedule 27.10.2015
comment
Спасибо за ответ, но, к сожалению, я не понимаю вашего алгоритма. Буду признателен, если вы напишете какой-нибудь псевдокод.   -  person Maciej Maciej Maciej    schedule 27.10.2015
comment
Имеет ли значение порядок? Если вы перечислите все перестановки, вы получите множество {{x,y}...}, перечисленных отдельно от {{y,x}...}, это то, что вы хотите?   -  person גלעד ברקן    schedule 27.10.2015
comment
Порядок внутри пары не имеет значения, как и порядок пар. Я хочу найти способ перечислить все подразделения {1,...,2*n} на двухэлементные подмножества. Например 1,2 - 3,4 - 5,6 - 7,8 это одно деление 2,1 - 3,4 - 5,6 - 7,8 это одно деление 3,4 - 1,2 - 5,6 - 7,8 тоже такое же деление. Количество всех делений на пары для множества {1,...2*n} равно (2n-1)*(2n-3)*(2n-5)* ... *5*3*1 и I хотел бы перечислить их все каким-то эффективным способом.   -  person Maciej Maciej Maciej    schedule 27.10.2015
comment
Я знаю, что список всех перестановок не является биективным со списком всех подразделений, но есть инъекция из перестановок в подразделения.   -  person Maciej Maciej Maciej    schedule 27.10.2015
comment
Посмотрите на мой ответ здесь: stackoverflow.com /questions/32493769/наборы всех непересекающихся пар/   -  person MBo    schedule 27.10.2015

Ответы (1)


arrow_upward
0
arrow_downward

Вот мой алгоритм карандаша и бумаги:

f(set,result):
  if the set is empty:
    return result
  otherwise:
    pair one item from the set with
    each of the remaining items,
    calling f again with the pair added to
    the result and out of the set

123456
12 34 56
   35 46
   36 45
13 24 56
   25 46
   26 45
14 23 56
   25 36
   26 35
...
person גלעד ברקן    schedule 27.10.2015