7-3 字符串的全排列

字符串的全排列可以通过递归实现。具体实现步骤如下：

1. 如果字符串为空或者只有一个字符，那么它的全排列就是它本身。
2. 否则，将第一个字符和后面的所有字符依次交换，得到新的字符串，并递归求新字符串的全排列。
3. 固定第一个字符，递归求后面所有字符的全排列。
4. 重复上述步骤，直到所有字符都被固定为止。

以下是代码实现：

def permutation(s):
    def dfs(index):
        if index == n:
            res.append(''.join(s))
            return
        for i in range(index, n):
            s[index], s[i] = s[i], s[index]
            dfs(index + 1)
            s[index], s[i] = s[i], s[index]

    n = len(s)
    res = []
    s = list(s)
    dfs(0)
    return res

例如，对于字符串 "abc"，调用 `permutation("abc")` 将返回其全排列 `["abc", "acb", "bac", "bca", "cab", "cba"]`。

相关问题

字符串全排列python

要实现字符串的全排列，可以使用递归的方法。下面是一个使用Python实现的示例代码：

def permute(s):
    # 如果字符串长度为1，则直接返回该字符串
    if len(s) == 1:
        return [s]

    # 递归地对字符串的每个字符进行全排列
    permutations = []
    for i in range(len(s)):
        # 将当前字符与其他字符交换位置
        for perm in permute(s[:i] + s[i+1:]):
            permutations.append(s[i] + perm)

    return permutations

# 测试代码
s = "abc"
result = permute(s)
for perm in result:
    print(perm)

运行上述代码会输出字符串 "abc" 的全排列：

abc
acb
bac
bca
cab
cba

希望对你有帮助！如果还有其他问题，请随时提问。

C++实现字符串全排列

要实现字符串的全排列，可以使用递归的方法。下面是一个使用C++实现字符串全排列的示例代码：

#include <iostream>
#include <string>
using namespace std;

// 交换字符串中两个字符的位置
void swap(char& a, char& b) {
    char temp = a;
    a = b;
    b = temp;
}

// 对字符串进行全排列
void permute(string& str, int start, int end) {
    if (start == end) {
        cout << str << endl;  // 输出排列结果
        return;
    }

    for (int i = start; i <= end; i++) {
        swap(str[start], str[i]);  // 将第i个字符放到起始位置
        permute(str, start + 1, end);  // 对剩余字符进行全排列
        swap(str[start], str[i]);  // 恢复原始顺序，以便进行下一次交换
    }
}

int main() {
    string str;
    cout << "请输入一个字符串：";
    cin >> str;

    cout << "字符串的全排列结果为：" << endl;
    permute(str, 0, str.length() - 1);

    return 0;
}

以上代码中，`permute`函数使用递归的方式实现了字符串的全排列。首先判断起始位置`start`是否等于结束位置`end`，如果相等，则表示已经完成了一种排列，输出结果并返回。否则，从起始位置开始，依次将每个字符与起始位置交换，然后递归调用`permute`函数对剩余字符进行全排列，最后再次交换字符的顺序，以便进行下一次交换。

在`main`函数中，首先输入一个字符串，然后调用`permute`函数进行全排列，并将结果输出。