文档章节

确定某字符串的所有排列组合

一贱书生
 一贱书生
发布于 2016/11/22 10:22
字数 1210
阅读 524
收藏 0

码上生花,ECharts 作品展示赛正式启动!>>>

/**
 * 功能:确定某字符串的所有排列组合。

 */

 

注意:不考虑重复字符。若考虑重复字符,只需在加入permulations时去掉重复的字符串即可。

 

 

[java] view plain copy

 

  1. /** 
  2.  * 思路:元素由少到多,将新的元素塞进所有字符串中间的任意可能位置。 
  3.  * @param str 
  4.  * @return 
  5.  */  
  6. public static ArrayList<String> getPerms(String str){  
  7.       
  8.     if(str==null)  
  9.         return null;  
  10.       
  11.     ArrayList<String> permutations=new ArrayList<String>();  
  12.     if(str.length()==0){  
  13.         permutations.add("");  
  14.         return permutations;  
  15.     }  
  16.       
  17.     char first=str.charAt(0);  
  18.     String remainder=str.substring(1);  
  19.     ArrayList<String> words=getPerms(remainder);  
  20.     for(String word:words){  
  21.         for(int i=0;i<=word.length();i++){  
  22.             String s=insertCharAt(word, first, i);  
  23.             permutations.add(s);  
  24.         }  
  25.     }  
  26.       
  27.       
  28.       
  29.     return permutations;  
  30. }  
  31.   
  32. public static String insertCharAt(String word,char c,int i){  
  33.     String start=word.substring(0, i);  
  34.     String end=word.substring(i);  
  35.     return start+c+end;  

一,问题描述

给定一个字符串,求出该字符串的全排列。

比如:"abc"的全排列是:abc、acb、bac、bca、cab、cba

 

二,实现思路

采用递归的方式求解。每次先选定一个字符,然后进行“若干次”交换,求出在选定这个字符的条件下,所有的全排列,并把字符“复位”再交换回来。至此,一趟全排列完成。第二趟,选定下一个字符,然后进行“若干次”交换,求出在选定这个字符的条件下,所有的全排列,并把字符“复位”再交换回来。.....

就类似于:(参考网上的解释如下:)

复制代码

设R={r1,r2,...rn}是要进行排列的n个元素.Ri=R-{ri}.集合X中元素的全排列记为 
    Perm(X).(ri)Perm(X)表示在全排列Perm(X)的每一个排列前加上前缀ri得到的排列 
    R的全排列可归纳定义如下: 
        当n=1时,Perm(R)=(r),其中r是集合R中唯一的元素; 
        当r>1时,Perm(R)由(r1)Perm(r1),(r2)Perm(r2).....(rn)Perm(rn)构成. 


全排列就是从第一个数字起每个数分别与它后面的数字交换
去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换, 用编程的话描述就是第i个数与第j个数交换时,要求[i,j)中没有与第j个数相等的数。

复制代码

 

代码实现如下:使用一个LinkedList<String>保存每一种排列,如果字符串中出现有重复的字符,则此方法会求出 重复的排列数,因而LinkedList<String>会保存重复的排列。

复制代码

import java.util.Collections;
import java.util.LinkedList;

public class Permutation {
    
    public static void allPermutation(String str){
        if(str == null || str.length() == 0)
            return;
        //保存所有的全排列
        LinkedList<String> listStr = new LinkedList<String>();
        
        allPermutation(str.toCharArray(), listStr, 0);
        
        print(listStr);//打印全排列
    }
    
    
    private static void allPermutation(char[] c, LinkedList<String> listStr, int start){

        
        if(start == c.length-1)
            listStr.add(String.valueOf(c));
        else{
            for(int i = start; i <= c.length-1; i++)
            {
                swap(c, i, start);//相当于: 固定第 i 个字符
                allPermutation(c, listStr, start+1);//求出这种情形下的所有排列
                swap(c, start, i);//复位
            }
        }
    }
    
    private static void swap(char[] c, int i, int j){
        char tmp;
        tmp = c[i];
        c[i] = c[j];
        c[j] = tmp;
    }
    
    private static void print(LinkedList<String> listStr)
    {
        Collections.sort(listStr);//使字符串按照'字典顺序'输出
        for (String str : listStr) {
            System.out.println(str);
        }
        System.out.println("size:" + listStr.size());
    }
    
    //hapjin test
    public static void main(String[] args) {
//        allPermutation("hapjin");
        allPermutation("abc");
    }
}

复制代码

 

如果要想让重复的排列只保存一次,有两种方式:①改进算法,不生成重复的排列  ②用HashSet来保存排列

 

那当字符串中出现重复的字符时,如何生成不重复的排列?---去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换

代码实现如下:(当有重复字符时,也可生成所有正确的排列(排列不会重复))

复制代码

public class Permutation {
    
    public static void allPermutation(String str){
        if(str == null || str.length() == 0)
            return;
        //保存所有的全排列
        LinkedList<String> listStr = new LinkedList<String>();
        
        allPermutation(str.toCharArray(), listStr, 0);
        
        print(listStr);//打印全排列
    }
    
    
    private static void allPermutation(char[] c, LinkedList<String> listStr, int start){

        if(start == c.length-1)
            listStr.add(String.valueOf(c));//System.out.println(String.valueOf(c));
        else{
            for(int i = start; i <= c.length-1; i++)
            {
                //只有当没有重叠的字符 才交换
                if(!isSwap(c, start, i))
                {
                    swap(c, i, start);//相当于: 固定第 i 个字符
                    allPermutation(c, listStr, start+1);//求出这种情形下的所有排列
                    swap(c, start, i);//复位
                }
            }
        }
    }
    
    private static void swap(char[] c, int i, int j){
        char tmp;
        tmp = c[i];
        c[i] = c[j];
        c[j] = tmp;
    }
    
    private static void print(LinkedList<String> listStr)
    {
        Collections.sort(listStr);//使字符串按照'字典顺序'输出
        for (String str : listStr) {
            System.out.println(str);
        }
        System.out.println("size:" + listStr.size());
    }
    
    //[start,end) 中是否有与 c[end] 相同的字符
    private static boolean isSwap(char[] c, int start, int end)
    {
        for(int i = start; i < end; i++)
        {
            if(c[i] == c[end])
                return true;
        }
        return false;
    }
    
    //hapjin test
    public static void main(String[] args) {
//        allPermutation("hapjin");
        allPermutation("aba");
    }
}

复制代码

 

上面的实现将所有的排列顺序都保存到LinkedList<String>了,这是要注意的。当然也可以不保存排列的顺序,直接输出(allPermutation方法)。

if(start == c.length-1)
    listStr.add(String.valueOf(c));//保存排列
    //System.out.println(String.valueOf(c));//不保存排列,直接输出    

© 著作权归作者所有

一贱书生
粉丝 21
博文 723
码字总数 600123
作品 0
私信 提问
加载中
请先登录后再评论。
输入一个字符串,输出该字符中字符的所有组合。

前言 在此研究: 1)给定一个字符串,如何对其中字母进行排列组合; 2)进一步了解Python递归。 题目内容 在指定位置编写代码,完成函数,根据给定的字符串,给出组成该字符串的字符的所有排...

osc_1h425qie
2019/02/20
7
0
Leetcode题解——算法思想之搜索

BFS 1. 计算在网格中从原点到特定点的最短路径长度 2. 组成整数的最小平方数数量 3. 最短单词路径 DFS 1. 查找最大的连通面积 2. 矩阵中的连通分量数目 3. 好友关系的连通分量数目 4. 填充封...

osc_9n23s39i
2019/06/12
12
0
剑指offer--字符串全排列/全组合

题目: 输入一个字符串,打印出该字符串中字符的所有排列。 例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 思路: 把一个字符串看成两部分组成...

osc_odyg6b92
2018/07/13
6
0
算法9-----输出全排列(递归)---移除K个数,剩下最小数。

1、题目:给定一个字符串,输出所有的字典序。 如: 输入字符串:'ac',输出:['ac','ca'] 输入字符串:‘abc' ,输出:['abc','acb','bac','bca','cab','cba'] 输入字符串:‘acc',输出:[......

osc_ch5yaeax
2018/04/27
4
0
剑指Offer-29-字符串的排列

题目 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 注意:字符可能重复! 比如,a...

SpecialYang
2018/07/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

JeecgBoot 连接达梦数据库

JeecgBoot连接达梦数据库 一、达梦数据库官网下载地址 http://www.dameng.com/down.aspx?TypeId=11&FId=t14:11:14 项目采用DMB8开发版(windows64位) 二、需要两个jar,可在达梦数据库安装...

JEECG开源社区
36分钟前
24
0
迅捷CAD转换器好不好用?

大家在工作中有掌握一些必备的CAD小技巧吗?比如怎么实现DWG与DXF互转?我们应该使用什么工具?下面小张给大家带来一款实用软件(迅捷CAD转换器)的图文教程分享,有兴趣和有需要的小伙伴们仔...

逆风小师傅
37分钟前
15
0
gitee仓库管理入门

gitee就是码云。只是入门笔记。 1.gitee注册,git下载安装。这个简单就不说了。 查看git配置: git config --list 配置用户名 邮箱 密码 git config --global user.name "用户名"git co...

仙游度尾东峰黄恩赐
38分钟前
11
0
Linux初学之bash相关

bash的颜色显示规则: ascll编码对于颜色进行设置 \033: ctrl键 [ :控制字符和颜色代码之间的间隔字符 0m:关闭颜色属性的命令 1m:对于显示的文本字符进行加粗 4m:为文本字符加下划线标识...

osc_umiwij2c
38分钟前
13
0
linux初学之——权限管理

上篇已经提到用户和组的管理相关知识,我们已经学会了如何在Linux系统中创建了用户和组,并对用户和组的内容和属性做一些修改。但是我们知道Linux系统是多用户多任务的操作系统,多个合法用户...

osc_znv7pwo3
40分钟前
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部