字符串全排列的问题 python和c语言实现

刺骨的言语ヽ痛彻心扉 2022-05-14 03:38 170阅读 0赞

# 前言 #

这是一个的经典的问题  
设计一个算法，输出一个字符串字符的全排列。  
比如，String = “abc”  
输出是"abc",“bac”,“cab”,“bca”,“cba”,“acb”

# 解法 #

从集合依次选出每一个元素，作为排列的第一个元素，然后对剩余的元素进行全排列，如此递归处理；  
比如：首先我要打印abc的全排列，就是第一步把a 和bc交换（得到bac,cab），这需要一个for循环，循环里面有一个swap，交换之后就相当于不管第一步了，进入下一步递归，所以跟一个递归函数， 完成递归之后把交换的换回来，变成原来的字串

abc 为例子：
    1. 固定a, 求后面bc的全排列： abc, acb。 求完后，a 和 b交换； 得到bac,开始第二轮
    2. 固定b, 求后面ac的全排列： bac, bca。 求完后，b 和 c交换； 得到cab,开始第三轮
    3. 固定c, 求后面ba的全排列： cab, cba
     即递归树： 
    　　　　　str:　　 a    　　　　 b 　　　　　　  c
    　　　　　　 　　ab ac     　　ba bc  　　　     ca cb
    　   　result:     abc acb    　 bac bca　     　   cab cba

大概情况如下  
![这里写图片描述][650482900-553cb3be6f419_articlex]

# 代码 #

## c语言实现 ##

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    void swap(char *s, int i, int j)
    {
        char temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }
    
    void permutation(char *s, int from, int to)
    {
        if (to <= 1)
        {
            return;
        }
        if (from == to)
        {
            printf("%s\n", s);
        }
        else
        {
            for (int i=from; i <= to; i++)
            {
                swap(s, i, from);
                permutation(s, from + 1, to);
                swap(s, from, i);
            }
        }
    
    }
    
    int main()
    {
        char s[] = "123";
        permutation(s, 0, strlen(s) - 1);
        return 0;
    }

## python实现 ##

def perm(s=''):
        if len(s) <= 1:
            return [s]
        sl = []
        for i in range(len(s)):
            for j in perm(s[0:i] + s[i + 1:]):
                sl.append(s[i] + j)
        return sl
    
    print(perm("123"))

# 相似题目 #

leetcode中有一题很相似的题目 [leetcode 567. Permutation in String][]

# 参考 #

[https://segmentfault.com/a/1190000002710424\#articleHeader0][https_segmentfault.com_a_1190000002710424_articleHeader0]

[650482900-553cb3be6f419_articlex]: /images/20220514/763d2f06633c4374b3ae3d852990e11e.png
[leetcode 567. Permutation in String]: https://blog.csdn.net/sty945/article/details/80293289
[https_segmentfault.com_a_1190000002710424_articleHeader0]: https://segmentfault.com/a/1190000002710424#articleHeader0