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

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

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

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

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

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

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

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

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

Мне кажется, что это такая простая, общая и общая проблема, у нее должен быть один из этих двухствольных алгоритмов, таких как Fisher-Yates или Boyer-Moore. Но мой google-fu явно не силен, так как мне еще предстоит найти набор терминов, которые обнаруживают неизбежную бумагу 1973 ACM, которая, вероятно, объясняет, как это сделать в O (1) раз, и почему мой алгоритм глубоко испорчен в некотором роде.

Ответы

Ответ 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

EDIT: добавлен метод playlist_of_length, чтобы уточнить, как вы вызываете next_item для создания списка воспроизведения

Ответ 2

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

В Mathematica:

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

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

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

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

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

Ответ 3

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

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

Изменить (подробнее о "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, чтобы отрегулировать, насколько далеко закончилась только что законченная песня может двигаться вперед в списке.

Edit 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]

Ответ 4

Моя идея - иметь очередь карточек, которые нужно сыграть. Очередь перетасовывается, а затем воспроизводится по одному, пока не опустеет. Когда играется каждая карта, если карта была сыграна менее чем m оборотов назад, добавьте ее в конец очереди и выберите следующую карту. Как только очередь опустела, ее можно снова заполнить и перетасовать. Массив можно использовать для отслеживания того, в какую игру в последний раз играл карта. Это выполняется в среднем по 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

Ответ 5

Это может быть то, что вы ищете.

Бесконечные перепутанные последовательности

Сайт ушел, но вот архив, так как эта ссылка была упомянута в другом месте. Archive.org