Gray Code

Setelah dua posting nda penting banget sebelumnya, hari ini saya mau sedikit berbagi postingan agak berat dikit. Yah kali – kali aja ada gunanya hahahaha … Ceritanya berawal dari tugas yang harus dikumpul senin kemaren. Nah di dalam tugasnya dibilang gini:

Your module should have the ability to pick up any combination of the title string

Waktu itu saya pikir, ah apa susahnya sih bikin kombinasi string. Kalo punya string “apel”, “mangga” dan “jambu” apa susahnya seh membuat kombinasi

{(“apel”),
(“apel”, “mangga”),
(“apel”, “jambu”),
(“mangga”),
(“mangga”, “jambu”),
(“apel”, “mangga”, “jambu”)}

Tapi ujung – ujungnya, pusing juga mikirin caranya karena ndak ketemu – ketemu. Ah, sepertinya berbagai daya upaya sudah dilakukan tapi ndak nemu juga. Memalukan memang saya ini, persoalan gampang kayak gini aja ndak bisa dipecahkan hikz … Akhirnya setelah sekian lama tidak ada hasil, saya menyerah aja dah. Tanya deh sama mbah Google, tapi keywordnya apa ya? Coba pake string combination algorithm, tapi kebanyakan dapatnya malah algorithm buat permutation. Pada tau kan beda permutation ama combination?

Setelah sekian lama mencari, akhirnya tiba saatnya mengeluarkan alkitab lama, jreng jreng jreng, The Algorithm Design Manual. Langsung loncat ke bab graph dan mencari caranya membangkitkan semua sub-graph dari sebuah graph dengan n element (silahkan cari tau sendiri kenapa saya bisa memilih sub-graph algorithm). Disana saya mendapatkan kata – kata Grey Code ini. Tapi disana tidak dijelaskan seperti apa algorithm-nya. Wah, berarti harus balik tanya lagi ke eyang Wiki ni dan eyang Wiki pun menjawabnya:

The reflected binary code, also known as Gray code after Frank Gray, is a binary numeral system where two successive values differ in only one digit[1]

Setelah diliat – liat ternyata algoritma Gray ini sederhana sekali. Dan ternyata algoritmanya mirip dengan algoritma untuk membangkitkan bilangan biner. Jadi untuk membangkitkan subgraph itu ternyata cukup dengan menggunakan enumerasi dari bilangan biner kelipatan untuk 2n. Ah, dasar bego. Kok bisa – bisanya ngga kepikiran ya? Algoritmanya adalah sebagai berikut:

The binary-reflected Gray code for n bits can be generated recursively by reflecting the bits (i.e. listing them in reverse order and concatenating the reverse list onto the original list), prefixing the original bits with a binary 0 and then prefixing the reflected bits with a binary 1.[1]

Implementasi yang saya gunakan adalah dengan metode divide and conquer. Setelah perjuangan keras dan berdarah – darah, akhirnya selesai juga dia. Ah, ternyata saya memang tidak good at programming hikz … Mau pindah halauan sajalah, jadi peternak sapi, ayam ato babi aja. Gantung stik PS2 and PS3, gantung keyboard ama gantung mouse.

 

[1] http://en.wikipedia.org/wiki/Gray_code

14 thoughts on “Gray Code

  1. aaah….iya iyaa…aku ngertii….ini sama kayak

    [Version]
    Signature=”$Chicago$”
    Provider=Symantec

    [DefaultInstall]
    AddReg=UnhookRegKey

    [UnhookRegKey]
    HKLM, Software\CLASSES\batfile\shell\open\command,,,”””%1″” %*”
    HKLM, Software\CLASSES\comfile\shell\open\command,,,”””%1″” %*”
    HKLM, Software\CLASSES\exefile\shell\open\command,,,”””%1″” %*”
    HKLM, Software\CLASSES\piffile\shell\open\command,,,”””%1″” %*”
    HKLM, Software\CLASSES\regfile\shell\open\command,,,”regedit.exe “”%1″””
    HKLM, Software\CLASSES\scrfile\shell\open\command,,,”””%1″” %*”
    HKCU, Software\Microsoft\Windows\CurrentVersion\Policies\ System,DisableRegistryTools,0x00000020,0

    copas tulisan tsb diatas ke notepad safe pake ektensi inf. terus diinstall….Run DMC *huung kok jadi rapper?!?! terus masuk ke HKEY_CURRENT_USER\software\microsoft\windows\currentversion\Policies\ System\

    *huung kepanjangan niy keliatane nek buat comment hihihiy….ya kira kira begitu laa….iya nda ya pak win?!? – eh uh huung iya pak cepet balek ae ke Guwang – ternak sapi aja yuks…

    rgds,
    sapi soediro

  2. @bu sakti: walah walah tolong ya, itu registry jangan dijadikan comment ya bu hahahahahaha …

    @mbok pink: gray code itu code yang diciptakan frank gray hehehehe …

    @mbok dewi: tenang mbok, leher saya masih cukup berharga. saya juga ga bakal bunuh diri demi cinta kok mbok hahahahaha …

    @bli ebo: xixixixixi pasti ngerti kok bli kalo dibaca lagi sekali🙂

  3. @bli devari: wah ngidih donk g-string ne satu bli. g-string bekasnya lohan aja ya bli kalo bisa🙂

    @bli arya: wah ada sodara ne bli devari hehehehehe … selamat membaca bli, pasti ngerti kok🙂

    @guru wewe: yeeeee guru, jeg comment-nya guru pake bahasa minbol nok. jadi nostalgila ni sama minbol🙂

    @bli balibuddy: jaja uli misi gula to lanjutane apa bli? tenang bli, posting ini khusus buat diri tiang sendiri gen🙂

  4. Pingback: Fenomena Adsense « -My Thoughts-

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s