Задача:
Есть набор элементов (дискретное, конечное множество).
Как реализовать функцию выбора (с возвращением) произвольного элемента таким образом, чтобы два идущих подряд выбора никогда не давали одинаковый результат.
Пример:
Множество {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 должен быть равен нулю при первом обращении, и единице - при последующих. Кроме того потребуется всё равно сгенерить значение якобы прошлого состояния индекса. Такой подход даст больше мозголомства и тормозов (на выполнении), чем позволит выиграть в количестве строк кода.