ปัญหา Nut และ Bolt (Nuts and Bolts Problem)

บทนำ

กำหนดรายการ Nut (นัท) ที่แตกต่างกัน และรายการ Bolt (บอท) อีกชุดหนึ่ง ภารกิจคือหาคู่ที่ตรงกันของ Nut และ Bolt จากรายการที่กำหนด และจับคู่ Nut นั้นกับ Bolt เมื่อตรงกัน

ปัญหานี้แก้ด้วยเทคนิค Quick Sort โดยนำอิลิเมนต์สุดท้ายของ Bolt เป็น Pivot เรียงใหม่รายการ Nut และได้ตำแหน่งสุดท้ายของ Nut ที่ Bolt ของมันคือ Pivot หลังจาก Partition Nut List แล้ว สามารถ Partition Bolt List โดยใช้ Nut ที่เลือก งานเดียวกันทำซ้ำสำหรับ Sub-list ซ้ายและขวา เพื่อได้การจับคู่ทั้งหมด

อินพุตและเอาต์พุต

Input: รายการล็อกและกุญแจ (Nuts และ Bolts)
nuts = { ),@,*,^,(,%, !,$,&,#}
bolts = { !, (, #, %, ), ^, &, *, $, @ }
Output: หลังจับคู่ Nuts และ Bolts:
Nuts:  ! # $ % & ( ) * @ ^
Bolts: ! # $ % & ( ) * @ ^

อัลกอริทึม

partition(array, low, high, pivot)

Input: อาเรย์หนึ่ง, index low และ high, อิลิเมนต์ pivot

Output: ตำแหน่งสุดท้ายของ pivot element

Begin
    i := low
    for j ในช่วง low ถึง high, do
        if array[j] < pivot, then
            swap array[i] และ array[j]
            เพิ่ม i ขึ้น 1
        else if array[j] = pivot, then
            swap array[j] และ array[high]
            ลด j ลง 1
    done
    swap array[i] และ array[high]
    return i
End

nutAndBoltMatch(nuts, bolts, low, high)

Input: รายการ nuts, รายการ bolts, index ต่ำและสูงของอาเรย์

Output: แสดงว่านัทไหนสำหรับบอทไหน

Begin
    pivotLoc := partition(nuts, low, high, bolts[high])
    partition(bolts, low, high, nuts[pivotLoc])
    nutAndBoltMatch(nuts, bolts, low, pivotLoc-1)
    nutAndBoltMatch(nuts, bolts, pivotLoc + 1, high)
End

ตัวอย่างโค้ด (C++)

#include <iostream>
using namespace std;

void show(char array[], int n) {
    for (int i = 0; i < n; i++)
        cout << array[i] << " ";
}

int partition(char array[], int low, int high, char pivot) {
    // หาตำแหน่งของ pivot สำหรับ quick sort
    int i = low;
    for (int j = low; j < high; j++) {
        if (array[j] < pivot) {
            // เมื่อ jth element น้อยกว่า pivot swap ith และ jth
            swap(array[i], array[j]);
            i++;
        } else if (array[j] == pivot) {
            // เมื่อ jth element เท่ากับ pivot swap jth และ last element
            swap(array[j], array[high]);
            j--;
        }
    }
    swap(array[i], array[high]);
    return i;  // ตำแหน่งของ pivot element
}

void nutAndBoltMatch(char nuts[], char bolts[], int low, int high) {
    if (low < high) {
        int pivotLoc = partition(nuts, low, high, bolts[high]);  // เลือกไอเทมจาก bolt มา partition nut
        partition(bolts, low, high, nuts[pivotLoc]);  // วางตำแหน่ง pivot ก่อนหน้าใน bolt ด้วย
        nutAndBoltMatch(nuts, bolts, low, pivotLoc - 1);
        nutAndBoltMatch(nuts, bolts, pivotLoc+1, high);
    }
}

int main() {
    char nuts[] = {')','@','*','^','(','%','!','$','&','#'};
    char bolts[] = {'!','(','#','%',' )','^','&','*','$','@'};
    int n = 10;
    nutAndBoltMatch(nuts, bolts, 0, n-1);
    cout << "After matching nuts and bolts:" << endl;
    cout << "Nuts:  "; show(nuts, n); cout << endl;
    cout << "Bolts: "; show(bolts, n); cout << endl;
}

ผลลัพธ์

After matching nuts and bolts:
Nuts:  ! # $ % & ( ) * @ ^
Bolts: ! # $ % & ( ) * @ ^