Виникла потреба в "швидкому" алгоритмі перебору всіляких розміщень K одиниць в N розрядах. Трохи погуглити, але так і не знайшов алгоритмів без двічі вкладених циклів. Але ж хочеться отримати функцію для "вироблення" наступної комбінації на основі попередньої. Та й зберігати одиниці і нулі бажано не в рядках (побайтно), а в багаторозрядних числах (побитно). В цьому випадку, звичайно, виникає питання розрядності чисел, як обмеження на параметр N. тоді використовуємо числа розрядності 64, 128, 256 біт і т.д. Наприклад, можна скористатися класом big_int в складі бібліотеки Boost. Парканом на око всілякі варіанти розміщення 3-ох одиниць в 5-ти розрядах і порядок перебору цих варіантів:
опис алгоритму
Разом 10 варіантів (число сполучень з п'яти по три). Візуально алгоритм виглядає як пробігає зліва направо одиниця. Наведемо його формально з використанням рекурсії:
1) Якщо найправіший символ "0", то знаходимо серед всіх одиниць найправішу і зрушуємо її на 1 позицію вправо.
2) Якщо найправіший символ "1", то відрубуємо найправіший символ і відправляємо отриману комбінацію (довжини N-1 з K-1 одиницями) на п.1 алгоритму. В отриманому значенні знаходимо найправішу одиницю і вписуємо вирізану раніше одиницю відразу після неї.
Завдання необхідних операцій на мові C ++
При зберіганні комбінації в багаторозрядних змінних нам знадобляться наступні операції:
а) Операція визначення значення молодшого розряду
б) Операція зсуву вправо наймолодшій одиниці, з недоторканністю більш старших розрядів.
в) Операція дописування одиниці праворуч від наймолодшій одиниці.
Тепер метод генерації першої комбінації. K одиниць зсуваються вправо на (N-K) позицій.
Головний метод для обчислення комбінації реалізує описаний нами алгоритм:
доповнення
1) Замість функцій (б) і (в) можна використовувати макроси.
(Акуратніше з вкладеним викликом макросів! - напоровся проте)
2) Акуратніше з типами констант:
(1 <<48) не равно (0x01000000000000)
(__int64 (1) <<48) равно (0x01000000000000)
Дуже рекомендую цей матеріал: Bit Twiddling Hacks