在 C++ 中列印字串的所有排列

Jinku Hu 2023年1月30日 2021年6月28日
  1. 使用 std::next_permutation 在 C++ 中列印字串的所有排列
  2. 使用 std::prev_permutation 在 C++ 中列印字串的所有排列
在 C++ 中列印字串的所有排列

本文將介紹如何在 C++ 中列印給定字串的所有排列。

使用 std::next_permutation 在 C++ 中列印字串的所有排列

std:next_permutation 演算法修改給定的範圍,以便元素的排列按字典順序升序排列,如果存在這樣的排列,則返回一個真正的布林值。如果字串字元按降序排序,則該函式可以對 std::string 物件進行操作以生成其排列。我們可以使用 std::sort 演算法和 std::greater 函式物件對字串進行排序,然後呼叫 next_permutation 直到它返回 false。後者可以使用 do...while 迴圈實現,該迴圈將 next_permutation 語句作為條件表示式,並在每個迴圈中將字串列印到 cout 流。

#include <iostream>
#include <iterator>
#include <algorithm>
#include <limits>

using std::cout; using std::endl;
using std::string; using std::cin;

void PrintStringPermutations(string &str)
{
    std::sort(str.begin(), str.end(), std::greater<>());

    do {
        cout << str << endl;
    } while (std::next_permutation(str.begin(), str.end()));
}

int main() {
    string input;

    cout << "Enter string to print permutations: ";
    cin >> input;

    PrintStringPermutations(input);


    return EXIT_SUCCESS;
}

輸出:

Enter string to print permutations: nel
nle
nel
lne
len
enl
eln

使用 std::prev_permutation 在 C++ 中列印字串的所有排列

或者,我們可以利用 STL 中的另一種演算法 - std::prev_permutation,該演算法以相同的字典順序生成給定範圍的新排列,但在提供序列時儲存先前的排列。除了在 while 迴圈條件中呼叫 prev_permutation 函式之外,最終的解決方案仍然與前面的示例類似。

#include <iostream>
#include <iterator>
#include <algorithm>
#include <limits>

using std::cout; using std::endl;
using std::string; using std::cin;

void PrintStringPermutations(string &str)
{
    std::sort(str.begin(), str.end(), std::greater<>());

    do {
        cout << str << endl;
    } while (std::prev_permutation(str.begin(), str.end()));
}

int main() {
    string input;

    cout << "Enter string to print permutations: ";
    cin >> input;

    PrintStringPermutations(input);


    return EXIT_SUCCESS;
}

輸出:

Enter string to print permutations: nel
nle
nel
lne
len
enl
eln

此外,可以通過實現使用者字串驗證功能來確保更健壯的程式碼,該功能將列印輸入提示,直到使用者提供有效字串。請注意,所有列出的解決方案將僅解析來自命令列輸入的單個字串引數,並且不會讀取多字字串。

#include <iostream>
#include <iterator>
#include <algorithm>
#include <limits>

using std::cout; using std::endl;
using std::string; using std::cin;

void PrintStringPermutations(string &str)
{
    std::sort(str.begin(), str.end(), std::greater<>());

    do {
        cout << str << endl;
    } while (std::prev_permutation(str.begin(), str.end()));
}

template<typename T>
T &validateInput(T &val)
{
    while (true) {
        cout << "Enter string to print permutations: ";
        if (cin >> val) {
            break;
        } else {
            if (cin.eof())
                exit(EXIT_SUCCESS);
            cout << "Enter string to print permutations\n";
            cin.clear();
            cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
        }
    }
    return val;
}

int main() {
    string input;

    validateInput(input);
    PrintStringPermutations(input);

    return EXIT_SUCCESS;
}

輸出:

Enter string to print permutations: nel
nle
nel
lne
len
enl
eln
Author: Jinku Hu
Jinku Hu avatar Jinku Hu avatar

Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.

LinkedIn

相關文章 - C++ String