Случайное возвращение элемента из массива

[impersonalis]

Целиком задача звучит так:

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

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

[impersonalis]

Кстати ещё одна фича влияния ключа (несортированного массива, задающего перестановки (кодирующего признаки)) на результат.

;графический хлам
Graphics 800,600,32,2
SetBuffer BackBuffer()
SetFont LoadFont("Arial",22)

;пример входа
Const N%=10;размер массива
Global p%[N];массив
Global r%[N];дополнительный массив
Local ec%
Local key$
For iv=1 To 3
Init()
Select iv
Case 1
key="1111111111"
Case 2
key="1111100000"
Case 3
key="0001111000"
End Select
GenKey(key)
ec=Output()
If ec=27 Exit
sort()
Color 255,0,0
Print "-----"
Color 255,255,255
ec=Output()
If ec=27 Exit
Cls
Locate 0,0
Next
End
;============================
Function Init()
For i=1 To N
p[i]=i;заполним чисилками
Next
End Function
Function GenKey(bit_key$)
;хиытрй шаффл
SeedRnd MilliSecs();рандомайз (u=2637)
If Len(bit_key)<N
RuntimeError "er len"
EndIf
For i=1 To N
r[i]=Rand(1,1000)*Int(Mid(bit_key,i,1));собственно шум
Next
End Function
Function sort()
;теперь подействуемна массив некоей функицей,
;например, отсортируем по убыванию, например,
;"вставками"
Local k%,z%
Local IterCnt%=0;число повторений (некая характеристкиа сложности)
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
IterCnt=IterCnt+1
Wend
r[j+1]=k; и тут
p[j+1]=z; =)
Next
End Function
Function Output()
;==
;вывод массива
For i=1 To N
Print Chr(p[i]+64)+" "+Str(r[i]);для красоты будем выводить
;1 как 'A', 2 - как 'B' и т.д.
Next
Return WaitKey();дождёмся тыка от пользователя
;==
End Function

Код приведён для демонстрации алгоритма, т.к. реализация не оптимальна.

ключ 945.627.329.749.753.579.117.51.73.589
результат A.E.D.B.J.F.C.G.I.H
комментарий весь массив перемешан

ключ 529.160.618.44.688.0.0.0.0.0
результат E.C.A.B.D.F.G.H.I.J
комментарий перемешаны первые 5 элементов (правые элементы в ключе были априори на месте)

ключ 0.0.0.901.370.798.72.0.0.0
результат D.F.E.G.A.B.C.H.I.J
комментарий 4 средних элемента перемешаны и сдвинуты в начало

ключ 9.9.9.4.7.3.8.0.0.0 (генерируется другим методом)
результат A.B.C.G.E.D.F.H.I.J
комментарий 4 средних элемента перемешаны

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

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

[EvilOkta]

*некромант mode on*
я бы предложил упрощенный алгоритм, с большим хаосом и хардкором:
- Задать массив значений размерностью в два раза большей, чем кол-во элементов n.
- Распределить элементы по массиву таким образом - 0..n - элементы массива, n+1..2n+1 - элементы типа null)
- Задать диапазон разброса значений для функции рандома равной кол-ву элементов
- Применять к каждому элементу диапазона массива 0..n функцию рандома, в качестве увеличения индекса элемента и перехода его в диапазон n+1..2n+1. При этом если элемент уже имеет отличное от null значение, то инициировать функцию рандома заново.
- Завершить функцию, когда в массиве не останется элементов типа null. В диапазоне n+1..2n+1 будет перемешанный массив, в 0..n - оригинальный.
Перед новой генерацией присвоить диапазону n+1..2n+1 null и можно запускать с начала.
Как то так. Хотя подход Импера для реализации открывает много полезных штук =)

*некромант mode off*

[Nikich]

На ум приходит слишком простой метод, поэтому он явно неверен, однако интересно, в чем ошибка.

Const N%=10;размер массива
Local p%[N],c%[N]
For i=1 To N
	p[i]=i;заполним чисилками
Next
;Перемешивание
For i=1 To N
a%=rnd(N)
       if c[a]<>1
            c[a]=1
            p[i]=a
       endif
Next
c[a]=0

Подзабыл синтаксис Blitz, однако логика, думаю, понятна.
Или вся фишка в том, что алгоритм устроен без if?

[radiobutton]

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