Как реализовать случайное повторение шаффла, но не слишком случайно

Question

У меня есть список n предметов.Я хочу, чтобы алгоритм позволял мне выбирать потенциально бесконечную последовательность элементов из этой коллекции случайным образом, но с парой ограничений:

1. после того, как элемент был выбран, он не должен снова появлятьсяв следующих нескольких пунктах (скажем, в следующих m элементах, с m явно строго <<em> n )
2. вам не нужнослишком долго ждать появления какого-либо элемента - элементы должны появляться в среднем один раз каждые n выборы
3. последовательность должна быть нециклической

В принципе, я хочуалгоритм генерации списка воспроизведения для MP3-плеера с включенными «shuffle» и «repeat», который гарантирует, что он не воспроизводит одну и ту же песню слишком близко к себе, и гарантирует, что он воспроизводит все ваши песни равномерно, без заметногоpattern.

Эти ограничения исключают два очевидных решения из спора:

• Мы не можем просто выбрать rnd ( n ) в качестве индекса для следующего элемента,потому что это не будет гарантией повторениясоперничеству;также может потребоваться много времени, чтобы выбрать некоторые элементы.
• Мы не можем просто перетасовать список с помощью перетасовки Фишера-Йейтса и многократно повторять его, перетасовывая его каждый раз, когда мы достигаем конца;хотя это гарантирует, что предметы появляются не более, чем 2n - 1 , это не полностью предотвращает повторение предметов.

Наивным решением может быть выбор случайным образом, но отказ от выбора, если они произошли в последнем m выборе;это означает сохранение списка m предыдущих пиков и проверку каждого пика по этому списку каждый раз, что делает алгоритм недетерминированным и медленным одновременно - проигрыш-проигрыш.Если я не пропущу что-то очевидное ..

Так что у меня есть алгоритм, которым я сейчас пользуюсь, и я немного недоволен.Я вывел его по аналогии с колодой карт, где у меня есть колода дро и колода сброса.Я начинаю с полного списка, перетасованного, в колоде розыгрыша, колода сброса пуста.Следующий предмет читается с верха колоды розыгрыша, а затем помещается в колоду сброса.Как только стопка сброса достигает определенного размера ( m предметов), я перетасовываю ее и перемещаю в нижнюю часть стопки.

Это соответствует требованию, но это перемешивается один раз м пикап беспокоит меня.Это O (1) обычно, но O (m) один раз в m.В среднем это равняется постоянному времени, но должно быть более чистое решение, которое перетасовывает сбрасывания по ходу дела.

Мне кажется, что это такая простая, общая и общая проблема, она должнаесть один из этих алгоритмов с двумя стволами, как Фишер-Йейтс или Бойер-Мур.Но мой гугл-фу явно не силен, так как мне еще предстоит найти набор терминов, которые определяют местоположение неизбежной статьи ACM 1973 года, которая, вероятно, объясняет, как именно это сделать за O (1) время, и почему мой алгоритм глубоко ошибочен.в некотором роде.

Answer 1

Для создания вашего списка сделайте следующее.Есть ничья и сбросить кучу.Изначально куча сброса пуста.Выберите свой первый предмет наугад из колоды розыгрыша.Добавьте его в список воспроизведения, а затем положите в стопку сброса.Когда в колоде сброса будет m предметов, возьмите последний предмет (наименее использованный в последнее время) из колоды сброса и добавьте его в колоду сброса.Плейлист будет случайным, но без тасования требуется.

Вот он в рубине:

SONGS = [ "Pink Floyd - Wish You Were Here",
          "Radiohead - Bones",
          "Led Zeppelin - Black Dog",
          "The Cure - A Strange Day",
          "Massive Attack - Teardrop",
          "Depeche Mode - Enjoy the Silence",
          "Wilco - Jesus etc." ]

DONT_REPEAT_FOR = 3

def next_item pick, discard
  result = pick.delete_at(rand(pick.count));
  discard.push result
  pick.push(discard.shift) if (discard.count > DONT_REPEAT_FOR)
  result
end

def playlist_of_length n
    discard = []
    pick = SONGS
    playlist = []
    (0..n).each { playlist.push next_item(pick, discard) }
    playlist
end

РЕДАКТИРОВАТЬ: Добавлен метод playlist_of_length, чтобы было понятнее, как вы вызываете next_item для генерацииплейлист

Answer 2

Внедрение алгоритма очереди и визуальная проверка

В Mathematica:

Play[themes_, minCycle_, iterations_] :=
 Module[{l, queue, played},
  l = Range[themes]; 
  queue = {};
  played = {}; (*just for accounting*)

  While [  Length@played < iterations,
   (AppendTo[queue, #]; l = DeleteCases[l, #]) &@RandomChoice[l];
   If[Length[queue] > minCycle, (AppendTo[l, First@queue]; queue = Rest@queue)];
   AppendTo[played, Last@queue]
   ];
  Return[played];
  ]

MatrixPlot[Partition[Play[100, 50, 20000], 100], ColorFunction -> Hue]

Давайте посмотрим, что не существует очевидных повторяющихся шаблонов:

Сравнение циклов различной длины:

Answer 3

После воспроизведения данной песни используйте псевдо-добавление, чтобы поместить ее в конец списка.Вы, вероятно, захотите, чтобы от 1/2 до 2/3 были действительно добавлены, а остальные от 1/3 до 1/2 распространялись на последние 5 или около того элементов в списке.

Очевидно, что это не такработать для очень коротких списков, но должно быть хорошо для списков от 10 и более.

---

Edit (предоставьте более подробную информацию о 'PseudoAppend'):

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

Заданный список [песни]

While(PLAY)
    Play(List[0])
    PseudoAppend(List[], 0)

def PseudoAppend(List[], index)
    # test to verify length of list, valid index, etc.
    song = List[index].delete    # < not safe
    List.append(song)
    target = -1

    While( (random() < (1/3)) && (target > -3) )
        Swap(List[target], List[target-1])
        target -= 1

Удаление только что законченной песни из списка без предварительного создания резервного спискаможет привести к потере информации, но это всего лишь псевдокод, предназначенный для передачи идеи.

Как вы можете видеть, 2/3 времени только что сыгранной песни будут перемещены в конецсписок, и в 1/3 времени она будет перемещаться впереди последней песни.

Из 1/3 вероятности того, что песня будет перемещена вперед, в 2/3 времени она будет перемещаться только впередодной песни, а в другой 1/3 времени она будет перемещаться впереди двух илибольше песен.Вероятность того, что песня переместится на последнюю позицию = 66%, вторая на последнюю позицию = 22%, с третьей на последнюю = 12%.

Фактическое поведение PseudoAppend регулируется в условии оператора While,Вы можете изменить значение для сравнения с генератором чисел random, чтобы повысить вероятность того, что песня будет опережать других, и изменить значение по сравнению с target, чтобы указать, насколько далеко только что законченная песня.может двигаться вперед в списке.

---

Редактировать II (код Python 3 и пример вывода для списка из 11 элементов)

songlist=[0,1,2,3,4,5,6,7,8,9,10]

import random

def pseudoappend(locallist, index):
    song=locallist[index]
    del(locallist[index])
    locallist.append(song)
    target=-1
    while (random.randint(1,3)==1) and (target> -3):
        locallist[target],locallist[target-1] = locallist[target-1],locallist[target]
        target-=1

for x in range(len(songlist)*9):
    print("%3d" % x, ': ', "%2d" % songlist[0], ': ', songlist)
    pseudoappend(songlist, 0)

print( 'end : ', "%2d" % songlist[0], ': ', songlist)

Вот пример вывода, проходящего через список ~9 разПервый столбец - просто текущий индекс, второй столбец показывает текущую выбранную песню, а третий столбец показывает текущий порядок списка:

>>> ================================ RESTART ================================
>>> 
  0 :   0 :  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
  1 :   1 :  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0]
  2 :   2 :  [2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1]
  3 :   3 :  [3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 2]
  4 :   4 :  [4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3]
  5 :   5 :  [5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4]
  6 :   6 :  [6, 7, 8, 9, 10, 0, 1, 2, 3, 4, 5]
  7 :   7 :  [7, 8, 9, 10, 0, 1, 2, 3, 4, 5, 6]
  8 :   8 :  [8, 9, 10, 0, 1, 2, 3, 4, 5, 6, 7]
  9 :   9 :  [9, 10, 0, 1, 2, 3, 4, 5, 6, 7, 8]
 10 :  10 :  [10, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 11 :   0 :  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
 12 :   1 :  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0]
 13 :   2 :  [2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 0]
 14 :   3 :  [3, 4, 5, 6, 7, 8, 9, 10, 1, 0, 2]
 15 :   4 :  [4, 5, 6, 7, 8, 9, 10, 1, 0, 2, 3]
 16 :   5 :  [5, 6, 7, 8, 9, 10, 1, 0, 2, 3, 4]
 17 :   6 :  [6, 7, 8, 9, 10, 1, 0, 2, 3, 4, 5]
 18 :   7 :  [7, 8, 9, 10, 1, 0, 2, 3, 4, 6, 5]
 19 :   8 :  [8, 9, 10, 1, 0, 2, 3, 4, 6, 7, 5]
 20 :   9 :  [9, 10, 1, 0, 2, 3, 4, 6, 7, 5, 8]
 21 :  10 :  [10, 1, 0, 2, 3, 4, 6, 7, 5, 8, 9]
 22 :   1 :  [1, 0, 2, 3, 4, 6, 7, 5, 10, 8, 9]
 23 :   0 :  [0, 2, 3, 4, 6, 7, 5, 10, 8, 9, 1]
 24 :   2 :  [2, 3, 4, 6, 7, 5, 10, 8, 9, 1, 0]
 25 :   3 :  [3, 4, 6, 7, 5, 10, 8, 9, 2, 1, 0]
 26 :   4 :  [4, 6, 7, 5, 10, 8, 9, 2, 1, 0, 3]
 27 :   6 :  [6, 7, 5, 10, 8, 9, 2, 1, 0, 3, 4]
 28 :   7 :  [7, 5, 10, 8, 9, 2, 1, 0, 3, 4, 6]
 29 :   5 :  [5, 10, 8, 9, 2, 1, 0, 3, 4, 6, 7]
 30 :  10 :  [10, 8, 9, 2, 1, 0, 3, 4, 5, 6, 7]
 31 :   8 :  [8, 9, 2, 1, 0, 3, 4, 5, 10, 6, 7]
 32 :   9 :  [9, 2, 1, 0, 3, 4, 5, 10, 6, 7, 8]
 33 :   2 :  [2, 1, 0, 3, 4, 5, 10, 6, 7, 9, 8]
 34 :   1 :  [1, 0, 3, 4, 5, 10, 6, 7, 9, 8, 2]
 35 :   0 :  [0, 3, 4, 5, 10, 6, 7, 9, 8, 2, 1]
 36 :   3 :  [3, 4, 5, 10, 6, 7, 9, 8, 2, 1, 0]
 37 :   4 :  [4, 5, 10, 6, 7, 9, 8, 2, 1, 0, 3]
 38 :   5 :  [5, 10, 6, 7, 9, 8, 2, 1, 0, 3, 4]
 39 :  10 :  [10, 6, 7, 9, 8, 2, 1, 0, 3, 4, 5]
 40 :   6 :  [6, 7, 9, 8, 2, 1, 0, 3, 4, 5, 10]
 41 :   7 :  [7, 9, 8, 2, 1, 0, 3, 4, 5, 10, 6]
 42 :   9 :  [9, 8, 2, 1, 0, 3, 4, 5, 7, 10, 6]
 43 :   8 :  [8, 2, 1, 0, 3, 4, 5, 7, 10, 6, 9]
 44 :   2 :  [2, 1, 0, 3, 4, 5, 7, 10, 6, 9, 8]
 45 :   1 :  [1, 0, 3, 4, 5, 7, 10, 6, 2, 9, 8]
 46 :   0 :  [0, 3, 4, 5, 7, 10, 6, 2, 9, 8, 1]
 47 :   3 :  [3, 4, 5, 7, 10, 6, 2, 9, 8, 1, 0]
 48 :   4 :  [4, 5, 7, 10, 6, 2, 9, 8, 1, 3, 0]
 49 :   5 :  [5, 7, 10, 6, 2, 9, 8, 1, 3, 0, 4]
 50 :   7 :  [7, 10, 6, 2, 9, 8, 1, 3, 5, 0, 4]
 51 :  10 :  [10, 6, 2, 9, 8, 1, 3, 5, 0, 7, 4]
 52 :   6 :  [6, 2, 9, 8, 1, 3, 5, 0, 7, 4, 10]
 53 :   2 :  [2, 9, 8, 1, 3, 5, 0, 7, 6, 4, 10]
 54 :   9 :  [9, 8, 1, 3, 5, 0, 7, 6, 4, 10, 2]
 55 :   8 :  [8, 1, 3, 5, 0, 7, 6, 4, 10, 2, 9]
 56 :   1 :  [1, 3, 5, 0, 7, 6, 4, 10, 2, 9, 8]
 57 :   3 :  [3, 5, 0, 7, 6, 4, 10, 2, 9, 1, 8]
 58 :   5 :  [5, 0, 7, 6, 4, 10, 2, 9, 3, 1, 8]
 59 :   0 :  [0, 7, 6, 4, 10, 2, 9, 3, 1, 8, 5]
 60 :   7 :  [7, 6, 4, 10, 2, 9, 3, 1, 8, 5, 0]
 61 :   6 :  [6, 4, 10, 2, 9, 3, 1, 8, 5, 0, 7]
 62 :   4 :  [4, 10, 2, 9, 3, 1, 8, 5, 0, 7, 6]
 63 :  10 :  [10, 2, 9, 3, 1, 8, 5, 0, 7, 6, 4]
 64 :   2 :  [2, 9, 3, 1, 8, 5, 0, 7, 6, 4, 10]
 65 :   9 :  [9, 3, 1, 8, 5, 0, 7, 6, 4, 10, 2]
 66 :   3 :  [3, 1, 8, 5, 0, 7, 6, 4, 10, 2, 9]
 67 :   1 :  [1, 8, 5, 0, 7, 6, 4, 10, 2, 9, 3]
 68 :   8 :  [8, 5, 0, 7, 6, 4, 10, 2, 9, 3, 1]
 69 :   5 :  [5, 0, 7, 6, 4, 10, 2, 9, 8, 3, 1]
 70 :   0 :  [0, 7, 6, 4, 10, 2, 9, 8, 3, 1, 5]
 71 :   7 :  [7, 6, 4, 10, 2, 9, 8, 3, 0, 1, 5]
 72 :   6 :  [6, 4, 10, 2, 9, 8, 3, 0, 1, 5, 7]
 73 :   4 :  [4, 10, 2, 9, 8, 3, 0, 1, 5, 7, 6]
 74 :  10 :  [10, 2, 9, 8, 3, 0, 1, 5, 7, 6, 4]
 75 :   2 :  [2, 9, 8, 3, 0, 1, 5, 7, 6, 4, 10]
 76 :   9 :  [9, 8, 3, 0, 1, 5, 7, 6, 4, 10, 2]
 77 :   8 :  [8, 3, 0, 1, 5, 7, 6, 4, 10, 2, 9]
 78 :   3 :  [3, 0, 1, 5, 7, 6, 4, 10, 2, 9, 8]
 79 :   0 :  [0, 1, 5, 7, 6, 4, 10, 2, 3, 9, 8]
 80 :   1 :  [1, 5, 7, 6, 4, 10, 2, 3, 9, 8, 0]
 81 :   5 :  [5, 7, 6, 4, 10, 2, 3, 9, 8, 1, 0]
 82 :   7 :  [7, 6, 4, 10, 2, 3, 9, 8, 1, 0, 5]
 83 :   6 :  [6, 4, 10, 2, 3, 9, 8, 1, 0, 7, 5]
 84 :   4 :  [4, 10, 2, 3, 9, 8, 1, 0, 7, 5, 6]
 85 :  10 :  [10, 2, 3, 9, 8, 1, 0, 7, 5, 6, 4]
 86 :   2 :  [2, 3, 9, 8, 1, 0, 7, 5, 6, 4, 10]
 87 :   3 :  [3, 9, 8, 1, 0, 7, 5, 6, 4, 2, 10]
 88 :   9 :  [9, 8, 1, 0, 7, 5, 6, 4, 2, 10, 3]
 89 :   8 :  [8, 1, 0, 7, 5, 6, 4, 2, 10, 3, 9]
 90 :   1 :  [1, 0, 7, 5, 6, 4, 2, 10, 8, 3, 9]
 91 :   0 :  [0, 7, 5, 6, 4, 2, 10, 8, 3, 1, 9]
 92 :   7 :  [7, 5, 6, 4, 2, 10, 8, 3, 1, 9, 0]
 93 :   5 :  [5, 6, 4, 2, 10, 8, 3, 1, 9, 0, 7]
 94 :   6 :  [6, 4, 2, 10, 8, 3, 1, 9, 0, 7, 5]
 95 :   4 :  [4, 2, 10, 8, 3, 1, 9, 0, 7, 6, 5]
 96 :   2 :  [2, 10, 8, 3, 1, 9, 0, 7, 6, 4, 5]
 97 :  10 :  [10, 8, 3, 1, 9, 0, 7, 6, 4, 5, 2]
 98 :   8 :  [8, 3, 1, 9, 0, 7, 6, 4, 5, 2, 10]
end :   3 :  [3, 1, 9, 0, 7, 6, 4, 5, 2, 10, 8]

Answer 4

Моя идея - иметь очередь карт для игры.Очередь перемешивается, а затем воспроизводится по одному, пока не будет очищена.Поскольку каждая карта разыгрывается, если карта была разыграна менее чем м ходов назад, добавьте ее в конец очереди и выберите следующую карту.После освобождения очереди ее можно снова заполнить и перетасовать.Массив может быть использован для отслеживания того, в какой ход в последний раз играли карты.Это в среднем O (1) на песню.

Вот мое решение в F #.

let deal (deck : _[]) m =
    let played = Array.create (deck.Length) (-m)

    let rec subDeal (cards : Queue<_>) i = 
        seq {
            if cards.Count = 0 then
                yield! subDeal (shuffledQueue deck) i
            else
                let card = cards.Dequeue()

                if i - played.[card] > m then
                    played.[card] <- i
                    yield card
                else
                    cards.Enqueue card

                yield! subDeal cards (i + 1)
        }

    subDeal (shuffledQueue deck) 1

Некоторые тестовые данные для сделки 0 .. 7 с m = 4.

[|3; 1; 4; 0; 2; 6; 5; 4; 0; 2; 3; 6; 1; 5; 0; 1; 2; 6; 4; 3; 5; 2; 0; 6; 3; 4;
  5; 1; 6; 0; 3; 2; 5; 4; 1; 3; 5; 2; 0; 6; 1; 4; 2; 5; 3; 4; 0; 1; 6; 5; 2; 4;
  3; 0; 6; 1; 3; 5; 6; 2; 4; 1; 0; 5; 2; 6; 3; 1; 4; 0; 2; 6; 1; 4; 0; 5; 3; 2;
  1; 0; 5; 6; 4; 3; 2; 1; 3; 0; 5; 6; 4; 3; 1; 2; 0; 5; 6; 4; 3; 0; ...|]

// card number and the number of occurrences of said card
[|(3, 286); (6, 286); (5, 285); (0, 286); (1, 285); (4, 286); (2, 286)|]

// longest time before each card is repeated
[|11; 11; 11; 11; 12; 11; 11|]

Полная программа испытаний.

open System
open System.Collections.Generic

let rnd = new Random()

let shuffle cards =
    let swap (a: _[]) x y =
        let tmp = a.[x]
        a.[x] <- a.[y]
        a.[y] <- tmp

    Array.iteri (fun i _ -> swap cards i (rnd.Next(i, Array.length cards))) cards
    cards

let shuffledQueue cards =
    let queue = new Queue<_>()

    cards 
    |> shuffle 
    |> Array.iter (fun x -> queue.Enqueue x)
    queue

let deal (deck : _[]) m =
    let played = Array.create (deck.Length) (-m)

    let rec subDeal (cards : Queue<_>) i = 
        seq {
            if cards.Count = 0 then
                yield! subDeal (shuffledQueue deck) i
            else
                let card = cards.Dequeue()

                if i - played.[card] > m then
                    played.[card] <- i
                    yield card
                else
                    cards.Enqueue card

                yield! subDeal cards (i + 1)
        }

    subDeal (shuffledQueue deck) 1

let size = 7
let deck = Array.init size (fun i -> i)
let cards = deal deck 4

let getMaxWait seq value =
    Seq.fold (fun (last, count) test -> 
        if test = value then 
            (0, count) 
        else 
            (last + 1, max (last+1) count)
    ) (0, 0) seq
    |> snd

let test = cards |> Seq.take 2000

test
|> Seq.take 200
|> Seq.toArray
|> printfn "%A"

test
|> Seq.countBy (fun x -> x)
|> Seq.toArray
|> printfn "%A"

deck
|> Seq.map (fun x -> getMaxWait test x)
|> Seq.toArray
|> printfn "%A"

Console.ReadLine() |> ignore