Целиком задача звучит так:
Необходимо случайным образом выбирать элементы из некоторого множества (считаем, что элементы множества имеют некий уникальный параметр, который и является определяющим, например, индекс в массиве); вторично выбрать элемент можно не ранее, чем будут выбраны не менее чем по одному (но, не более чем по два) раза все остальные элементы множества.
|
Практическое применение:
Пользователю в случайном порядке демонстрируются изображения из некоего списка. Элементы воспроизводятся в произвольном порядке. Как только, все изображения представлены, начинается новый виток генерации.
Если каждое изображение представить буквенным кодом, то набор из
ABCDE может быть показан так:
AECDB… далее следует новая генерация
..
BCDE.. вот тут мы можем, например, вызвать
A, т.к. он повторно вызывается лишь после того как использованы уже все буквы не менее чем по одному разу, но не более чем по два. По той же причине букву
B использовать уже нельзя.
Суть ясна, я думаю.
Подобную задачу легко решить, имея богатый ООП-функционал. Примитивная работа с контейнером: изменить случайным образом порядок следования элементов в списке, пройтись по нему и повторить произвольную перестановку. Или – удалять произвольно выбранные элементы списка, пока он не будет исчерпан, после чего составить список заново и повторить алгоритм.
Но, не все языки имеют эти приятные свистелки.
Вот простой способ (несложно до него додуматься), вариацию которого я почерпнул в статье, по генерации лабиринтов по алгоритму Краскала.
Алгоритм позволяет псевдослучайным образом изменить порядок элементов внутри массива. Т.е. трудоёмкий фрагмент кода - подготовка искажённой последовательности.
Смысл:
Необходимо подействовать на имеющийся массив некоей хеш-функцией, которая однозначно задаст биекцию «i-ый элемент переходит в j-ый». Хотя имеющийся массив, вероятнее всего уже и так числовой, использовать эти значения как вход нашей фукции нельзя: статистические показатели распределения, получающегося при той или иной (фиксированной) интерпретации массива как последовательности отсчётов, недолжны оказывать какое-либо влияние на результат воздействия хеш-функцией. Иными словами, корреляция входа и выхода должна стремиться к нулю. Собственно, корреляция, между выходами (результатами действия хеш-функции на наш массив), должна быть тоже минимальной.
Указанные соображения, приводят к следующему: в качестве входа, должен использоваться некий дополнительный параметр. С учётом оговорки о скудности функционала (невозможности эргономично агрегировать новый признак в массив), и, соображений модульности кода, создадим дополнительный массив, виртуально связав его с нашим, посредством индексов: признак для i-ого элемента нашего исходного массива содержится в i-ом элементе дополнительного массива.
Теперь возникает вопрос о значениях признака и хеш-функции. Сразу очевидно: чтобы реализовать на практике нашу виртуальную связь, достаточно чтобы все изменения дополнительно массива приводили к точно таким же изменениям нашего исходного.
Теперь мы имеем
ABCDE исходный массив
22345 массив признаков
Наша функция должна анализировать признаки, как некую входную последовательность и преобразовывать её в иную, например:
54322
EDCBA
Причём, вторичная обработка исходных признаков (
22345) должна (как вариант) возвращать отличную от получившейся ранее (
54322) последовательность. Для реализации последнего необходимо либо заложить стохастичность в функцию, либо перманентно генерировать новые признаки. Первое можно, например, реализовать, задав в качестве функции (я так понимаю, хешем, в этом случае, она уже не является), случайное изменение порядка следования элементов. Подобный подход (можно показать) при неудачном стечении обстоятельств требует огромных производительных затрат (напомню об отсутствии связанных списков и прочих радостей); кроме того, подобное непотребство можно было реализовать без всяких признаков и связей.
Второе, например, реализуется так: признаки раздаются случайно, затем производится их сортировка.
Вот рабочий
код, где функция сортирует признаки по возрастанию методом вставок.
;графический хлам
Graphics 800,600,32,2
SetBuffer BackBuffer()
SetFont LoadFont("Arial",20)
;пример входа
Const N%=10;размер массива
Local p%[N];массив
For i=1 To N
p[i]=i;заполним чисилками
Next
;==
;вывод массива
For i=1 To N
Print Chr(p[i]+64);для красоты будем выводить
;1 как 'A', 2 - как 'B' и т.д.
Next
WaitKey();дождёмся тыка от пользователя
Print "===="
;==
;хиытрй шаффл
SeedRnd MilliSecs();рандомайз (u=2637)
Local r%[N];дополнительный массив,
For i=1 To N;его надо забить шумом
r[i]=Rand(1,1000);собственно шум
Next
;теперь подействуемна массив некоей функицей,
;например, отсортируем по возрастанию, например,
;"вставками"
Local k%,z%
For i=1 To N
k=r[i];при этом, с исходным массивом, мы
z=p[i];должны делать такие же преобразования,
j=i-1
While j>0 And r[j]>k
r[j+1]=r[j];что и с ориганльным -
p[j+1]=p[j];такая вот, связь =)
j=j-1
Wend
r[j+1]=k; и тут
p[j+1]=z; =)
Next
;==
;выведем массив!
For i=1 To N
Print Chr(p[i]+64)
Next
WaitKey()
;==
Листинг использует blitz-диалект басика, что должно было облегчить пользователям чтение, а облегчило - мне написание заметки.
Вероятно, я буду спорадически что-то вспоминать и приписывать – потому обратите внимание, на возможные посты ниже в треде.
Опять-таки – стиль изложения и общие познания автора – оставляют желать лучшего, так что учтите это перед тем как, радостно потирая ладони, строчить гневный отзыв.