LINUX.ORG.RU

Подскажите алгоритм «перемешки с приоритетом» [Решено]

 ,


1

1

подскажите алгоритм «перемешки с приоритетом»

хочу примерно следующее

const result = shuffleWithPriority([{el: 1, priority: 0.1}, {el: 2, priority: 10}, {el: 3, priority: 5}])

где в результате будет скорее всего 2,3,1, иногда 3,2,1, и совсем редко 1,2,3 либо 1,3,2

В идеале готовый код на npm, либо код на js. Но и просто описание подойдет.

По поводу эффективности, не критично, но желательно не больше чем O(n^2)

UPD решение

генерируем [псевдо]случайное число от 1 до <максимальный приоритет>
умножаем приоритет на получившееся число
сортируем в порядке получившихся приоритетов

★★★

ты хотел сказать «распределение, отличное от равномерного»?

Harald ★★★★★ ()

Отсортируй в порядке уменьшения приоритета, затем немного перемешай пары с близкими значениями приоритетов.

Eddy_Em ☆☆☆☆☆ ()

Сразу D&D вспоминаетя, все эти кинжалы 1d4 и кубики с 20ю гранями…

pon4ik ★★★★★ ()

Если ограничить приоритет сверху, по идее подойдёт такой алгоритм:

  • для каждого элемента:
    • генерируем [псевдо]случайное число от 1 до <максимальный приоритет>
    • умножаем приоритет на получившееся число
  • сортируем в порядке получившихся приоритетов
pon4ik ★★★★★ ()

Вероятность встретить единицу первой/второй должна быть супер-мелкой из-за 0.1, или важна лишь последовательности убывания приоритета?

Если первое, то можно напихать их в разном количестве, перемешать и убить последующие повторы. Если второе, то слушай Эдика.

t184256 ★★★★★ ()
Последнее исправление: t184256 (всего исправлений: 1)
Ответ на: комментарий от pon4ik

Круто. Может время позднее, но че-то не догоняю. Почему не от 0 до 1? На что тут влияет этот «максимальный приоритет»?

t184256 ★★★★★ ()
Ответ на: комментарий от t184256

Я просто постарался продолжить аналогию с кубиками. Т.е. самый мелкий приоритет может встать на первое место, но при очень уж особом стечении обстоятельств - когда максимальному приоритету выпало 1, а самому мелкому - максимальное значение.

pon4ik ★★★★★ ()
Ответ на: комментарий от pon4ik

Решение и вправду простое и красивое. Просто константный множитель в нем ни на что не влияет, так что можно еще проще.

UPD: а, у тебя там почему-то от 1 до константы…

t184256 ★★★★★ ()
Последнее исправление: t184256 (всего исправлений: 1)
Ответ на: комментарий от t184256

Возможно ты прав, но во-первых решение просто интуитивное. Во-вторых на практике генерировать псевдослучайное целое число в заданном диапазоне эффективнее чем число с плавающей точкой. А так, если произвести немного дополнительной арфиметики можно избавиться от константы. Вот то, что это проще, это уже спорный вопрос.

pon4ik ★★★★★ ()

генерируем [псевдо]случайное число от 1 до <максимальный приоритет>

Зачем? Просто любое равномерно распределённое случайное число.

slovazap ★★★★★ ()
Ответ на: комментарий от slovazap

Обратите внимание что у данного алгоритма есть одна «неприятная» особенность.

Если у нас есть такие данные

{type: 'apple', priority: 1}
{type: 'orange1', priority: 0.1}
...
{type: 'orangeN', priority: 0.1}

Не важно как много у нас апельсинов, скорее всего на первом месте будет яблоко.

решение которое я применил - я делю, а не умножаю на random(0.0001, 1)

abs ★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.