文档章节

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

一贱书生
 一贱书生
发布于 2016/11/22 10:22
字数 1210
阅读 6
收藏 0
点赞 0
评论 0

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

 */

 

注意:不考虑重复字符。若考虑重复字符,只需在加入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));//不保存排列,直接输出    

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 722
码字总数 600072
作品 0
一个算法问题,请各位大神帮忙!

完成一个方法,返回一种排列组合的所有字符串结果的数目。排列组合的规则如下: 1)排列组合的的字符串由a~z 26个小写字母组成; 2)方法入参为每个字符串长度; 3)每个字符串中的后一个字符...

WilliamHoward ⋅ 2014/08/20 ⋅ 4

next_permutation(全排列算法)

STL提供了两个用来计算排列组合关系的算法,分别是nextpermutation和prevpermutation。首先我们必须了解什么是“下一个”排列组合,什么是“前一个”排列组合。考虑三个字符所组成的序列{a,...

angel_kitty ⋅ 2017/02/12 ⋅ 0

【递归】阶乘、全排列 、组合、二分查找

递归(recursion):程序调用自身的编程技巧。 递归满足2个条件: 1)有反复执行的过程(调用自身) 2)有跳出反复执行过程的条件(递归出口) 最简单的例子是阶乘 全排列 从n个不同元素中任...

SibylY ⋅ 2016/07/03 ⋅ 0

js 代码片段2

大概就是只转不看吧。。。 Anagrams of string(带有重复项的全排列) 使用递归。对于给定字符串中的每个字母,为字母创建字谜。使用map()将字母与每部分字谜组合,然后使用reduce()将所...

阿豪boy ⋅ 02/20 ⋅ 0

精心收集的48个JavaScript代码片段

精心收集的48个JavaScript代码片段 程序师2017-12-184 阅读 javascript业界观察 该项目来自于Github用户Chalarangelo(文末有项目完整地址,原版为英文),目前已在Github上获得了3000多Sta...

程序师 ⋅ 2017/12/18 ⋅ 0

容斥原理

容斥原理 对容斥原理的描述 容斥原理是一种重要的组合数学方法,可以让你求解任意大小的集合,或者计算复合事件的概率。 描述 容斥原理可以描述如下: 要计算几个集合并集的大小,我们要先将...

angel_kitty ⋅ 2017/02/23 ⋅ 0

递归与动态规划

递归:将问题分解成子问题求解,从较小的问题逐渐逼近原始问题,很多时候只需要在f(n-1)中加入或移除某些东西或稍作修改就可以求得f(n) 动态规划与递归的区别:动态规划要将中间的结果缓...

memristor ⋅ 2014/04/17 ⋅ 0

排列组合算法

1.组合算法 1.1 方法一 本程序的思路是开一个数组,其下标表示1到m个数,数组元素的值为1表示其下标 代表的数被选中,为0则没选中。 首先初始化,将数组前n个元素置1,表示第一个组合为前n个...

面码 ⋅ 2014/05/15 ⋅ 0

Permutation test(排列(组合)检验)

对Permutation test 的首次描述可追溯到上个世纪30年代, Fisher( 1935) 和Pitman( 1937) 介绍了其在线性统计模型中的应用。但该法计算工作量过大, 其发展在随后的半个世纪里未 得到重视。上个...

pbyang ⋅ 2014/02/26 ⋅ 0

ROSALIND Bioinformatics(16-20)

刷题ROSALIND,练编程水平 http://rosalind.info/problems/list-view/ 16. Finding a Protein Motif (寻找蛋白质模体) image.png 解题思路 为表示蛋白质模体的多种形式,设计以下表示形式:[...

thinkando ⋅ 2017/11/16 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

android -------- 颜色的半透明效果配置

最近有朋友问我 Android 背景颜色的半透明效果配置,我网上看资料,总结了一下, 开发中也是常常遇到的,所以来写篇博客 常用的颜色值格式有: RGB ARGB RRGGBB AARRGGBB 这4种 透明度 透明度...

切切歆语 ⋅ 11分钟前 ⋅ 0

CentOS开机启动subversion

建立自启动脚本: vim /etc/init.d/subversion 输入如下内容: #!/bin/bash## subversion startup script for the server## chkconfig: 2345 90 10# description: start the subve......

随风而飘 ⋅ 14分钟前 ⋅ 0

Nginx + uwsgi @ubuntu

uwsgi 安装 sudo apt-get install python3-pip # 注意 ubuntu python3默认没有安装pippython3 -m pip install uwsgi 代码(test.py) def application(env, start_response): start_res......

袁祾 ⋅ 15分钟前 ⋅ 0

版本控制工具

CSV , SVN , GIT ,VSS

颖伙虫 ⋅ 18分钟前 ⋅ 0

【2018.06.19学习笔记】【linux高级知识 13.1-13.3】

13.1 设置更改root密码 13.2 连接mysql 13.3 mysql常用命令

lgsxp ⋅ 25分钟前 ⋅ 0

LVM

LVM: 硬盘划分分区成物理卷->物理卷组成卷组->卷组划分逻辑分区。 1.磁盘分区: fdisk /dev/sdb 划分几个主分区 输入t更改每个分区类型为8e(LVM) 使用partprobe生成分区的文件:如/dev/sd...

ZHENG-JY ⋅ 53分钟前 ⋅ 0

彻底删除Microsoft Office的方法

参照此链接彻底删除Office https://support.office.com/zh-cn/article/%e4%bb%8e-pc-%e5%8d%b8%e8%bd%bd-office-9dd49b83-264a-477a-8fcc-2fdf5dbf61d8?ui=zh-CN&rs=zh-CN&ad=CN......

Kampfer ⋅ 今天 ⋅ 0

大盘与个股之间关系

大盘走多:积极出手 顺势加码 大盘走空: 少量出手 退场观望 大盘做头:逆势减码 少量操作 大盘做底 : 小量建仓 小量试单

guozenhua ⋅ 今天 ⋅ 0

Day16 LVM(逻辑卷管理)与磁盘故障小案例

lvm详解 简述 LVM的产生是因为传统的分区一旦分区好后就无法在线扩充空间,也存在一些工具能实现在线扩充空间但是还是会面临数据损坏的风险;传统的分区当分区空间不足时,一般的解决办法是再...

杉下 ⋅ 今天 ⋅ 0

rsync实现多台linux服务器的文件同步

一、首先安装rsync,怎样安装都行,rpm,yum,还是你用源码安装都可以。因为我用的是阿里云的ESC,yum install rsync就ok了。 二、配置rsync服务 1.先建立个同步数据的帐号 123 groupadd r...

在下头真的很硬 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部