一列貨運列車有 n 節車廂, 第 i 節車廂停靠在第 i 個站點. 假設列車在裝載的時候, 不一定按照順序進行裝載, 即車廂的編號不一定有序. 在列車到達終點站之前需要經過一個緩衝站點. 當列車駛出緩衝站點之後, 要求所有車廂有序裝載, 也就是此時車廂的編號必定有序. 假設緩衝站點中有 k 個緩衝軌道. 我們首先使用數學語言, 簡化列車重排問題 : 針對某個排列 b_{1}b_{2}...b_{n}, 有一標準排列 a_{1}a_{2}...a_{n}. 要求使用 k 個緩衝區, 每一次只能將一個元素放入緩衝區, 每一次也只能從緩衝區取出一個元素. 當所有元素從緩衝中取出之後, 排列 b_{1}b_{2}...b_{n} 變為標準排列 a_{1}a_{2}...a_{n}. 其中對於任意 b_{j}, 必有一 a_{i} 與之對應, 即 a_{i} = b_{j}. 其中, i, j = 1, 2, ..., n

每一次只能有一個元素進入緩衝區, 每一次只能從緩衝區中取出一個元素, 那麼有兩個資料結構與之相符合, 也就是堆疊和佇列

現在, 我們暫時限制只能從緩衝區頂部取出元素, 因此我們使用堆疊作為存放車廂的緩衝區

首先要考慮的問題是, 當列車到達緩衝站點的時候, 什麼樣的車廂需要放入緩衝站點, 什麼樣的車廂可以直接駛出緩衝站點

考慮序列 581742963. 一般來說, 標準排列從小到大, 因此此處我們設標準排列為 123456789. 也就是說, 當所有車廂從緩衝區取出的時候, 原來的排列要變為標準排列. 根據標準排列, 只有當進入的第一個車廂是 1 的時候, 才允許車廂直接駛出緩衝站點; 其餘情況一律需要進入緩衝區. 當 1 號車廂駛出緩衝站點後, 接著就是等待 2, 3, ..., n 號車廂的過程

接著, 我們需要考慮緩衝區分配車廂的問題. 對於一個空的緩衝區來說, 可以直接放入車廂; 但是如果緩衝區不為空, 那麼就需要考慮放入的目標問題, 也就是某個車廂應該放入哪一個緩衝區比較合適. 不妨考慮將大的車廂放在小的車廂後面. 那麼如果要找到這個小的車廂, 則需要移動小的車廂後面的所有車廂. 這樣, 小的車廂才能被取出. 這種方法可行, 但是過於複雜, 如果我們限定每一次只能從緩衝區取出期望車廂, 而不能移動其它車廂, 那麼這個方法就行不通, 故我們考慮把小的車廂放在大的車廂後面. 在這種情況下, 就可能出現重排失敗的問題, 原因是緩衝區的數量不足, 而且所有的緩衝區頂部的車廂編號都比現在要進入緩衝區的車廂編號要小. 此時, 就需要擲出一個運作期的例外情況來說明重排失敗

每一次列車到來的時候, 根據標準排列, 將期望車廂設為標準排列的第一個元素. 當遇到期望車廂, 那麼就直接將車廂駛出緩衝區; 否則, 將車廂放入緩衝區. 在放入緩衝區的時候, 優先選擇; 當不存在空的緩衝區的時候, 根據緩衝區的順序規則將其放入. 因為我們在選擇空的緩衝區放入的時候, 是從前到後進行選擇, 自然越靠後的緩衝區中存放的車廂編號越大. 是否能夠放入的原則就是小的車廂放入大的車廂之後

每一次有車廂駛出緩衝車站的時候, 都要去緩衝軌道上尋找下一個期望車廂. 當軌道上沒有期望車廂的時候, 需要去緩衝區尋找. 只有所有能找的地方都沒有辦法找到的時候, 才繼續將軌道上的車廂放入緩衝區

#include <iostream>

template <typename Stack, std::size_t BufferSize, typename T, std::size_t N>
void train_rearrangement(T (&arr)[N], const T (&standard)[N]) {
    int excepted {};
    Stack buffer[BufferSize] {};
    int cursor {};
    int rearrangement_cursor {};
    while(excepted < N) {
        if(arr[cursor] == standard[excepted]) {     //檢查進入的車廂編號是否為我們期望的車廂
            arr[rearrangement_cursor++] = arr[cursor];      //駛出
            ++excepted;
            ++cursor;
            bool find {};
            do {        //尋找緩衝區中, 是否存在我們期望的車廂
                find = false;
                for(auto i {0}; i < BufferSize; ++i) {
                    if(buffer[i].empty()) {
                        continue;
                    }
                    if(buffer[i].top() == standard[excepted]) {
                        arr[rearrangement_cursor++] = buffer[i].top();
                        ++excepted;
                        buffer[i].pop();
                        find = true;
                        break;
                    }
                }
            }while(find);
            continue;
        }
        /* 駛入的車廂並不是我們期望的車廂 */
        bool pushed {};
        for(auto i {0}; i < BufferSize; ++i) {
            if(buffer[i].empty()) {     //如果緩衝區為空, 說明之前緩衝區中的車廂編號都比現在的車廂編號要小
                buffer[i].push(arr[cursor++]);
                pushed = true;
                break;
            }
            if(buffer[i].top() > arr[cursor]) {     //緩衝區中的車廂編號比現在的車廂要大
                buffer[i].push(arr[cursor++]);
                pushed = true;
                break;
            }
        }
        if(not pushed) {        //所有緩衝區都不為空, 而且所有緩衝區頂部的車廂編號都比現在的車廂要小, 說明緩衝區數量不足
            throw std::runtime_error("Too few buffers!");
        }
    }
}

如果標準排列是無序的, 那麼上述程式碼就沒有辦法適用, 這是因為我們採用小於或著大於進行比較, 而無序的標準排列只有等於或著不等於的比較. 因此, 此時只有依靠足夠的緩衝區才可以完成重排

堆疊每次都只能從它的頂部取出車廂, 如果換成佇列, 每次就只能從佇列頭部取出車廂. 此時, 我們只需要更改一個原則 : 每次將編號大的車廂放入到編號小的車廂之後就可以了. 使用佇列的實作此處不再累贅

最後, 我們需要分析程式碼的複雜度. 首先分析空間複雜度. 一種比較極端的情況是期望的車廂在最後一個才出現. 此時, 此時需要的額外空間數量為 n - 1. 其中, n 為要重排的元素數量. 剩下的都是一些輔助型的變數, 不妨設有 c 個, 其中 c 為常數. 那麼其空間複雜度為 O(n - 1 + c) = O(n)

然後分析這個程式碼的時間複雜度. 所有的車廂都要尋訪一邊, 那麼此處的時間複雜度至少為 O(n). 當有車廂駛出的時候, 我們需要檢查所有的緩衝區中是否存在可以駛出的車廂, 每一次檢查的複雜度為 O(k). 其中, k 為緩衝區數量 . 在最壞的情況下, 需要檢查 n - 1 次, 因此總的檢查時間複雜度為 O(k * (n - 1)) = O(k * n). 在車廂進入緩衝區的時候, 我們需要檢查所有緩衝區中是否存在可以讓車廂進入的緩衝區, 因此檢查的時間複雜度為 O(k). 最後, 這個程式總的時間複雜度為 O(k * n) + O(n) + O(k) = O(k * n)