forum.boolean.name - Выбор из множества

forum.boolean.name (http://forum.boolean.name/index.php)

- Алгоритмика (http://forum.boolean.name/forumdisplay.php?f=21)

- - Выбор из множества (http://forum.boolean.name/showthread.php?t=15658)

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

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

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

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

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

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

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

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

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

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

Код:

        Local newLI% = LI

        newLI = Rand(1,Size)

        If newLI = LI Then

                newLI = (LI + 3) % Size

        LI=newLI

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

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

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

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

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

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