Как выбрать менее чем N объектов случайным образом из K объектов? - PullRequest
Новая
       9

Как выбрать менее чем N объектов случайным образом из K объектов?

0 голосов
/ 15 сентября 2018

из 4 предметов, 1,2,3,4.Хотел бы случайно выбрать 2 объекта, но также можно не выбирать ни одного, или просто выбрать 1 объект.(Рассматривая только комбинацию. Нет порядка.)

Таким образом, возможными состояниями являются следующие 11 состояний: 

[(empty)],[1],[2],[3],[4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]

Как сгенерировать одно из состояний выше при возможности один раз в 11раз?

Нужно написать обобщенную версию этого.Выберите случайным образом менее N объектов из K объектов.

1 Ответ

0 голосов
/ 15 сентября 2018

Сначала нужно определить, сколько объектов вы хотите выбрать.В вашем примере у вас есть 11 возможных подмножеств, 1 с размером 0, 4 с размером 1 и 6 с размером 2. Поэтому вы должны выбрать размер 0, 1 или 2 в соответствии со взвешенным распределением 1: 4: 6.Один из способов визуализировать это - представить 11 одинаковых по размеру слотов: 1 с 0, 4 с 1 и 6 с 2. Теперь поместите шар случайным образом в один из слотов и отметьте метку.Каждый слот имеет одинаковую вероятность получения мяча, но вероятность получения слота с меткой 0, 1 или 2 пропорциональна 1: 4: 6.

В общем, количество комбинаций k объекты из набора размером n задаются как n!/(k!*(n-k)!).Мы можем использовать эту формулу для определения нашего взвешенного распределения.Обратите внимание, что я следую обычному соглашению об использовании k для представления количества выбранных объектов из n возможностей - вы используете их в противоположном смысле, что немного сбивает с толку.

Как только вы определили количество пиков p, вы случайным образом выбираете p элементы из входных данных, используя что-то вроде вариации Дюрстенфельда Фишера-Йейтса shuffle.

Вот пример кода Java для иллюстрации: 

static <E> List<E> randomPick(List<E> in, int k)
{   
    int n = in.size();

    // determine number of elements to pick using a random selection
    // weighted by the number of subsets of each size, 0..k
    Random r = new Random();
    NavigableMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
    int total = 0;
    for(int i=0; i<=k; i++)
    {
        total += fact(n)/(fact(i)*fact(n-i));
        map.put(total, i);
    }       
    int p = map.higherEntry(r.nextInt(total)).getValue();

    // Use Durstenfeld shuffle to pick p random elements from list
    List<E> out = new ArrayList<>(in);
    for(int i=n-1; i>=n-p; i--)
    {
        Collections.swap(out, i , r.nextInt(i + 1));
    }       
    return out.subList(n-p, n);
}

static int fact(int n)
{
    int f = 1;
    while(n > 0) f *= n--;
    return f;
}

Тест: 

public static void main(String[] args)
{
    List<Integer> in = Arrays.asList(1, 2, 3, 4);       
    for(int i=0; i<10; i++)
        System.out.println(randomPick(in, 2));
}

Вывод: 

[]
[2, 1]
[4]
[3, 2]
[1]
[1, 4]
[2, 1]
[2, 3]
[4]
[1, 4]
...