обчислювальна складність
Ця реалізація вимагає k операцій множення і ділення. Тобто його обчислювальна складність дорівнює O (k).
Алгоритм працює швидше, але у нього є певні недоліки. Навіть при невеликих n він викликає переповнення цілих чисел, так як примножує n на біноміальний коефіцієнт, який являє собою досить велике число. Так, якщо Integer - беззнаковое ціле число, що складається з чотирьох байт, то переповнення виникає вже при n = 50 і k = 8.
Генерація випадкового поєднання методом випадкової перестановки
Перший алгоритм, який ми опишемо, є досить простим і очевидним.
Ідея алгоритму полягає в наступному. Візьмемо список об'єктів з n елементів G = (g1. G2. ... gn). Це буде наше безліч, з якого ми будемо будувати поєднання. Поєднанням H з n по k назвемо рядок з n бітів, в якій рівно k одиниць. Одиниця на i-му місці означає, що в даний поєднання входить елемент gi. Наприклад, H може бути одно H '= (1, ... 1, 0, ... 0), де перші k елементів одиниці, решта - нулі. Тоді випадкова злука H - це випадкова перестановка рядки H '.
У STL є функція random_shuffle (). яка генерує випадкову перестановку.
Перша функція використовує генератор випадкових чисел за замовчуванням, друга - в якості параметра. RandomNumberGenerator - це функціональний об'єкт, який в якості параметра приймає число n типу, відповідного результату операції Last-First, і повертає випадкове число r: 0≤r Реалізація алгоритму досить проста, так як вона грунтується на генерації випадкової перестановки - алгоритму, у якого вже є готова реалізація. Даний алгоритм реалізують кілька функцій. Ось вони. RandomFunc - функціональний об'єкт, який при виклику RandomFunc (Max) повертає випадкове число x з діапазону 0≤x Функції з назвою RandomCombination () генерують хаотичне нагромадження методом випадкової перестановки в форматі «підмножина». Параметр n (де він вказаний) - це розмір вихідного безлічі, k - розмір генерованого поєднання. RandomAccessIterator - итератор довільного доступу, за допомогою параметрів такого типу задається вхідна послідовність. OutputIterator - итератор виведення, в який записується результат. InputIterator - итератор введення. Перші дві такі функції отримують вхідну послідовність за допомогою ітераторів довільного доступу. Її довжину вони обчислюють, застосовуючи вираз std :: distance (First, Last). Власне, на цьому і закінчується їх використання як ітераторів довільного доступу. Якщо надається итератор не є ітератором довільного доступу, то можна використовувати функції, які приймають параметр n - довжину вхідної послідовності. В іншому всі ці функції однакові. Дуже важливо передавати функціональний об'єкт RandomFunc по посиланню, а не за значенням, так як більшість генераторів випадкових чисел використовують свій внутрішній стан. Таким чином, якщо вихідний генератор, який передається в функцію, скопіювати, а не передати по посиланню, два виклики RandomCombination () поспіль можуть привести до однакового результату. Нижче приведена реалізація описаних функцій. Ідея алгоритму полягає в тому, щоб якимось чином пронумерувати всі поєднання з n по k, тобто поставити у відповідність кожному числу i з діапазону 0≤i Отже, спочатку визначимо відношення порядку на безлічі поєднань з n по k. Для наочності будемо записувати поєднання в форматі «список з bool». Наше відношення порядку буде лексикографічним. Для наочності розташуємо, наприклад, все поєднання з 7 по 3 в зазначеному порядку. Якщо уважно подивитися на ці поєднання, то в їх порядку легко простежити рекуррентную залежність. Розглянемо перший елемент поєднань. Спочатку йдуть всі поєднання, в яких він дорівнює 0, потім - все, в яких він дорівнює 1. Причому порядок проходження сполучень в обох цих підгрупах повторюється - в кожній підгрупі спочатку йдуть поєднання, в яких другий елемент - 0, а потім - в яких він дорівнює 1 і т.д. Кількість сполучень, в яких перший елемент дорівнює нулю, дорівнює числу сполучень з n-1 по k, а кількість сполучень, в яких перший елемент дорівнює одиниці, дорівнює числу сполучень з n-1 по k-1 (відповідь на питання, чому так відбувається , описаний в примітці до другого властивості біноміального коефіцієнта). Отже, якщо номер поєднання менше числа сполучень з n-1 по k, то перший елемент множини не входить в даний поєднання, інакше - входить. Узагальнюючи вищесказане, приходимо до наступного алгоритму. Вхідні дані. CombNumber - номер поєднання, n, k - розмір вхідного безлічі і розмір поєднання, Src - вхідна множина (послідовність), з якого вибирається поєднання, Dest - вихідна безліч, в яке в результаті роботи алгоритму буде записано поєднання. Вихідні дані. поєднання, записане в Dest. Даний алгоритм в значній мірі використовує обчислення біноміального коефіцієнта, тому його ефективність залежить від ефективності обчислення біноміального коефіцієнта. Максимальна кількість ітерацій одно n (мінімальне - k). Крім того, використовується k операцій присвоювання. Є також незначні операції типу инкремента і віднімання цілих чисел. Їх також не більше n. Припустимо, що в якості алгоритму обчислення біноміального коефіцієнта використовується перший описаний в статті алгоритм (який використовує додаткову пам'ять). Його тимчасова складність дорівнює O (nk), якщо необхідне значення C (n, k) не вирахував до моменту виклику, і O (1), якщо воно вже знаходиться в кеші. Тоді при обчисленні C (n, k), виходячи з алгоритму, всі інші необхідні значення біноміального коефіцієнта також обчислюються. Тобто, по суті, біноміальний коефіцієнт необхідно обчислити за все один раз, в усі наступні виклики значення беруться з кеша. Таким чином, тимчасова складність всього алгоритму вибору випадкового поєднання становить O (nk), якщо кеш не заповнений, і O (n), якщо він заповнений потрібними нам біноміальними коефіцієнтами. Забігаючи наперед, скажемо, що при наявності заповненого кеша описуваний алгоритм ефективніший, ніж алгоритм генерації поєднання методом випадкової перестановки. Тобто, якщо він викликається багаторазово (наприклад, хоча б 5-10 разів), можна отримати виграш в продуктивності (заповнення кеша окупається). Якщо ж необхідно згенерувати лише одне поєднання, то, звичайно, краще застосувати алгоритм генерації випадкового поєднання методом випадкової перестановки. Функцій, що відносяться до даного алгоритму, досить багато, але не слід лякатися - всі вони однотипні. На параметри GetBinomialCoefficient, RandomFunc, n, k, Src, Dest, First, Last, типи RandomAccessIterator, InputIterator, OutputIterator накладаються ті ж обмеження і вимоги, що і в функціях, що реалізують алгоритм генерації методом випадкової перестановки. Параметр CombNumber (там, де він є) повинен задовольняти умові 0≤CombNumber≤C (n, k) - це порядковий номер поєднання. Функції з назвою CombinationFromNumberBool () генерують поєднання по заданому номеру в форматі «список з bool». На вхід їм подається номер поєднання, його розмір, можливо, функціональний об'єкт, який обчислює число поєднань (якщо його немає, то такий вибирається за замовчуванням). На виході вони повинні записати в Dest послідовність елементів, синтаксично сумісних з bool (яким можна присвоїти значення типу bool). Функції з назвою CombinationFromNumber () генерують поєднання по заданому номеру в форматі «підмножина». На вхід вони приймають той же, що і CombinationFromNumberBool (), а також итератор (ітератори), що описує вхідну послідовність. На виході вони повинні сформувати потрібну підпослідовність (іншими словами, поєднання) і записати її в Dest. Функції з назвами RandomCombinationFromNumberBool () і RandomCombinationFromNumber () генерують випадкові поєднання в форматах «список з bool» і «підмножина», відповідно. На вхід мають ті ж параметри, що і відповідні їм функції без префікса «Random», за винятком параметра RandomFunc, який передається замість CombNumber. Викликають відповідні їм функції (без префікса «Random») з параметром CombNumber = RandomFunc (GetBinomialCoefficient (n, k)). Нижче приведена реалізація описаних функцій. Реалізовані функції використовують семантику ітераторів STL і, отже, їх можна використовувати однаково зручно як зі звичайними масивами, так і з контейнерами стандартної бібліотеки шаблонів C ++ і навіть з одними типами даних. Найкраще різні варіанти виконання функцій можна продемонструвати за допомогою наступної невеликої програми. Файл Demo.cpp з програмою можна скачати за посиланням в кінці статті. Алгоритм генерації випадкового поєднання в форматі «підмножина» методом випадкової перестановки створює vector Алгоритм генерації поєднання по його номеру сам по собі додаткової пам'яті не використовує. Але він використовує функцію GetBinomialCoefficient (), яка (в одному з варіантів алгоритму GetBinomialCoefficient) використовує O (nk) байт пам'яті для кешування значень коефіцієнта. Як і зазначалося раніше, продуктивність алгоритмів в різних умовах відрізняється. Щоб показати порівняльну продуктивність реалізованих алгоритмів, напишемо просту програму. Тут CTimer - це клас, що вимірює час. Його код задля стислості наводиться. 1 - це вимір часу роботи простого алгоритму RandomCombination (). 2 - це вимір часу роботи алгоритму RandomCombinationFromNumber () за умови, що кеш значень біноміального коефіцієнта не заповнений. Як згодом ми побачимо, за такої умови час його роботи є неприйнятним. 3 - це вимір часу роботи алгоритму RandomCombinationFromNumber () за умови, що кеш значень біноміального коефіцієнта заповнений. 4 зроблено для порівняння часу роботи двох алгоритмів в реальних умовах. Сумарно тут RandomCombinationFromNumber () викликається той же число раз, що і RandomCombination () в першому прикладі, але кеш значень біноміального коефіцієнта скидається раз в 25 викликів. Ось висновок програми на процесорі Core 2 Duo E7500. З цього можна зробити наступні висновки. Таким чином, якщо для n = 500 і k = 275 застосовувати RandomCombinationFromNumber (), то він окупить себе в сенсі часу виконання за C викликів, де C<25. Если n и k меньше, то C также уменьшается. Например, для n=250 и k=135 RandomCombinationFromNumber() окупается уже за C<12 вызовов. Эти данные, разумеется, справедливы лишь для целых 32-битных чисел. В общем случае мы имеем объекты некоторых классов, которые, возможно, копируются медленнее. Тогда C может уменьшиться ещё больше. Покладемо, існує деяка заздалегідь відома і не змінюється послідовність елементів довжини n. Будь-яким чином, неважливо яким, обрана підпослідовність цієї послідовності, в якій елементи не повторюються. Її довжину позначимо через k. Очевидно, зазначена підпослідовність є одним з поєднань з n по k. Отже, її можна згенерувати описаним раніше алгоритмом генерації поєднання за порядковим номером поєднання. Так як алгоритм є детермінованим, підпослідовність повністю визначається вихідною послідовністю і номером поєднання. Підсумовуючи вищесказане, можна легко реалізувати алгоритм збереження підпослідовності. Для цього нам бракує ще однієї функції - NumberFromCombination (). Щоб зберегти поєднання, нам необхідно записати в файл лише параметри k і номер поєднання. Таким чином, наприклад, зберігаючи список з k 32-бітних чисел, ми економимо 4k-8 байт, записуючи всього 8 байт замість 4k (зрозуміло, за умови, що k і n досить малі, щоб номер поєднання не перевищував 2 32 -1) . Нижче приведена реалізація оголошених функцій. В описаній статті розглянуті два різних підходи до генерації випадкових поєднань без повторень. Також наведені порівняльні результати продуктивності методів і з'ясовані обставини, при яких потрібно використовувати той чи інший алгоритм. Реалізована бібліотека дозволяє без проблем використовувати алгоритми для всіх STL-сумісних контейнерів і масивів.Оцінка тимчасової складності
Реалізація
опис функцій
Вихідний код
Генерація поєднання по його номеру
Оцінка тимчасової складності
Реалізація
опис функцій
Вихідний код
Використання реалізованих функцій
Порівняння двох алгоритмів
споживання пам'яті
продуктивність
Деякі корисні властивості алгоритму генерації поєднання по його номеру
Компактне зберігання поєднань
висновок
Схожі статті