Как да приложим претеглено разбъркване

Наскоро написах някакъв код, който смятах за много неефективен, но тъй като включваше само няколко стойности, го приех. Все пак се интересувам от по-добър алгоритъм за следното:

Сумата Избрах

  1. Списък с X обекта, на всеки от тях е присвоено „тегло“
  2. Обобщете тежестите
  3. Генерирайте произволно число от 0 до сумата
  4. Итератирайте през обектите, като извадите тежестта им от сумата, докато сумата не е положителна
  5. Премахнете обекта от списъка, след което го добавете в края на новия списък

Всички елементи 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 е генератор, така че можете ефективно да вземете проби от най-добрите елементи. Ако искате да смесите целия масив, просто прегледайте генератора до изчерпване (използвайки функцията list).

АКТУАЛИЗАЦИЯ:

Претеглена произволна извадка (2005; Efraimidis, Spirakis) предоставя много елегантен алгоритъм за това. Внедряването е супер просто и също работи в O (n log (n)):

РЕДАКТИРАНЕ: Този отговор не интерпретира тежестите, както се очаква. С други думи, елемент от тегло 2 не е два пъти по-вероятно да бъде първостепенен от елемент от тегло 1.

Един от начините за разбъркване на списък е да присвоите произволни числа на всеки елемент от списъка и да ги сортирате по тези номера. Можем да разширим тази идея, просто изберете претеглени случайни числа. Например можете да използвате произволно () * тегло. Различните избори ще доведат до различни разпределения.