首頁 > 後端開發 > C++ > 如何使用「std::next_permutation」和「std::prev_permutation」在 C 中高效率產生組合?

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

Susan Sarandon
發布: 2024-12-03 13:05:12
原創
487 人瀏覽過

How Can I Efficiently Generate Combinations in C   Using `std::next_permutation` and `std::prev_permutation`?

在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中文網其他相關文章!

來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
作者最新文章
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板