Вопрос по algorithm, java – Случайно выбрать k бит из n из Java BitSet

3

Как правильно выбратьk биты отJava BitSet длиныm сn биты включены, гдеk≤n≤m?

Пример ввода:m=20, n=11

Пример вывода:k=3

Наивный подход

Выберите случайное число0≤ i ≤ m-1. если он включен на входе и не включен на выходе, включите его на выходе, покаk биты включены на выходе.

Этот подход не работает, когдаn намного меньше, чемm. Есть другие идеи?

Ваш Ответ

4   ответа
5

отбор проб из резервуара к битам, которые установлены.

Алгоритм имеетO(m) сложность времени и требуетO(k) объем памяти

1

n позиции всех установленных битов и размещение их в коллекции в качестве первого шага, и их выборk позиции из этой коллекции случайно?

1

ПостроитьList удерживая все установленные битовые индексы. ДелатьCollections#shuffle в теме. Выберите первыйk индексы из перемешанного списка.

РЕДАКТИРОВАТ Согласно комментариям этот алгоритм может быть неэффективным, еслиk действительно маленький, аn большой. Вот альтернатива: генерироватьk случайные, разные числа в интервале[0, n]. Если при генерации числа число уже присутствует в наборе выбранных индексов, используйте подход с цепочкой: увеличивайте число на 1, пока не получите число, которого еще нет в наборе. Наконец, сгенерированные индексы - это те, которые вы выбираете среди установленных битов.

Для маленьких неэффективноk и большойn значения Adam Matan
@ AdamMatan Я не совсем уверен. Альтернатива со случайным испытанием может привести к бесконечному циклу с малым n. Сложность моего подходаO(m) как в памяти, так и во времени. Вы не можете сократить время, если хотите, чтобы алгоритм был действительно случайным. Вы можете уменьшить память для малыхk вероятно. Я постараюсь редактировать с этим улучшением. Boris Strandjev
Спасибо, Борис. Улучшение памяти было бы здорово. Adam Matan
Борис, Второй подход не случаен, потому что он предпочитает разреженные биты по плотным кластерам. Рассмотреть возможность000000001000000011111. Крайний левый бит имеет больше шансов быть выбранным, чем кластеризованный в правом куске. Adam Matan
@ AdamMatan Нет, я рассматриваю только установленные биты, таким образом, я генерируюk случайные числа доn, неm. Boris Strandjev
1

Еслиn намного больше, чемk, вы можете просто сократить алгоритм перемешивания Фишера-Йейтса, чтобы остановить его, выбрав столько, сколько вам нужно:

private static Random rand = new Random();
public static BitSet chooseBits(BitSet b, int k) {
    int n = b.cardinality();
    int[] indices = new int[n];
    // collect indices:
    for (int i = 0, j = 0; i < n; i++) {
        j=b.nextSetBit(j);
        indices[i] =j++;
    }
    // create returning set:
    BitSet ret = new BitSet(b.size());
    // choose k bits:
    for (int i = 0; i<k; i++) {
        //The first n-i elements are still available.
        //We choose one:
        int pick = rand.nextInt(n-i);
        //We add it to our returning set:
        ret.set(indices[pick]);
        //Then we replace it with the current (n-i)th element
        //so that, when i is incremented, the 
        //first n-i elements are still available:
        indices[pick] = indices[n-i-1];
    }
    return ret;
}
Сложность памяти O O (N), верно? Это неэффективно для очень больших значенийn гдеk очень маленький. Adam Matan
@ AdamMatan Да, отбор проб из резервуара кажется таким способом, пока ваш prng очень быстрый, так как вы бы назвали егоm-k раз. Если это не так, вы можете просто выбратьk значения в[0..n), пропуская дубликаты k/n ок. 0, так что это эффективно), в отсортированный набор. Тогда единственное, что вам нужно сделать наm scale будет подсчитывать установленные биты и записывать, когда ваш счет находится в вашем наборе случайных значений. Получениеn может быть проблематично, так как для этого потребуется дополнительный проход. maybeWeCouldStealAVan

Похожие вопросы