Permutation การเรียงสับเปลี่ยน

วันนี้จะมาเล่าโจทย์ข้อนึงใน code signal ให้ฟังครับ
ผมใช้เวลาแก้นานมากประมาณ 1 สัปดาห์ จนสุดท้ายยอมกดดูเฉลย

ก็คือ ให้ []string มาแล้ว ตรวจว่า array นี้มันสามารถทำ chain ต่อกันได้ไหม

ปัญหาที่เจอ

ตอนแรกผมตีโจทย์ผิด เข้าใจว่า chain คำกันแบบไม่สนตำแหน่ง ดังนั้นนนนน หลงทางไปหลายวันเลย

อย่างที่สอง คือ ผมพยายามหาทางทำ recursive function หรือการคิดแบบ group char, map char มาใช้
ซึ่งโจทย์เก่าๆข้อก่อนๆที่เคยทำมันดัน work ไง ก็เลยคิดว่าอันนี้น่าจะมี easter egg แบบนั้น

ผมหมดเวลาไปกับการคิดแนวคิดใหม่ๆ คิดวิธีแปลกๆเยอะมากๆ จนลืมเป้าหมายจริงๆว่ามันแค่ต้องแก้โจทย์ให้ออก

ความจริงคือ โจทย์ข้อนี้ ให้ข้อมูลละเอียดและ test ละเอียดอยู่แล้ว ซึ่ง keyword ที่จะหา คือคำว่า Permutation

การทำ Permutation

ผมยอมกดดูเฉลย ก็พบว่า บ้าเอ๊ยยยย มันก็เอาถึกเข้าแลก คือทำสร้าง array สับเปลี่ยนมารับทั้งหมดก่อน จากนั้นค่อยวนลูปตรวจสอบทีละตัว แบบง่ายๆเลย แบบตามตัวอย่างเลยยยย

แล้วไอที่ผมคิดตั้งหลายวัน แทบไม่มีประโยชน์เลย

โอเค ผมก็เลยมา research factorial, และพบว่า Permutation เป็นส่วนนึงของ factorial

เมื่อผมได้แนวคิดจึงเรียกเขียน function permutaion และก็พบว่า เห้ยยยย แม่งยากชิบหายยยยย ทำเรียงสับเปลี่ยนเข้าใจง่ายๆ พอมาเขียนเป็น code ทำไมมันยากขนาดนี้!!!!

ผมพยายามทำ function permutaion อยู่ประมาณ 2 วัน(วันละ 3 ชั่วโมง)ก็ยอมละ มันเสียเวลาเกินไป

เลยเปิดหา code permutaion ก็พบว่า เห้ยยยย มันทำงานแบบ heap แล้ววว heap มันต่างยังไงกับ binary search tree วะครับเนี่ยยยย (ไว้จะเขียนบทความขยายความให้นะ)

ผมก็เอาวะ คิดเองไม่ไหวแล้ว copy code จาก yourbasic.org ไปแปะเลยละกัน

// Perm calls f with each permutation of a.
func Perm(a []rune, f func([]rune)) {
    perm(a, f, 0)
}

// Permute the values at index i to len(a)-1.
func perm(a []rune, f func([]rune), i int) {
    if i > len(a) {
        f(a)
        return
    }
    perm(a, f, i+1)
    for j := i + 1; j < len(a); j++ {
        a[i], a[j] = a[j], a[i]
        perm(a, f, i+1)
        a[i], a[j] = a[j], a[i]
    }
}

// Example usage
Perm([]rune("abc"), func(a []rune) {
     fmt.Println(string(a))
 })

ผมพยายาม debug code เพื่อมาอธิบาย แต่บอกได้เลยว่า อธิบายยากมากๆๆๆๆๆ
ถ้าให้อธิบายคร่าวๆ คือ มันทำ recursive แบบ deep ก่อน ก็คือจะ print เมื่อตัวสุดท้าย เมื่อ i เกิน len(a)
จากนั้น loop จะ return ย้อนกลับเป็น i-1

ลำดับของผลลัพธ์จะได้เป็น abc, acb, bac, bca, cba, cab // บ้าบอออออ

ขั้นต่อไป

หลังจากผ่าน Permutation ที่เหลือก็ไม่มีอะไรยากละครับ
ก็คือปรับ []rune เป็น []string และสร้าง make [][]string, len(n!) จากนั้นก็ logic ปกติ
คือ ตรวจสอบ array[i], array[i+1] แล้วต้อง diff กันไม่เกิน 2

ถ้าอันไหนผ่านก็ return true จบโปรแกรมไปเลย

สรุป (แบบไม่เกี่ยวกันเลยยยย)

สรุปคือ python มี lib สำหรับทำ Permutations and Combinations อยู่แล้วววว
ส่วนผมอิโก้สูง ดันทุรังใช้ Golang ก็ต้องอดทนกันไป (ฮาาาาาาาาาาาา)

code signal golang permutation