Иногда бывает нужно решить такую задачу: есть массив, из которого мы по очереди выбираем рандомные элементы. И нужно сделать так, чтобы однажды выбранные элементы больше нам не попадались. Очевидное решение в лоб – завести рядом Set, в котором хранить либо сами выбранные элементы, либо их идентификаторы – совсем не годится: мало того, что придётся использовать дополнительную память, так ещё и нет гарантии, что следующий элемент получится найти сразу же. Чем больше мы будем выбирать элементов, тем дольше мы будем вынуждены искать следующий рандомный элемент, который еще отсутствует во множестве использованных. Другой способ – перекладывать использованные элементы в другую коллекцию – работоспособен только если исходная коллекция допускает операцию remove, и она реализована в ней эффективно. Поэтому для массивов не подходит (remove просто нет), да и для ArrayList’ов тоже не годится (remove неэффективен). Вот с LinkedList будет работать вполне себе неплохо. Смущает только невозможность восстановить исходное состояние коллекции после завершения работы алгоритма. Тогда уж проще скопировать исходную коллекцию целиком, и удалять из неё элементы. Но это не очень, если коллекция большая, а элементов нам нужно всего с десяток.

В общем, воспользуемся солдатской смекалкой и сделаем следующий алгоритм: каждый очередной выбираемый элемент мы меняем с последним элементом массива, и уменьшаем длину используемой части массива на единицу. В конце массива таким образом скапливаются “использованные” элементы. А чтобы сохранить возможность вернуться к исходному состоянию, рядом в ArrayList будем записывать оригинальные индексы использованных элементов.

Собственно, я написал класс, реализующий эту идею, и, находя его полезным, привожу код.

Пример использования:

Integer[] array = new Integer[100];
try (Picker<Integer> picker = new Picker<>(array)) {
    Integer randomItem = picker.pickRandom();
}

Код класса:

(more…)