@BabuinSlayer

В общем, из массива рандомно выбирается элемент, как сделать так, чтобы выбирались только те, которые не были выбраны раньше? Можно это сделать без дополнительного массива и чтобы памяти поменьше занимало? Уже должно было много раз обсуждаться, но видимо я не умею искать.

0

@Cyborg Drone

Всё зависит от того, нужно ли Вам помнить первоначальное расположение элементов массива. Если нет - то не нужен дополнительный массив, достаточно "перемешать" массив, после чего читать из него элементы по порядку. Если да - то чудес не бывает, и нужно как-то запоминать, какие элементы были выбраны (либо, напротив, остались). И придётся использовать дополнительный массив (скорее всего - типа boolean), либо, если массив небольшой, использовать множество для хранения индексов выбранных (или оставшихся) элементов массива. В случае применения дополнительного массива типа boolean можно указать в начале программы директиву компилятораи объявить массив как упакованныйВ этом случае под тип boolean будет отводиться по одному биту памяти (а не по одному байту), и размер массива сократится в восемь раз, однако, доступ к элементам массива будет несколько медленнее.

1

@BabuinSlayer

Примерно так и думал, спасибо

Добавлено через 7 минут
Кстати, тогда ещё вопрос. Если массив довольно большой и нужно помнить изначальные индексы, то будет много времени занимать. Если при рандомном тыке каждый раз сверяться с дополнительным массивом, то при 100 на 100 шанс выбора последнего не выбранного элемента 1 к 10000, а это чёт долго будет. Можно как-нибудь оптимизировать?

0

@Joy

если попадает в выбранный, выбираете ближайший к нему справа или слева.

0

@BabuinSlayer

Не сильно поможет наверное, та же ситуация будет, когда мало не выбранных останется. Но хотя да, можно что-то типа бинарного поиска сделать и проверять сначала всё слева, а потом справа если не найдётся.

0

@volvo

Имеешь массив A[1 .. n], для него создаешь дополнительный массив индексов ix[1 .. n], перемешиваешь его любым нормальным алгоритмом, и потом просто идешь по нему по порядку либо с начала в конец, либо с конца в начало. Элемент a[ix[ i ]] будет "случайно" (насколько хорошо перемешаешь массив индексов - настолько более "случайно") выбран из массива A, но при этом, поскольку i все время только увеличивается/уменьшается, соответственно, ix[ i ] не повторяется - то и повторов из A не будет (если, конечно, в нем не было изначально одинаковых значений). Зато никаких затрат на получение следующего "случайного" элемента из A - просто inc(i)/dec(i), никаких проверок не надо.

Без доп. памяти это нереализуемо.

1

@BabuinSlayer

Нужно будет попробовать, спасибо

0