9.5 พิมพ์ทุกรูปแบบ

โจทย์จำนวนมากในค่ายถามว่า "มีแบบไหนบ้าง" หรือ "แบบไหนดีที่สุด" แล้วขนาดข้อมูลเล็กพอจะลองทุกแบบได้ เช่น ข้อสอบถูกผิด 10 ข้อตอบได้กี่แบบ เพื่อน 5 คนขึ้นพูดหน้าห้องได้กี่ลำดับ ถ้าจำนวนช่องตายตัว ลูปซ้อนกันก็พอ แต่ถ้าจำนวนช่องเป็น n ที่รับเข้ามา จะเขียนลูปซ้อน n ชั้นไม่ได้ recursion ทำเรื่องนี้ได้พอดี หน้านี้เริ่มจากหอคอยฮานอยที่ recursion แก้ได้สวยที่สุด แล้วพิมพ์สตริงฐานสองทุกแบบ และการเรียงสับเปลี่ยนทุกแบบ ซึ่งเป็นโครงของ backtracking ในบทที่ 21

หอคอยฮานอย

มีหลักสามหลัก A B C หลัก A มีแผ่นกลม n แผ่น ใหญ่อยู่ล่าง เล็กอยู่บน ต้องย้ายทั้งหมดไปหลัก C โดย

• ย้ายได้ครั้งละหนึ่งแผ่น หยิบได้เฉพาะแผ่นบนสุดของหลัก
• ห้ามวางแผ่นใหญ่ทับแผ่นเล็ก

ลองคิดด้วยลูปจะงงทันที ว่าแผ่นไหนควรไปหลักไหนตอนไหน แต่ถ้าตอบสามคำถาม จะเห็นคำตอบเลย แผ่นใหญ่สุดคือแผ่นที่ n จะย้ายไป C ได้ก็ต่อเมื่อไม่มีอะไรทับอยู่ และ C ต้องว่าง แปลว่าอีก n - 1 แผ่นต้องไปกองอยู่ที่ B ก่อน

1. ย้าย n - 1 แผ่นบนจาก A ไป B โดยใช้ C เป็นที่พัก ซึ่งเป็นปัญหาเดิมที่เล็กลง
2. ย้ายแผ่นที่ n จาก A ไป C
3. ย้าย n - 1 แผ่นจาก B ไป C โดยใช้ A เป็นที่พัก ปัญหาเดิมที่เล็กลงอีกครั้ง

กรณีฐานคือ n = 0 ไม่มีอะไรต้องย้าย ภาพนี้คือสามขั้นนั้นเมื่อ n = 3

#include <stdio.h>

int moves = 0;

void hanoi(int n, char from, char to, char via)
{
    if (n == 0) {
        return;
    }
    hanoi(n - 1, from, via, to);
    moves++;
    printf("move disk %d from %c to %c\n", n, from, to);
    hanoi(n - 1, via, to, from);
}

int main()
{
    int n;
    scanf("%d", &n);
    hanoi(n, 'A', 'C', 'B');
    printf("total %d moves\n", moves);
    return 0;
}

3

move disk 1 from A to C
move disk 2 from A to B
move disk 1 from C to B
move disk 3 from A to C
move disk 1 from B to A
move disk 2 from B to C
move disk 1 from A to C
total 7 moves

พารามิเตอร์สามตัว from to via คือหลักต้นทาง ปลายทาง และที่พัก แต่ละชั้นสลับบทบาทของหลักตามขั้นที่ 1 กับ 3 สามบรรทัดแรกของผลลัพธ์คือขั้นที่ 1 (ย้ายสองแผ่นบนไป B) บรรทัดที่สี่คือขั้นที่ 2 และสามบรรทัดถัดไปคือขั้นที่ 3 ลองทำตามด้วยเหรียญสามขนาดบนโต๊ะดู จะเห็นว่าไม่มีครั้งไหนผิดกฎ

จำนวนครั้งที่ย้ายของ n แผ่น คือสองเท่าของ n - 1 แผ่นบวกหนึ่ง ได้ 1 3 7 15 ... หรือ 2ⁿ - 1 บนเครื่องที่เขียนเอกสารนี้ ป้อน 10 ได้ total 1023 moves ป้อน 20 ได้ total 1048575 moves ทุกแผ่นที่เพิ่มทำให้งานเพิ่มเท่าตัว แบบเดียวกับต้นไม้ของฟีโบนัชชี แต่คราวนี้ทุกครั้งที่ย้ายต่างกันหมด ไม่มีงานซ้ำให้จด จึงเร็วกว่านี้ไม่ได้ ตำนานที่ว่าพระย้ายแผ่นทอง 64 แผ่น ต้องย้าย 2⁶⁴ - 1 ครั้ง ซึ่งมากกว่าที่ long long เก็บได้เสียอีก

สตริงฐานสองยาว n ทุกแบบ

ข้อสอบถูกผิด 3 ข้อ ตอบได้กี่แบบ และมีแบบไหนบ้าง ให้ 0 แทนผิด 1 แทนถูก คำตอบหนึ่งแบบคือสตริงยาว 3 ที่มีแต่ 0 กับ 1 ช่องแรกเลือกได้ 2 แบบ แต่ละแบบเลือกช่องที่สองได้อีก 2 แบบ รวม 2 × 2 × 2 = 8 แบบ

คิดแบบ recursion โดยเติมทีละช่อง ฟังก์ชัน generate(pos) หมายความว่า "ช่อง 0 ถึง pos - 1 เติมเสร็จแล้ว ให้เติมช่องที่เหลือทุกแบบ"

• กรณีฐาน pos เท่ากับ n แปลว่าเติมครบทุกช่องแล้ว ได้หนึ่งแบบ พิมพ์ออกมา
• กรณีเรียกซ้ำ ใส่ '0' ที่ช่อง pos แล้วเติมช่องที่เหลือทุกแบบ จากนั้นเปลี่ยนเป็น '1' แล้วเติมช่องที่เหลือทุกแบบอีกรอบ

#include <stdio.h>

int n;
char bits[21]; // (1)!

void generate(int pos)
{
    if (pos == n) {
        bits[n] = '\0';
        printf("%s\n", bits);
        return;
    }
    bits[pos] = '0';
    generate(pos + 1);
    bits[pos] = '1'; // (2)!
    generate(pos + 1);
}

int main()
{
    scanf("%d", &n);
    generate(0);
    return 0;
}

1. สตริงที่กำลังเติมเป็น global ทุกชั้นเขียนลงอาเรย์ตัวเดียวกัน แต่ละชั้นดูแลแค่ช่อง pos ของตัวเอง ยาวได้ถึง 20 ตัวกับ '\0' อีกหนึ่งช่องตามบทที่ 6
2. เขียนทับ '0' ที่ใส่ไว้ได้เลย เพราะตอนมาถึงบรรทัดนี้ ทุกแบบที่ขึ้นต้นด้วย '0' ที่ช่องนี้ถูกพิมพ์ไปครบแล้ว

3

000
001
010
011
100
101
110
111

ภาพนี้คือการเรียกทั้งหมดเมื่อ n = 3 แต่ละชั้นแตกเป็นสองทาง ทางซ้ายใส่ 0 ทางขวาใส่ 1 กล่องแถวล่างสุดคือกรณีฐานที่พิมพ์ออกมา ไล่จากซ้ายไปขวาจึงได้ลำดับเดียวกับผลลัพธ์

n ช่องได้ 2ⁿ แบบ n = 20 คือ 1048576 บรรทัด บนเครื่องที่เขียนเอกสารนี้ให้โปรแกรมเขียนผลลงไฟล์แบบที่ grader ทำ ใช้ราว 0.15 วินาที ยังไหว แต่ n = 30 คือพันล้านกว่าแบบ มากกว่าพันเท่า ไม่ทันแน่ ก่อนเลือกวิธีลองทุกแบบ ต้องนับก่อนเสมอว่ามีกี่แบบ

การเรียงสับเปลี่ยนทุกแบบ

เพื่อน 3 คนหมายเลข 1 2 3 ต้องขึ้นนำเสนองานหน้าห้องทีละคน มีลำดับได้กี่แบบ แต่ละลำดับคือ การเรียงสับเปลี่ยน (permutation) ของ 1 ถึง n ต่างจากสตริงฐานสองตรงที่ เลขที่ใช้ไปแล้วห้ามใช้ซ้ำ จึงต้องมีอาเรย์ used จำไว้ว่าใครขึ้นไปแล้ว

#include <stdio.h>

int n;
int order[12];
int used[12];

void permute(int pos)
{
    if (pos == n) {
        for (int i = 0; i < n; i++) {
            if (i > 0) {
                printf(" ");
            }
            printf("%d", order[i]);
        }
        printf("\n");
        return;
    }
    for (int v = 1; v <= n; v++) {
        if (used[v] == 0) {
            used[v] = 1; // (1)!
            order[pos] = v;
            permute(pos + 1); // (2)!
            used[v] = 0; // (3)!
        }
    }
}

int main()
{
    scanf("%d", &n);
    permute(0);
    return 0;
}

1. เลือก ให้คนที่ v ขึ้นเป็นลำดับที่ pos และจดว่าใช้ไปแล้ว
2. ลอง เติมลำดับที่เหลือทุกแบบ โดยไม่มีใครเลือก v ได้อีก
3. คืนสภาพ ปลดคนที่ v ออก เพื่อให้รอบถัดไปของลูปลองคนอื่นในลำดับที่ pos และให้ชั้นข้างบนใช้ v ในลำดับอื่นได้

3

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

ลูปลอง v จากน้อยไปมาก ผลลัพธ์จึงออกมาเรียงตามพจนานุกรมเอง ลำดับแรกเลือกได้ n คน ลำดับถัดไปเหลือ n - 1 คน รวมเป็น n! แบบ ตามที่เห็นในหน้า 9.2 ว่าแฟกทอเรียลโตเร็วแค่ไหน 8! = 40320 แบบยังสบาย 10! = 3628800 แบบยังพอไหว แต่ 12! เกือบห้าร้อยล้านแบบ พิมพ์ไม่ทันแล้ว โจทย์ที่ให้ลองทุกลำดับจึงมักให้ n ไม่เกินราว 10

โครง เลือก ลอง คืนสภาพ นี้คือหัวใจของ backtracking ในบทที่ 21 ที่นั่นจะเพิ่มอีกหนึ่งอย่าง คือถ้าเลือกไปครึ่งทางแล้วรู้ว่าไม่มีทางได้คำตอบ ก็ไม่ต้องลองต่อ ตัดกิ่งนั้นทิ้งเลย ทำให้ลองทุกแบบได้กับข้อมูลที่ใหญ่กว่านี้มาก ส่วนหอคอยฮานอยที่แบ่งเป็นปัญหาย่อยแล้วประกอบกลับ คือ divide and conquer ในบทที่ 22

ลองทำให้พัง

แบบที่ 1 ลืมคืนสภาพ

ลบบรรทัด used[v] = 0; ออกจากโปรแกรมเรียงสับเปลี่ยน คอมไพล์ผ่านโดยไม่มีคำเตือน ป้อน 3 ได้

1 2 3

ออกมาแบบเดียวแล้วจบ ป้อน 4 ก็ได้แค่ 1 2 3 4 หลังพิมพ์แบบแรก ทุกคนถูกจดว่าใช้แล้วค้างไว้ พอย้อนกลับไปลองคนอื่นในลำดับที่ 2 ก็ไม่เหลือใครให้เลือก ทุกชั้นวนลูปผ่านไปเฉยๆ ถ้าโปรแกรมลองทุกแบบแล้วได้คำตอบน้อยกว่าที่นับไว้ ให้สงสัยการคืนสภาพก่อนอย่างอื่น

สรุป

• หอคอยฮานอย ย้าย n - 1 แผ่นไปที่พัก ย้ายแผ่นใหญ่สุด แล้วย้าย n - 1 แผ่นกลับมาทับ รวม 2ⁿ - 1 ครั้ง
• พิมพ์ทุกรูปแบบด้วยการเติมทีละช่อง generate(pos) กรณีฐานคือเติมครบ n ช่องแล้วพิมพ์
• สตริงฐานสองยาว n มี 2ⁿ แบบ การเรียงสับเปลี่ยนของ n ตัวมี n! แบบ นับก่อนเสมอว่าทันไหม
• ห้ามใช้ซ้ำ ใช้อาเรย์ used ตามโครงเลือก ลอง คืนสภาพ ลืมคืนสภาพจะได้คำตอบไม่ครบ
• โครงนี้คือพื้นฐานของ backtracking ในบทที่ 21 และ divide and conquer ในบทที่ 22

กลับไปเช็กรายการ ผ่านบทนี้เมื่อ แล้วไปทำแบบฝึกหัด