หาเลขสูงสุดจากการสลับหลัก (Max Number By Swapping)

บทนำ

กำหนดสตริงตัวเลขบวก ต้องการหาการเรียงสับเปลี่ยน (Permutation) ที่ให้ค่าสูงสุดโดยการสลับหลักได้ k ครั้ง

วิธีแก้: เลือกหลักหนึ่งแล้วสลับกับหลักถัดไปทีละตัวเพื่อหาค่าสูงสุด ทำซ้ำ k ครั้ง ใช้กลยุทธ์ Backtracking เพราะหากค่าที่ได้ไม่มากกว่าเดิม จะย้อนกลับไปตรวจสอบใหม่

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

Input: ตัวเลขหลายหลัก เช่น 129814999
Output: The maximum value from these digits by swapping them.
        The output is: 999984211

อัลกอริทึม

maxNum(number, swaps, maxNumber)

Input: สตริงตัวเลข, จำนวนครั้งที่สลับได้, สตริงค่าสูงสุด
Output: อัปเดต maxNumber ให้เป็นค่าสูงสุด

Begin
    if swaps = 0 then return
    n := จำนวนหลักในตัวเลข
    for i := 0 ถึง n-2 do
        for j := i+1 ถึง n-1 do
            if number[i] < number[j] then
                สลับ number[i] และ number[j]
                if number > maxNumber then maxNumber := number
                maxNum(number, swaps-1, maxNumber)
                สลับ number[i] และ number[j] อีกครั้งเพื่อ backtrack
        done
    done
End

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

#include <iostream>
using namespace std;

void maxNum(string str, int swaps, string &max) {
    if(swaps == 0) return;
    int n = str.length();
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (str[i] < str[j]) {
                swap(str[i], str[j]);
                if (str.compare(max) > 0) max = str;
                maxNum(str, swaps - 1, max);
                swap(str[i], str[j]);  // backtrack
            }
        }
    }
}

int main() {
    string str = "129814999";
    int swapNumber = 4;
    string max = str;
    maxNum(str, swapNumber, max);
    cout << "The given number is: " << str << endl;
    cout << "The maximum number is: " << max << endl;
}

ผลลัพธ์

The given number is: 129814999
The maximum number is: 999984211