文档章节

排列与组合

Cobbage
 Cobbage
发布于 2013/10/01 17:28
字数 1003
阅读 70
收藏 1

 

一、递归的实现排练与组合

全排列:

public static void recursive(char[] test_array, int start, int end) {
		if (start == end) {
			for (int i = 0; i <= end; i++) {
				System.out.print(test_array[i] + " ");
			}
			System.out.println();
		} else {
			for (int j = start; j <= end; j++) {
				char temp = test_array[start];
				test_array[start] = test_array[j];
				test_array[j] = temp;

				recursive(test_array, start + 1, end);

				temp = test_array[start];
				test_array[start] = test_array[j];
				test_array[j] = temp;
			}
		}
	}

全排列去重 

public class Solution {
    public List<List<Integer>> permuteUnique(int[] num) {
		     	ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
			    permuteUnique(num, 0, result);
			    return result;
		}
		 
		private void permuteUnique(int[] num, int start, ArrayList<List<Integer>> result) {
		 
			if (start >= num.length ) {
				ArrayList<Integer> item = convertArrayToList(num);
				result.add(item);
			}
		 
			for (int j = start; j <= num.length-1; j++) {
				if (containsDuplicate(num, start, j)) {
					swap(num, start, j);
					permuteUnique(num, start + 1, result);
					swap(num, start, j);
				}
			}
		}
		 
		private ArrayList<Integer> convertArrayToList(int[] num) {
			ArrayList<Integer> item = new ArrayList<Integer>();
			for (int h = 0; h < num.length; h++) {
				item.add(num[h]);
			}
			return item;
		}
		 
		private boolean containsDuplicate(int[] arr, int start, int end) {
			for (int i = start; i <= end-1; i++) {
				if (arr[i] == arr[end]) {
					return false;
				}
			}
			return true;
		}
		 
		private void swap(int[] a, int i, int j) {
			int temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
}

字典顺序找位置

public class Solution {
    public String getPermutation(int n, int k) {  
        k--;//to transfer it as begin from 0 rather than 1
        
        List<Integer> numList = new ArrayList<Integer>();  
        for(int i = 1; i<= n; i++)
            numList.add(i);
       
        int factorial = 1;    
        for(int i = 2; i < n; i++)  
            factorial *= i;    
        
        StringBuilder res = new StringBuilder();
        int times = n-1;
        while(times>=0){
            int indexInList = k/factorial;
            res.append(numList.get(indexInList));  
            numList.remove(indexInList);  
            
            k = k%factorial;//new k for next turn
            if(times!=0)
                factorial = factorial/times;//new (n-1)!
            
            times--;
        }
        
        return res.toString();
    }
}

组合:这个组合是从后向前的i>=m

        如果从前向后应该是的i<=m

static void combine( int a[],int n,int m,int b[] )
	{ 
	 for(int i=n; i>=m; i--)  
	 {
	  b[m-1] = a[i-1];
	  if (m > 1)
	   combine(a,i-1,m-1,b);
	  else                    
	  {   
	   System.out.println(Arrays.toString(b));
	  }
	 }
	}

二、非递归方法

排列:1.首先排序递增,那么这是最小的字典顺序。一直到递减则是最后一个位置

        2.接着倒叙查找如果有大于前一个的位置(这说明有下一个排列)

        3.在上个可能的位置后面查找可能有最小的大于当前的值(这个是存在排列的一个最小的序)

        4.交换位置后一位后面是(递减的,要反转变成递增的)这样得到新列的最小序

        5.如果全部变成了递增额则排列结束了

public static void main(String[] args) {

		// TODO 自动生成方法存根
		WordBook a = new WordBook();
		Scanner input = new Scanner(System.in);
		System.out.print("请输入要排列的元素有多少种:");
		int count = input.nextInt();
		int[] p = new int[count];
		for (int i = 1; i <= p.length; i++) {
			p[i - 1] = i;
		}
		boolean con;
		long start=System.currentTimeMillis();
		do {
			a.pr(p);// 输出排列p
			con = a.next(p);// 求出按字典序排列的下一个排列p
		} while (con);
		System.out.println(System.currentTimeMillis()-start);
	}

	public int indexof(int[] n) {
		int index = -1;
		for (int i = n.length - 1; i >= 1; i--) {
			if (n[i - 1] < n[i]) {
				index = i - 1;
				break;
			}
		}
		return index;
	}

	public int indexmin(int ini, int[] n) {
		int index = n.length - 1;
		int min = n[ini + 1];
		for (int i = ini + 1; i < n.length; i++) {
			if (n[i] <= min && n[i] > n[ini]) {
				min = n[i];
				index = i;
			}
		}
		return index;
	}

	public void swap(int index1, int index2, int[] n) {
		int temp;
		temp = n[index1];
		n[index1] = n[index2];
		n[index2] = temp;
	}

	public void oppositeDirection(int index1, int[] n) {
		for (int i = index1 + 1, j = n.length - 1, k = 0, temp; k <= (n.length - i) / 2; i++, j--, k++) {
			temp = n[i];
			n[i] = n[j];
			n[j] = temp;
		}
	}

	public boolean next(int[] n) {
		int index1 = indexof(n);
		if (index1 == -1) {
			return false;
		}
		int index2 = indexmin(index1, n);
		swap(index1, index2, n);
		oppositeDirection(index1, n);
		return true;
	}

	public void pr(int[] n) {
		for (int i = 0; i < n.length; i++) {
			System.out.print(n[i] + "  ");
		}
		System.out.println();
	}

 组合:网上找的那个10排列的

//按照网上的10转换
	//输出有10的位置第一次位置 
	//然后调整为01
	//10左边的移动到左边
	static void combine2(int[]a,int n,int m,int[] b){
	 for(int i=0;i<m;i++)
		 b[i]=1;
	 do{
		 printArray(b,a);
	 }while(getFirstFlage(b,n,m)!=-1);
	}
	
	static int getFirstFlage(int[]b,int n,int m){
		int count=0;
		for(int i=0;i<n-1;i++){
			
			if(b[i]==1&&b[i+1]==0){
			     	//交换位置
				    b[i]=0;
				    b[i+1]=1;
				    //移动
				    for(int j=0;j<count;j++){
				    	b[j]=1;
				    }
				    for(int k=count;k<i;k++)
				    	b[k]=0;
				   // System.out.println(count+"=="+Arrays.toString(b));
				 return i;
			}else if(b[i]==1){
				count++;
			}
		}
		return -1;
	}
	static void printArray(int[]b,int[]a){
		for(int i=0;i<b.length;i++){
			if(b[i]==1)
			System.out.print(a[i]+" ");
		}
		System.out.println();
	}
	public static void main(String[] args) {
	 
	    int[] a=new int[]{1,2,3,4,5,6,7,8};
	    int[] b=new int[8];
	    combine2(a,a.length,3,b);
		//combine(a,a.length,2,b);
		//System.out.println("总的个数:"+k);
	}

 

© 著作权归作者所有

共有 人打赏支持
下一篇: memcached
Cobbage

Cobbage

粉丝 50
博文 146
码字总数 73307
作品 1
闵行
QA/测试工程师
私信 提问
next_permutation(全排列算法)

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

angel_kitty
2017/02/12
0
0
小朋友学奥数(12):组合

一、定义 从n个不同的元素中,任取m(m≤n)个元素为一组,叫作从n个不同元素中取出m个元素的一个组合。 二、例题 从甲、乙、丙3名同学中选出2名去参加一项活动,有多少种不同的选法? 分析:...

翡翠森林Z
2017/11/29
0
0
程序员必备算法——排列组合

程序员必备算法——排列组合 [TOC] 还记得排列组合吗? 在高中的时候最常接触的莫过于排列组合了,毕竟高考必考的嘛。我们先来回忆下这两个的公式是啥: 如果看到这个还有一丢丢的印象,说明...

窗边的扁豆
2017/10/07
0
0
【递归】阶乘、全排列 、组合、二分查找

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

SibylY
2016/07/03
32
0
一个算法问题,请各位大神帮忙!

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

WilliamHoward
2014/08/20
273
4

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周一乱弹 —— 白掌柜说了卖货不卖身

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @爱漫爱 :这是一场修行分享羽肿的单曲《Moony》 手机党少年们想听歌,请使劲儿戳(这里) @clouddyy :开不开心? 开心呀, 我又不爱睡懒觉…...

小小编辑
今天
15
3
大数据教程(11.7)hadoop2.9.1平台上仓库工具hive1.2.2搭建

上一篇文章介绍了hive2.3.4的搭建,然而这个版本已经不能稳定的支持mapreduce程序。本篇博主将分享hive1.2.2工具搭建全过程。先说明:本节就直接在上一节的hadoop环境中搭建了! 一、下载apa...

em_aaron
今天
5
0
开始看《JSP&Servlet学习笔记》

1:WEB应用简介。其中1.2.1对Web容器的工作流程写得不错 2:编写Servlet。搞清楚了Java的Web目录结构,以及Web.xml的一些配置作用。特别是讲了@WebServlet标签 3:请求与响应。更细致的讲了从...

max佩恩
今天
5
0
mysql分区功能详细介绍,以及实例

一,什么是数据库分区 前段时间写过一篇关于mysql分表的的文章,下面来说一下什么是数据库分区,以mysql为例。mysql数据库中的数据是以文件的形势存在磁盘上的,默认放在/mysql/data下面(可...

吴伟祥
今天
5
0
SQL语句查询

1.1 排序 通过order by语句,可以将查询出的结果进行排序。放置在select语句的最后。 格式: SELECT * FROM 表名 ORDER BY 排序字段ASC|DESC; ASC 升序 (默认) DESC 降序 1.查询所有商品信息,...

stars永恒
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部