Страницы

Поиск по вопросам

вторник, 21 мая 2019 г.

Генерация сочетаний

Необходимо построить сочетания всех возможных размеров так, чтобы элементы в сочетаниях не совпадали (1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,1,2; 3,2,1 - одни и те же сочетания)
Например, даны числа: 1,2,3,4
Ответ:
1 2 3 4
12 13 14 23 24 34
123 124 134
1234
Можно и псевдокод.


Ответ

Вы забыли еще 234 и пустое сочетание :)
Берем число, каждому биту которого соответствует один элемент вашего множества, и проходим все числа в цикле - от 00..00 до 11..11. Все. Каждое число - это одно "сочетание" (вообще-то это генерация всех подмножеств данного множества), которое строим, выбирая элементы, соответствующие единичным битам...
Например, ваше 1234 - соответственно, 4-битное число...
0000 пустое множество 0001 1 0010 2 0011 12 0100 3 .... 1110 432 1111 4321

Комментариев нет:

Отправить комментарий