1s

Question

sabit yoğunluğuna sahip Pseudo Rastgele Sayı üreteci Sabit bir Hamming ağırlığı [1s sabit yoğunluğu] olan rasgele rasgele bit dizileri ya da sözde rasgele sayılar üretmek için bir yol arıyorum [olasılıkla düşük "rastgele"). ihtiyacım Hamming ağırlığa sahip bir tohum ile basit bir lineer benzeşimsel jeneratörü kullanılarak ilgili bazı öneri bulundu, ancak hiçbir mantık

herkes olabilir [Hamming ağırlıklı doğrusal benzeşimsel dönüşüm altında değişmeyen neden] Bu doğru neden verildi Neden bu bana başka bir yol gösteriyor?

Teşekkür ...

Answer 1

düzenlemek: piton kolay şeyler

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 

---

İşte temelde olası bir yolu (var karışık bir taban dize rastgele permütasyon oluşturmak için yapar:

1. rastgele bir factoradic numarası N oluşturmak için Bit-derinliği.

[perm_list x in x < ağırlıkça]

:

factoradic (sözde piton gösterilen) bit dizisi için permütasyon listesini dönüştürmek göstergesi-listesini

permütasyonuna dönüştürmek

Answer 2

Sabit bir hamming ağırlığı oluşturmak için bir LCG kullanmakla ilgili duymadım (okulda bu kodları çok fazla çiğnemedim, bu yüzden çok da şaşırmadım). Her durumda, sabit bir hamming ağırlığına sahip bir grup bit üretmek oldukça basittir. İşte, belirli bir ağırlığa sahip bir n -bit sayısını döndürecek bir python kodu. Bu, diğer dillere de kolayca tercüme edilmeli (python tam sayılarının keyfi olarak geniş olması gerçeğinden başka). bir psödo rasgele sayı üreteci (PRNG) düşük bir ağırlık tohumu ile bile basit bir kullanma

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 3

kesinlikle iyi bir çözüm değildir. PRNG, tohumun Hamming ağırlığını sabit tutmaz ve bir PRNG'nin tüm fikri, tohumun bilgilerini kaldırmaktır.

Tam olarak bitlerden n'in 1'ine ayarlanmak isterseniz, sorunuz thesetwo sorularının bir çeşididir. Eğer k n'den daha küçükse, karıştırma solüsyonu O (n) 'dir. Aşağıdaki çözümün O (k) olduğunu düşünüyorum. Eğer yaklaşık k bit olması istiyorsanız

Bu piton

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)) 

yılında, this answer dayanmaktadır k ile, birine setleri/n her bit olasılığını olma Mecbur sonra biri olmak Bernouilli ve Geometrik dağılımlara bakın.