[pieczywowewiadrze]

#programowanie

Ma ktoś pomysł jak ułożyć algorytm posortowania liczb od 0 do 2^20-1 w kolejności tak aby każda kolejna liczba różniła się od poprzedniej zmianą tylko i wyłącznie 1 bitu. Idzie to zrobić w krócej niż 100 lat?

[d.....c]

@pieczywowewiadrze: Emacsem przez sendmail.

[tommach]

@pieczywowewiadrze: Jeżeli możesz skorzystać z dodatkowej pamięci, zobacz sobie sekwencyjne generowanie kodów greya https://en.wikipedia.org/wiki/Gray_code#Constructing_an_n-bit_Gray_code i wygeneruj kody dla przedziału. Potem posortuj sortowaniem kubełkowym te liczby które masz. Wtedy przechodzisz sobie po sekwencji kodów greya, patrzysz czy masz taką liczbę w kubełku i jeśli masz wypisujesz. To jest tylko 10^6, więc nawet jakby generowanie kodów greya miało jakąś większą złożoność, to nie powinno być problemu.

Edit: możesz też użyć jakiejś hashmapy, zamiast

[Hauleth]

@pieczywowewiadrze: ale wiesz, że wszystkie liczby z przedziału tam będą? Przy czym wiesz, że taka tablica to 4 GiB?

[fizyk20]

@Hauleth: 2^20 to tylko trochę ponad milion. Liczby tej wielkości zmieszczą się w 4 bajtach, więc potrzeba tylko 2^22 bajtów = 4 MiB.

@pieczywowewiadrze: Nie powinno być trudno wygenerować taki ciąg rekurencyjnie.

Jeśli potrafisz wygenerować odpowiednią kolejność dla n-bitowych liczb, to dla n+1-bitowych robisz tak:
1. Wypisujesz ciąg n-bitowych z dopisanym 0 z przodu.
2. Wypisujesz ciąg n-bitowych od tyłu z dopisanym 1 z przodu.

W każdym ciągu z punktów

[Hauleth]

@fizyk20: Ok, musiało mi się omsknąć przy liczeniu.

[pieczywowewiadrze]

@fizyk20: dziena, bede musiał coś podobnego wykombinować

[pieczywowewiadrze]

@fizyk20: DZIAŁA!!!!!!!!!!!!!

[pieczywowewiadrze]

kod