数据结构与算法--字符串的排列组合问题

谁借莪１个温暖的怀抱￠ 2022-10-15 08:59 145阅读 0赞

#### 字符串的全排列 ####

*  题目：输入一个字符串，打印出改字符串中所有字符的所有排列。例如输入字符串abc，那么打印出由a，b，c字符组成的所有字符串：abc，acb，bac，bca，cab，cba
 *  如何求解全排列，这个问题初看还是比较复杂的，在之前的文章 ：[数据结构与算法–代码完整性案例分析][Link 1]中我们在解决问题 “打印1 到最大的n位数” 的时候也用了全排列的方式是解决，思路是将1~n 位看成独立的一位，然后每一位都可能是 0 ~ 9 的组合，这样递归去排列每一位。
 *  借鉴上文中的这题的思路进行全排列看似能找到解决方案，但是此处又有所不同，因为上文中全排列是按位来枚举，此处不行，不能重复，例如，abc无法出现 aaa的排列字符串。
 *  分析
    
     *  借鉴之前文章中的全排列思想，我们还是逐个字符串分析
     *  将字符串看成是两部分组成，第一部分是第一个字符，第二部分是后面所有字符串。

![在这里插入图片描述][20210524145949230.png]

*  观察如上案例，我们看到，我们固定第一个字符，然后求后面字符的全排列
 *  接着，我们固定后面字符的第一个字符，再求后面字符的全排列，依次类推，这个步骤我们可以通过递归来实现
 *  在观察看，以上三种情况，第一个将a与第一个字符交换得，第二个将a与第二个字符交换，三个将a与第三个字符交换
 *  得到结论，当固定第一个字符时候，我们将第一个字符分别与后面的n个字符分别交换，得到第一个字符的全排列，
 *  接着固定第一个字符，从第二个字符开始，求第二个字符的全排列，这样就避免了出现aaa的情况，并且也可以通过递归去解决此问题
 *  通过如上分析，有如下代码：

/** * 求字符串的全排列 * * @author liaojiamin * @Date:Created in 12:07 2021/5/24 */
    public class Permutation { 
    
        public static void main(String[] args) { 
            permutationArray("ertgf");
        }
    
        public static void permutationArray(String arr) { 
            char[] pChars = arr.toCharArray();
            permutationArray(pChars, 0);
        }
    
        public static void permutationArray(char[] pChars, Integer start){ 
            if(pChars == null || pChars.length <= 1 || start == pChars.length - 1){ 
                printArray(pChars);
            }
            for (int i = start;i<=pChars.length-1;i++){ 
                char temp = pChars[i];
                pChars[i] = pChars[start];
                pChars[start] = temp;
                permutationArray(pChars, start +1);
                temp = pChars[i];
                pChars[i] = pChars[start];
                pChars[start] = temp;
            }
        }
    
        public static void printArray(char[] pChars){ 
            if(pChars == null || pChars.length <= 1){ 
                return;
            }
            for (char pChar : pChars) { 
                System.out.print(pChar+",");
            }
            System.out.println();
        }
    }

#### 字符串组合 ####

*  以上我们解决了字符串的全排列问题，如果我们需要得到字符串的所有组合应该怎么办？
 *  还是输入三个字符a，b，c，那么会有如下组合a,b,c,ab,ac,bc,abc
 *  如果我们安如上思路进行交换虽然能得到不同的排列，但是得到的确实同一个组合，例如，ab和ba是不同的排列，但是只是一个组合。
 *  我们将组合问题归类如下数学描述：
    
     *  如果输入n个字符，则这n个字符能构成长度为 1 ~ n de zuhe
     *  在求解n个字符 的 长度为 m的组合（1<=m <=n）的组合时候我们还是同上面思路，将n个字符串分为两部分第一个字符和其余所有字符
        
         *  如果第一个字符参与组合，则下一步在剩余 n-1个字符中挑选m - 1个
         *  如果第一个字符不参与组合，则下一步在剩余 n-1个字符中挑选m个
 *  依次按如上逻辑执行每一个位置的逻辑，直到 n 字符到达最后一个字符，或者，获取到m个字符为止
 *  根据如上分析有如下代码：

public static void main(String[] args) { 
            permutationArray("ertgf");
            combination("abcde".toCharArray());
        }
        
     public static void combination(char[] pChars){ 
            if(pChars == null){ 
                return;
            }
            Stack<Character> combinaChar = new Stack<>();
            for (Integer i = 1; i <= pChars.length; i++) { 
                combination(pChars, 0, i, combinaChar);
            }
        }
        
    /** * 求解字符串的所有组合 * */
        public static void combination(char[] pChars, Integer begin, Integer number, Stack<Character> combinaChar){ 
            if(number <= 0){ 
                System.out.println(combinaChar.toString());
                return;
            }
            if(begin == pChars.length){ 
                return;
            }
            //第一个字符放入组合中
            combinaChar.push(pChars[begin]);
            combination(pChars, begin +1, number-1, combinaChar);
            //第一个字符不放入组合中
            combinaChar.pop();
            combination(pChars, begin+1, number, combinaChar);
        }

[上一篇：数据结构与算法–二叉查找树转顺序排列双向链表][Link 2]  
[下一篇：数据结构与算法-- 八皇后问题（两种实现方案）][--]

[Link 1]: https://blog.csdn.net/liaojiamin0102/article/details/115199996
[20210524145949230.png]: /images/20221014/12c0d23e3803410292a0d8782373e47a.png
[Link 2]: https://blog.csdn.net/liaojiamin0102/article/details/117084229
[--]: https://blog.csdn.net/liaojiamin0102/article/details/117294938