Выбор из множества

[impersonalis]

Задача:
Есть набор элементов (дискретное, конечное множество).
Как реализовать функцию выбора (с возвращением) произвольного элемента таким образом, чтобы два идущих подряд выбора никогда не давали одинаковый результат.
Пример:
Множество {1,2,3,4,5}.
Допустимая генерация: 1,5,3,2,3,1,2,1,2,1,2
Недопустимая генерация 1,3,4,2,5,5
Демо для экспериментов:

Const Size%=3
Dim Vector(Size)
For i=1 To Size
	Vector(i)=i
Next

Global LI=0

While True
	Local k%=WaitKey()
	If Chr(k)="1" Then Exit
	;=
	ТуДу: инсёрт йо код хир
	;=
	Print Vector(LI)
Wend
End

Решение, которым многие не брезгуют:

Local newLI%=LI
	While newLI=LI
		newLI=Rand(1,Size)
	Wend
	LI=newLI

А именно:
1. сгенерить новый индекс
2. если новый совпадает со старым, гото 1
3. готово
Решение имеет уйму минусов:
1. непредсказуемое время исполнения при одинаковых входных данных
2. потенциально бесконечное время выполнения

Мой вариант решения:

Const Size%=3
Dim Vector(Size)
For i=1 To Size
	Vector(i)=i
Next

Global LI=0

While True
	Local k%=WaitKey()
	If Chr(k)="1" Then Exit
	;=
	If LI=0
		LI=Rand(1,Size)
	Else
		LI=((LI+Rand(1,Size-1)-1) Mod Size)+1
	EndIf
	;=
	Print Vector(LI)
Wend
End

При первом запросе (LI=0) мы можем выбрать любой элемент (Rand(1,Size)). При последующих обращениях у нас N-1 элементов для выбора. Логика следующая.
1) Закольцовываем индексацию элементов при помощи взятия остатка от деления:
было: 1 2 3 4 5
стало: 1 2 3 4 5 1 2 3 4 5
Mod Size
2) Чтобы исключить выбранный ранее элемент, новый будем находить как стоящий от уже выбранного на X элементов.
LI+Rand
3) Пусть X не отрицательный: мы уже реализовали цикличность и, потому, отрицательное отклонение реализуется большим положительным (Если долго двигаться по направлению от нулевого меридиана, то попадёте в него).
4) Нулевой X не подходит, т.к. результат будет соотвествовать уже выбранному элементу.
LI+Rand(1,
5) Сдвиг на длину всего набора не подходит, т.к.
а) за счёт кольца эквивалентен сдвигу на ноль (см. п. 4)
б) логично, что для выбора всегда (кроме первого раза) доступно N-1 элементов.
LI+Rand(1,Size-1)
6) Если мы будем подавать на MOD числа от 1 до N, то с выхода будем снимать числа от 0 до N-1, что нарушит логику индексации, сдвинув диапазон:
-> 1 2 3 4 5 6 7 8 9 10
<- 1 2 3 4 0 1 2 3 4 0
LI+Rand(1,Size-1)-1
7) Однако, мы имеем индексацию с единицы, а формула - с 0:
-> 1 2 3 4 5 6 7 8 9 10
= 0 1 2 3 4 5 6 7 8 9
<- 0 1 2 3 4 0 1 2 3 4
Необходимо повторно скорректировать результат:
((LI+Rand(1,Size-1)-1) Mod Size)+1
8) Итоговая формула:
LI=((LI+Rand(1,Size-1)-1) Mod Size)+1

ЗЫЖ
Можно переписать блок, используя формулу и для случая первого обращения:
LI=((LI+Rand(1,Size-COND)-1) Mod Size)+1
COND должен быть равен нулю при первом обращении, и единице - при последующих. Кроме того потребуется всё равно сгенерить значение якобы прошлого состояния индекса. Такой подход даст больше мозголомства и тормозов (на выполнении), чем позволит выиграть в количестве строк кода.

[dsd]

1.создаем массив из (n-1) элементов, где n-кол-во элементов в множестве.
2.размещаем в массиве элементры множества.
3.генерируем случайное целое число от 0 по (n-2) включительно.
4.выдаем на вывод элемент лежащий в ячейке массива с выпавшим индексом.
5.запоминаем выданный элемент
6.пишем в эту ячейку элемент множества не влезший в массив, а запомненный на место не влезшего
п.3-п6 в цикл
Профит?
Можно в принципе просто выпавший элемент менять местом с последним в множестве, а последний просто не выбирать

[impersonalis]

Занятно.
У моего зато вектор const

[dsd]

Можно еще запоминать индекс выпавшего элемента.
если индекс предыдущего и выпавшего равны то если индекс выпавший не равен последнему элементу индекс выпавшего ++ иначе индекс выпавшего --.
Сорри за троллинг

[Aikon]

impersonalis, если смущает бесконечное время выполнение, то можно допилить так

	Local newLI% = LI
	newLI = Rand(1,Size)
	If newLI = LI Then
		newLI = (LI + 3) % Size
	LI=newLI

Т.е при попадании на повторный элемент будет выбран элемент, который отстоит от этого на заданное число элементов.
P.S. dsd это и написал Перечитал и твой пост подробнее - нафига вместо 3 использовать rand не сильно понятно, поскольку величина все равно псевдо-случайная получается.

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

[impersonalis]

Дорогой, Aikon, очень приятно, что ты осилил мой пост и даже предложил своё решние

Const Size%=3
Dim Vector(Size)
For i=1 To Size
Vector(i)=i
Next

Global LI=0

While True
Local k%=WaitKey()
If Chr(k)="1" Then Exit
;=
If LI=0
LI=Rand(1,Size)
Else
Local newLI% = LI
newLI = Rand(1,Size)
If newLI = LI Then
newLI = (LI + 3) Mod Size
LI=newLI
EndIf
EndIf
;=
Print Vector(LI)
Wend
End

которое, к сожалению, выдаёт следующий ряд 22222222222222222222222222222222222222222222222222 222222222
Угадай: почему? Уж не из-за отсутствия "нафиг" ненужного рнд? Хотя прибавка размера (+3) тоже сильно "помогает".

Что касается предложения dsd (последнего, на которое ты сослался), то, такой механизм:
1) работает (опять-таки) разное время
2) потащит за собой дополнительные проверки на выход за границы массива
3) увеличивает вероятность выпадания одного из элементов на P`=1/(N-1), повышая тем самым автокорреляцию распределения.
4) при этом выгоды (перевешивающей п.1-3) я не вижу чего-то