如何使用「std::next_permutation」和「std::prev_permutation」在 C 中高效率產生組合？

在C 語言中產生組合

問題介紹

生成組合是各種語言中常見的操作程式設計場景。它包括建立包含來自較大集合的指定數量元素的集合。本文探討如何解決在 C 中產生組合的挑戰。

使用 std::next_permutation 的解決方案

一個有效的方法是利用 std::next_permutation 函數來自 C 標準函式庫。這是一個實作：

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    int n, r;
    std::cin >> n >> r;

    std::vector<bool> v(n);
    std::fill(v.end() - r, v.end(), true);

    do {
        for (int i = 0; i < n; ++i) {
            if (v[i]) {
                std::cout << (i + 1) << " ";
            }
        }
        std::cout << "\n";
    } while (std::next_permutation(v.begin(), v.end()));
    return 0;
}

此解決方案首先建立一個選擇陣列 (v) 並將 r 選擇器放置在最後 r 個位置。 std::next_permutation 函數產生這些選擇器的所有排列。對於每個排列，它都會列印與所選位置相對應的集合成員。

與std::prev_permutation 替代

對於組合應以不同方式輸出的情況順序，請考慮使用std::prev_permutation 取代：

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
   int n, r;
   std::cin >> n >> r;

   std::vector<bool> v(n);
   std::fill(v.begin(), v.begin() + r, true);

   do {
       for (int i = 0; i < n; ++i) {
           if (v[i]) {
               std::cout << (i + 1) << " ";
           }
       }
       std::cout << "\n";
   } while (std::prev_permutation(v.begin(), v.end()));
   return 0;
}

此變體會交替順序的組合，使輸出更容易解釋。

以上是如何使用「std::next_permutation」和「std::prev_permutation」在 C 中高效率產生組合？的詳細內容。更多資訊請關注PHP中文網其他相關文章！