如何用C++编写控制台程序生成仅相邻移动且不重复移动的字符串排列？

Got it, let's tackle this problem step by step. First, let's clarify the exact rules from your examples to avoid confusion:

• We can only generate permutations by swapping adjacent characters in the original string.
• Once a character is swapped (moved), it can't be involved in any other swaps. This means overlapping swaps (like swapping positions 0-1 then 1-2) are forbidden, since the character at position 1 would be moved twice.
• The original string itself isn't included in the output (as seen in your ABC example).

Core Approach #

The problem boils down to finding all ways to select non-overlapping adjacent pairs in the string, swapping each selected pair, and collecting the unique results. We can use a recursive backtracking approach to explore all valid swap combinations efficiently:

1. Start at the first character of the string.
2. For each position, we have two choices:
   • Skip swapping the current character with its neighbor, and move to the next position.
   • Swap the current character with its neighbor (if possible), then jump two positions ahead (since both characters in the pair are now "used" and can't be swapped again).
3. Collect all unique permutations that aren't the original string.

C++ Implementation #

Here's a complete console application that implements this logic:

#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
#include <algorithm>

void generateValidPermutations(int currentIndex, std::string currentStr, const std::string& originalStr, std::unordered_set<std::string>& results) {
    // Base case: we've processed all characters
    if (currentIndex >= currentStr.size()) {
        // Skip the original string
        if (currentStr != originalStr) {
            results.insert(currentStr);
        }
        return;
    }

    // Choice 1: Do not swap current character with next, move to next index
    generateValidPermutations(currentIndex + 1, currentStr, originalStr, results);

    // Choice 2: Swap current character with next (if within bounds), then jump 2 indices
    if (currentIndex + 1 < currentStr.size()) {
        std::swap(currentStr[currentIndex], currentStr[currentIndex + 1]);
        generateValidPermutations(currentIndex + 2, currentStr, originalStr, results);
        // No need to backtrack here because we're passing currentStr by value (each recursive call gets a copy)
    }
}

int main() {
    std::string input;
    std::cout << "Enter your string: ";
    std::cin >> input;

    std::unordered_set<std::string> uniqueResults;
    generateValidPermutations(0, input, input, uniqueResults);

    // Convert to sorted vector for clean output
    std::vector<std::string> sortedResults(uniqueResults.begin(), uniqueResults.end());
    std::sort(sortedResults.begin(), sortedResults.end());

    std::cout << "\nValid permutations:\n";
    for (const auto& perm : sortedResults) {
        std::cout << "- " << perm << "\n";
    }

    return 0;
}

Key Details Explained #

• Recursive Logic: The recursion explores all valid swap paths without overlapping moves. By passing currentStr by value, each recursive branch works with its own copy of the string, so we don't need to manually reverse swaps (no backtracking cleanup required).
• Duplicate Prevention: Using an unordered_set automatically removes duplicate permutations, which is useful if your input string has repeated characters (e.g., input "AAB" will only output "ABA").
• Sorting: Converting the set to a sorted vector ensures the output is in alphabetical order for readability.
• Edge Cases: Handles empty strings, single-character strings (outputs nothing, since no swaps are possible), and strings with repeated characters correctly.

Test Results #

• Input ABC → Outputs ACB, BAC
• Input AUTO → Outputs ATUO, AUOT, UATO, UAOT
• Input ATOU (your forbidden example) will not be generated by this code, as it would require overlapping swaps (moving the same character twice).

内容的提问来源于stack exchange，提问作者Elia Prosperi