Як здійснити зважене перетасовку

Нещодавно я написав деякий код, який, на мій погляд, був дуже неефективним, але оскільки він містив лише кілька значень, я прийняв його. Однак мене все-таки цікавить кращий алгоритм для наступного:

Список X об'єктів, кожному з них присвоєна "вага"
Підсумуйте ваги
Створіть випадкове число від 0 до суми
Перебирайте предмети, віднімаючи їх вагу від суми, поки сума не буде додатною
Видаліть об’єкт зі списку, а потім додайте його в кінець нового списку

Елементи 2, 4 і 5 займають n часу, і тому це алгоритм O (n ^ 2).

Чи можна його вдосконалити?

Як приклад зваженого перемішування, елемент, швидше за все, буде спереду з більшою вагою.

Приклад (я згенерую випадкові числа, щоб зробити це реальним):

6 предметів вагою 6,5,4,3,2,1; Сума дорівнює 21

Я вибрав 19: 19-6-5-4-3-2 = -1, тому 2 виходить на перше місце, зараз вага становить 6,5,4,3,1; Сума дорівнює 19

Я вибрав 16 16-6-5-4-3 = -2:, отже, 3 переходить до другої позиції, вага зараз 6,5,4,1; Сума дорівнює 16

Я вибрав 3: 3-6 = -3, тож 6 переходить на третю позицію, вага зараз становить 5,4,1; Сума дорівнює 10

Я вибрав 8:, 8-5-4 = -1, таким чином 4 переходить до четвертої позиції, зараз ваги 5.1; Сума дорівнює 6

Я вибрав 5:, 5-5 = 0, тож 5 переходить на п’яту позицію, вага зараз дорівнює 1; Сума дорівнює 1

Я вибрав 1:, 1-1 = 0, тому 1 переходить до останньої позиції, я більше не маю ваги, закінчую

Це можна реалізувати в O (n log (n)) за допомогою дерева.

Спочатку створіть деревоподібну структуру, зберігаючи в кожному вузлі сукупну суму всіх нащадкових вузлів праворуч і ліворуч від кожного вузла.

Для вибірки елемента рекурсивно виконайте вибірку з кореневого вузла, використовуючи поточні суми, щоб вирішити, чи повертаєте ви поточний вузол, лівий вузол чи правий вузол. Кожного разу, коли ви берете вибірку вузла, встановлюйте його вагу рівним нулю, а також оновлюйте батьківські вузли.

Ось моя реалізація в Python:

weigthed_shuffle - це генератор, тому ви можете ефективно відібрати k найкращих елементів. Якщо ви хочете змішати весь масив, просто перебирайте генератор до вичерпання (за допомогою функції списку).

ОНОВЛЕННЯ:

Зважена випадкова вибірка (2005; Efraimidis, Spirakis) забезпечує дуже елегантний алгоритм для цього. Реалізація надзвичайно проста, а також працює в O (n log (n)):

РЕДАГУВАТИ: Ця відповідь не інтерпретує ваги, як очікувалося. Іншими словами, предмет ваги 2 не вдвічі частіше є простим, ніж предмет ваги 1.

Один із способів перемішати список - це присвоїти випадкові числа кожному елементу у списку та відсортувати їх за цими номерами. Ми можемо продовжити цю ідею, просто виберіть зважені випадкові числа. Наприклад, ви можете використовувати випадкову () * вагу. Різні варіанти спричинять різні розподіли.

У чомусь на зразок Python це має бути настільки просто, як:

Будьте обережні, щоб не оцінювати ключі більше одного разу, оскільки вони матимуть різні значення.

Перш за все, давайте відштовхуємося від того, що вага даного елемента у списку, який потрібно відсортувати, є постійною. Це не зміниться між ітераціями. Якщо так, то. ну це більша проблема.

Наприклад, давайте використаємо колоду карт, де ми хочемо зважити карти обличчям вперед. вага (картка) = картка. Підсумовуючи, якщо ми не знаємо, розподіл ваги дійсно дорівнює O (n) один раз.

Ці елементи зберігаються у відсортованій структурі, такій як модифікація в індексованому списку переходів, так що всі індекси рівня доступні з даного вузла:

Однак у цьому випадку кожен вузол також займає стільки місця, скільки його вага.

Тепер, коли ви шукаєте карту в цьому списку, ви можете перейти до її позиції у списку за час O (log n) і видалити її зі пов’язаних списків за час O (1). Гаразд, можливо, це не O (1), це може бути O (log log n) (мені слід подумати про це набагато більше). Видалення 6-го вузла у наведеному вище прикладі вимагало б оновлення всіх чотирьох рівнів - і ці чотири рівні не залежать від кількості елементів у списку (залежно від того, як ви реалізуєте рівні).

Вага елемента постійний, ми можемо просто обійтися без sum - = вага (видалений), який знову перетинає структуру.

Отже, у вас є одна вартість O (n) і пошукове значення O (log n) і вартість видалення з O (1). Це стає O (n) + n * O (log n) + n * O (1), що дає загальну ефективність O (n log n).

Давайте розглянемо це з картами, тому що це те, що я використав вище.

Це дуже маленька колода, на якій всього 4 карти. Повинно бути легко зрозуміти, як це можна продовжити. З 52 картами ідеальна структура мала б 6 рівнів (журнал 2 (52)

= 6), хоча, якщо заглибитися в списки стрибків, це може бути зменшено до меншої кількості.

Сума всіх ваг дорівнює 10. Отже, ви отримуєте випадкове число [1 . 10) і його 4. Ви переглядаєте список стрибків, щоб знайти предмет, який знаходиться на стелі (4). Оскільки 4 менше 10, ви переходите з вищого рівня на другий рівень. Четверо - це більше 3, отже, зараз у нас два алмази. 4 менше 3 + 7, тому ми опускаємось на нижній рівень, а 4 менше 3 + 3, отже, у нас є 3 алмази.

Після вилучення 3-х діамантів із конструкції структура тепер виглядає так:

Ви помітите, що вузли займають кількість "простору", пропорційного їх вазі в конструкції. Це дозволяє зважений вибір.

Оскільки це наближається до збалансованого двійкового дерева, пошук у ньому не потребує сканування нижнього шару (який би мав значення O (n)), а замість цього підйом дозволяє швидко пропустити структуру, щоб знайти те, що ви шукаєте.

Багато чого з цього можна зробити за допомогою якогось збалансованого дерева. Проблема полягає в тому, що перебалансування структури при видаленні вузла стає заплутаним, оскільки це не є типовою деревною структурою, і домогосподарству доводиться пам’ятати, що 4 алмази тепер переміщено з позицій [6 7 8 9] в [3 4 5 6 ] може коштувати дорожче, ніж переваги деревної структури.

Однак, незважаючи на те, що список переходів наближається до бінарного дерева, оскільки він здатний переходити до списку за час O (log n), він має просту роботу зі зв'язаним списком.

Це не означає, що легко зробити все це (завжди слідкуйте за будь-якими посиланнями, які потрібно редагувати під час видалення елемента), але це означає лише оновлення кількості рівнів, які у вас є., А також їх посилань ніж направо на відповідній структурі дерева.