Jak wypisać wszystkie możliwości k z n?na przykład wypisać 32-bitowe
liczby, które by miały 6 bitów zapalonych?

do góry

W dniu 2015-07-24 o 17:32, Borneq pisze:
> Jak wypisać wszystkie możliwości k z n?na przykład wypisać 32-bitowe
> liczby, które by miały 6 bitów zapalonych?

Podobno kod Graya w tym pomaga, ale nie widzę w jaki sposób

do góry

W dniu 2015-07-24 o 17:48, Borneq pisze:
> W dniu 2015-07-24 o 17:32, Borneq pisze:
>> Jak wypisać wszystkie możliwości k z n?na przykład wypisać 32-bitowe
>> liczby, które by miały 6 bitów zapalonych?
>
> Podobno kod Graya w tym pomaga, ale nie widzę w jaki sposób
Jest algorytm: http://webhome.csc.uvic.ca/~haron/CoolCombo.pdf

do góry

On 24.07.2015 17:32, Borneq wrote:
> Jak wypisać wszystkie możliwości k z n?na przykład wypisać 32-bitowe
> liczby, które by miały 6 bitów zapalonych?


Nakarm googla
Enumerating k-combinations
(enumerate) numbers with k bits set
matlab nchoosek.m ;-)

http://stackoverflow.com/questions/127704/algorithm-
to-return-all-combinations-of-k-elements-from-n

Tu masz kilka różnych algorytmów, włącznie z kodami greya.


Podoba mi się ten bitowy:
http://stackoverflow.com/questions/1851134/generate-
all-binary-strings-of-length-n-with-k-bits-set
http://www.graphics.stanford.edu/~seander/bithacks.h
tml#NextBitPermutation

Po małym odkurzeniu:

int main() {
int k=4;
const int n=7;
uint64_t v= (1<<k) - 1;

while ( v < (1<<n) ) {
cout<<bitset<n>(v)<<endl;
uint64_t t = (v | (v - 1)) + 1;
v = t | ((((t & -t) / (v & -v)) >> 1) - 1);
}
}

bitset<n> jest tylko do ładnego wyświetlania.

Ograniczone jest niestety do 64 obiektów.
boost::multiprecision::int128_t i podobne marudzą na
jednoargumentowy minus, można je nakłonić do współpracy tak:
v = t | ((((t & 0-t) / (v & 0-v)) >> 1) - 1);

pzdr
bartekltg


0001111
0010111
0011011
0011101
0011110
0100111
0101011
0101101
0101110
0110011
0110101
0110110
0111001
0111010
0111100
1000111
1001011
1001101
1001110
1010011
1010101
1010110
1011001
1011010
1011100
1100011
1100101
1100110
1101001
1101010
1101100
1110001
1110010
1110100
1111000

do góry

W dniu 2015-07-24 o 19:48, bartekltg pisze:
> Podoba mi się ten bitowy:
> http://stackoverflow.com/questions/1851134/generate-
all-binary-strings-of-length-n-with-k-bits-set
>
> http://www.graphics.stanford.edu/~seander/bithacks.h
tml#NextBitPermutation
>
> Po małym odkurzeniu:
>
> int main() {
> int k=4;
> const int n=7;
> uint64_t v= (1<<k) - 1;
>
> while ( v < (1<<n) ) {
> cout<<bitset<n>(v)<<endl;
> uint64_t t = (v | (v - 1)) + 1;
> v = t | ((((t & -t) / (v & -v)) >> 1) - 1);
> }
> }
Przyjrzę się, 64 obiekty to dużo, nie będę potrzebował nawet 32.

na razie przeglądam http://webhome.csc.uvic.ca/~haron/CoolCombo.pdf
począwszy od rekurencyjnego, wszystkie dla argumentów (3, 2) dają wyniki:
11000
01100
10100
01010
00110
10010
01001
00101
00011
10001

Teraz chcę uruchomić ten ostatni bitowy, są tam symvole matematyczne jak
and, xor, ale nie rozumiem strona 11 linia kodu 9: jest tam znak jakby
"Saturna" a za nią jednynka. Co to może być za operacja?

do góry

W dniu 2015-07-24 o 20:51, Borneq pisze:
> Teraz chcę uruchomić ten ostatni bitowy, są tam symvole matematyczne jak
> and, xor, ale nie rozumiem strona 11 linia kodu 9: jest tam znak jakby
> "Saturna" a za nią jednynka. Co to może być za operacja?

Jest:
The operator o is a specialized form of subtraction, called saturating
subtraction,where the result of i o j is i - j if i >= j,
and is 0 if i < j.

do góry

On 24.07.2015 20:51, Borneq wrote:
> W dniu 2015-07-24 o 19:48, bartekltg pisze:
>> Podoba mi się ten bitowy:
>> http://stackoverflow.com/questions/1851134/generate-
all-binary-strings-of-length-n-with-k-bits-set
>>
>>
>> http://www.graphics.stanford.edu/~seander/bithacks.h
tml#NextBitPermutation
>>
>>
>> Po małym odkurzeniu:
>>
>> int main() {
>> int k=4;
>> const int n=7;
>> uint64_t v= (1<<k) - 1;
>>
>> while ( v < (1<<n) ) {
>> cout<<bitset<n>(v)<<endl;
>> uint64_t t = (v | (v - 1)) + 1;
>> v = t | ((((t & -t) / (v & -v)) >> 1) - 1);
>> }
>> }
> Przyjrzę się, 64 obiekty to dużo, nie będę potrzebował nawet 32.
>
> na razie przeglądam http://webhome.csc.uvic.ca/~haron/CoolCombo.pdf
> począwszy od rekurencyjnego, wszystkie dla argumentów (3, 2) dają wyniki:
> 11000
> 01100
> 10100
> 01010
> 00110
> 10010
> 01001
> 00101
> 00011
> 10001
>
> Teraz chcę uruchomić ten ostatni bitowy, są tam symvole matematyczne jak
> and, xor, ale nie rozumiem strona 11 linia kodu 9: jest tam znak jakby
> "Saturna" a za nią jednynka. Co to może być za operacja?

Czy Twoim celem jest dokładne zapoznanie się z algorytmem, czy użycie
go? :>

pzdr
bartekltg

do góry

W dniu 2015-07-24 o 22:04, bartekltg pisze:
> Czy Twoim celem jest dokładne zapoznanie się z algorytmem, czy użycie
> go? :>

Ten opisany jest bardziej zrozumiały, choć może nie tak szybki jak ten w
C, ale piszę w C#. Ale tak się nie wgłębiałem, tyle że uruchomiłem te
algorytmy. Chodzi o użycie jako części większego algorytmu.

do góry