โปรแกรมหา Permutation ถัดไปของตัวเลขใน C++

ให้ตัวเลข n หา permutation ถัดไปที่มากกว่าเดิม (เรียงตัวเลข) ถ้าเป็น permutation สุดท้ายแล้ว ให้กลับไป permutation แรก (น้อยที่สุด)

ตัวอย่าง: n=319 → 391

ขั้นตอนการแก้ปัญหา (Next Permutation Algorithm)

1. แปลงตัวเลขเป็นอาร์เรย์หลัก
2. หา index i จากขวาไปซ้าย ที่ a[i] < a[i+1]
3. หา index j จากขวาไปซ้าย ที่ a[j] > a[i]
4. swap a[i], a[j]
5. reverse ส่วน a[i+1..end]
6. รวมกลับเป็นตัวเลข

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

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> makeArray(int x) {
        vector<int> ret;
        while (x) { ret.push_back(x%10); x/=10; }
        reverse(ret.begin(), ret.end());
        return ret;
    }
    int combine(vector<int>& v) {
        int ret = 0;
        for (int d : v) { ret = ret*10 + d; }
        return ret;
    }
    int getIndex(vector<int>& v) {
        int idx = -1;
        for (int i = v.size()-1; i >= 1; i--)
            if (v[i] > v[i-1]) { idx = i; break; }
        if (idx != -1) {
            int x = v[idx-1], best = idx;
            for (int j = idx+1; j < v.size(); j++)
                if (v[j] < v[best] && v[j] > x) best = j;
            swap(v[idx-1], v[best]);
        }
        return idx;
    }
    int solve(int num) {
        vector<int> v = makeArray(num);
        int idx = getIndex(v);
        if (idx == -1) sort(v.begin(), v.end());
        else sort(v.begin()+idx, v.end());
        return combine(v);
    }
};

int main() { cout << (new Solution())->solve(319); } // 391

อินพุต

319

เอาต์พุต

391