Генератор псевдослучайных чисел с фиксированной плотностью 1 с

Question

Я ищу способ генерации псевдослучайных чисел [возможно, с низкой «случайностью»] или псевдослучайные битовые последовательности с фиксированным весом Хэмминга [фиксированная плотность 1 с]. Я нашел предложение об использовании простого линейного конгруэнтного генератора с затравкой, имеющей нужный мне вес Хэмминга, но не было приведено никаких соображений, почему это правильно [почему вес Хэмминга инвариантен относительно линейного конгруэнтного преобразования]

Может ли кто-нибудь обосновать это или дать мне другой способ?

Спасибо ...

Answer 1

Я не слышал об использовании LCG для генерации фиксированного веса Хэмминга (я не слишком разбирался в кодах Хэмминга в школе, поэтому я тоже не слишком удивлен :).

В любом случае, довольно просто сгенерировать кучу бит с фиксированным весом Хэмминга. Вот немного кода на Python, который будет возвращать n -битное число с определенным весом. Это должно легко переводиться и на другие языки (кроме того факта, что целые числа Python произвольно большие).

from random import randrange

def get_ham_and_bits(weight, nbits=32):
    "Get n-bits with a fixed hamming weight"
    if weight > nbits: 
        return 1 < nbits

    result = 0
    for i in xrange(weight):
        bit = 1 << randrange(nbits)

        # only flip bits that aren't already flipped. delete the loop to
        # make this return a random weight instead of a fixed weight
        while bit & result != 0: 
            bit = 1 << randrange(nbits)

        # An XOR might be a better idea here, especially if you remove the loop.
        result |= bit
    return result

Answer 2

Использование генератора псевдослучайных чисел (PRNG), даже простого генератора с малым весом, определенно НЕ является хорошим решением. PRNG не поддерживают постоянный вес Хемминга семян, и вся идея PRNG заключается в удалении информации о семени.

Если вы хотите, чтобы биты были точно установлены в 1 из n, ваш вопрос является вариантом этих двух вопросов. Если k намного меньше, чем n, решение для перемешивания равно O (n). Я думаю, что следующее решение O (k).

Он основан на этом ответе , на питоне

from random import sample

def konesoutofn(k, n):
    output=0
    for d in sample(xrange(n), k):output+=(1<<d)
    return output

x=konesoutofn(4,32)
print(bin(x))

Если вы хотите иметь приблизительно k битов, установленных в единицу, при k / n, равной вероятности того, что каждый бит равен единице, вам следует взглянуть на распределения Бернулли и Геометрические.

Answer 3

edit : python упрощает перемешивание вещей

from random import shuffle

def gen(ham, bits=32):
    # generate a list with the correct number of 1's
    x = [1]*ham+[0]*(bits-ham)
    shuffle(x)
    # convert back to a number
    return int(''.join(map(str,x)),2)

>> print('\n'.join(bin(gen(5,15)) for x in range(10)))
0b101100100001000
0b100110010010
0b100110110000000
0b10010101100
0b11101100000
0b100100001000110
0b10000010101001
0b110000011100000
0b100011100010
0b100000011100010

---

Вот один из возможных способов (в основном, генерировать случайные перестановки базовой строки:

1. генерирует случайное факторическое число N вплоть до вашей битовой глубины.
2. преобразование факторадика в индекс-список перестановок

3. преобразовать ваш список перестановок в битовый массив (проиллюстрирован на псевдо-питоне):

   [x <вес для x в perm_list] </strike>