Как сделать выборку без замены, используя только количество элементов каждого класса?
У меня есть список строк (["A", "B", ...]) и список размеров ([4,7,...]). Я хотел бы сделать выборку без замены из набора строк, где изначально строка в позиции i появляется sizes[i] раз. Я должен выполнить эту операцию k раз. Понятно, что если я выберу строку i, то sizes[i] уменьшится на 1. Текущее наивное решение, которое я разработал, состоит в том, чтобы сгенерировать весь входной набор, перемешать его и итеративно извлечь первый элемент массива. Это явно неэффективно, поскольку, если строка появляется 1 миллион раз, мне пришлось бы сгенерировать 1 миллион записей.
public static void main(String[] args) {
String[] elems = { "A", "B", "C", "D", "E" };
Integer[] sizes = { 10, 5, 4, 7, 3 };
int k = 3;
ArrayList<String> bag = new ArrayList<>();
for (int i = 0; i < elems.length; i++) {
for (int j = 0; j < sizes[i]; j++) {
bag.add(elems[i]);
}
}
Collections.shuffle(bag);
for (int i = 0; i < k; i++) {
System.out.println(bag.remove(0));
}
}
Есть ли лучший и более эффективный способ выполнить эту операцию? Спасибо.
Ты прав. Я мог просто получить доступ к первым k элементам. В конце концов, результат все равно тот же, я думаю
Ответы 4
Предполагая, что сумка не должна быть постоянной или вообще использоваться, вы можете создать класс, который содержит ввод и частоту, например. вот так (упрощенно):
class SampleElement<T> {
private T value;
private int frequency;
//constructors, getters, setters
}
Затем создайте коллекцию этих элементов из ввода, который у вас есть, например. (опять же упрощенно):
List<SampleElement<String>> samples = Arrays.asList(new SampleElement<String>("A",10), ...);
Наконец, выполните цикл, пока эта коллекция не станет пустой или вы не сделаете это k раз, и выберите случайный элемент. Уменьшите частоту этого элемента, и если она достигнет 0, вы удалите его из коллекции. Пример (сверху у меня в голове, поэтому может содержать ошибки):
Random rand = new Random();
int runs = k;
while(runs > 0 && !samples.isEmpty() ) {
runs--;
int index = rand.nextInt(samples.size());
SampleElement<String> element = samples.get(index);
System.out.println(element.getValue());
element.decrementFrequency();
if ( element.getFrequency() <= 0 ) {
samples.remove(index);
}
}
Я не совсем уверен, что ваш ответ решает мою проблему. Давайте рассмотрим крайний случай, когда «A» имеет размер 9, а «B» имеет размер 1. Я хочу выполнить k = 1 выборок. Вероятность выбора A будет 9/10, а вероятность выбора B равна 1/10. В вашем решении я думаю, что вместо этого вероятность составляет 1/2 и 1/2.
@molfo верно, хотя это требование не вошло в ваш вопрос (или я его пропустил). Что вы могли бы сделать, так это суммировать все частоты и сгенерировать случайное число в этом диапазоне, например. rand.nextInt(10) для вашего примера. Наконец, вместо использования индекса вы перебираете элементы и суммируете их частоту, пока не дойдете до конца или сумма не станет больше или равна этому случайному числу + 1, и выберите этот элемент (так что, если вы получите 9, вы бы выбрали B, поскольку B имеет A (9) + B (1) = 10 (случайное (9) + 1)). Конечно, вам нужно будет корректировать верхнюю границу на каждой итерации.
Вы можете собрать эти два массива в карту:
String[] elems = {"A", "B", "C", "D", "E"};
Integer[] sizes = {10, 5, 4, 7, 3};
Map<String, Integer> map = IntStream.range(0, elems.length).boxed()
.collect(Collectors.toMap(i -> elems[i], i -> sizes[i]));
System.out.println(map); // {A=10, B=5, C=4, D=7, E=3}
Предполагая, что длины этих двух массивов одинаковы, вы можете создать список записей карты, содержащих пары элементов из этих массивов, и перетасовать этот список:
String[] elems = {"A", "B", "C", "D", "E"};
Integer[] sizes = {10, 5, 4, 7, 3};
List<Map.Entry<String, Integer>> bag = IntStream
.range(0, elems.length)
.mapToObj(i -> Map.of(elems[i], sizes[i]))
.flatMap(map -> map.entrySet().stream())
.collect(Collectors.toList());
System.out.println(bag); // [A=10, B=5, C=4, D=7, E=3]
Collections.shuffle(bag);
System.out.println(bag); // [D=7, C=4, E=3, A=10, B=5]
See also: How to sort an array with respect to another array if there are duplicates?
Если все, что вам нужно, это получить случайный элемент из bag, вам не нужно перемешивать bag. Вы можете использовать Random#nextInt(elems.length * размеры.длина), чтобы получить случайный int от 0 до elems.length * sizes.length - 1, и используя этот int в качестве индекса, вы можете получить элемент из bag.
Демо:
import java.util.ArrayList;
import java.util.Random;
public class Main {
public static void main(String[] args) {
String[] elems = { "A", "B", "C", "D", "E" };
Integer[] sizes = { 10, 5, 4, 7, 3 };
int k = 3;
ArrayList<String> bag = new ArrayList<>();
for (int i = 0; i < elems.length; i++) {
for (int j = 0; j < sizes[i]; j++) {
bag.add(elems[i]);
}
}
Random random = new Random();
int count = elems.length * sizes.length;
for (int i = 0; i < k; i++) {
System.out.println(bag.get(random.nextInt(count)));
}
}
}
Зачем тогда удаляешь? Поскольку это ArrayList, вы можете получить доступ к первым
kэлементам по их индексу (bag.get(i)). Каковы ожидания, когда понадобятся следующиеkэлементы? Следует ли восстановить оригинальную сумку?