Алгоритм обхода массива

Question

Алгоритм обхода массива

Георгий Кищенко Ученик (143), на голосовании 1 месяц назад

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

Answer 1

нынеЗАБАНЕННЫЙ (Приговорён к 10 годам) Гуру (3962) 2 месяца назад

сделать второй массив, в который кидать использованные, или каждый раз двигать использованный в самый конец массива, а потом сужать диапазон рандома до -2, до -3 итд

Георгий КищенкоУченик (143) 2 месяца назад

каждый раз рандом будет выбирать число и каждый раз проверять его на наличие в вспомогательном массиве? а когда будет выбрано 999999 чисел сколько времени понадобится чтобы тыкая пальцем в небо найти неиспользованный? неужели нет какого то нормального подхода?

нынеЗАБАНЕННЫЙ (Приговорён к 10 годам) Гуру (3962) Георгий Кищенко, ты конч? я 2 варика дал

Answer 2

Ну не удаляй.
Просто меняй местами, сокращая количество элементов, из которых делается выборка.
Например, у тебя есть 1 2 3 4
На первом шаге выбираешь из 4-х, скажем, выпало 2.
Меняешь его с последним элементом:
1 4 3 2
А теперь выбираешь из трех.
Пусть выпало 1.
Массив будет
3 4 1 2
Выбираешь из двух...

Answer 3

Перемешай (алгоритм Фишера-Йетса) и затем просто последовательно выбирай.