文档章节

排列与组合

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

 

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

全排列:

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);
	}

 

© 著作权归作者所有

共有 人打赏支持
Cobbage

Cobbage

粉丝 46
博文 122
码字总数 65058
作品 0
闵行
QA/测试工程师
排列组合算法

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

面码 ⋅ 2014/05/15 ⋅ 0

next_permutation(全排列算法)

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

angel_kitty ⋅ 2017/02/12 ⋅ 0

小朋友学奥数(12):组合

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

翡翠森林Z ⋅ 2017/11/29 ⋅ 0

程序员必备算法——排列组合

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

窗边的扁豆 ⋅ 2017/10/07 ⋅ 0

一个算法问题,请各位大神帮忙!

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

WilliamHoward ⋅ 2014/08/20 ⋅ 4

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

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

SibylY ⋅ 2016/07/03 ⋅ 0

如何知道某个组合是否是一个排列组合中的一员

目标是如何知道某个组合是否是一个排列组合中的一员,有什么好的算法?例如C(4,10),如何知道组合1,2,3,4在这个排列中? @宏哥 @中山野鬼

技术揣摩 ⋅ 2013/09/27 ⋅ 4

公平选择组合

计算机学院有n(0using namespace std; int main(){int n, m;cin >> n >> m;int i = n;int*

程红玲OOO ⋅ 2016/11/29 ⋅ 0

对59个字符进行排列组合?

比如a,b,c的排列组合有a , b , c , ab , ac , ad ,...... ddd 字符少,好处理。但现在是要求对59个字符进行排列组合,内存只有1G。。

李渊 ⋅ 2011/03/02 ⋅ 11

软件可以像生物一样自我进化吗

我举个最简单的例子,软件说到底还是一串0和1的排列,也就是说一串0与1的组合排列就可能成为软件。那如果我们让计算机不断生成0与1 的组合不就可以实现软件的自我生成。当然这只是最原始的构...

zhouzqian ⋅ 2013/12/26 ⋅ 42

没有更多内容

加载失败,请刷新页面

加载更多

下一页

OSChina 周日乱弹 —— 这么好的姑娘都不要了啊

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @TigaPile :分享曾惜的单曲《讲真的》 《讲真的》- 曾惜 手机党少年们想听歌,请使劲儿戳(这里) @首席搬砖工程师 :怎样约女孩子出来吃饭,...

小小编辑 ⋅ 26分钟前 ⋅ 1

Jenkins实践3 之脚本

#!/bin/sh# export PROJ_PATH=项目路径# export TOMCAT_PATH=tomcat路径killTomcat(){pid=`ps -ef | grep tomcat | grep java|awk '{print $2}'`echo "tom...

晨猫 ⋅ 今天 ⋅ 0

Spring Bean的生命周期

前言 Spring Bean 的生命周期在整个 Spring 中占有很重要的位置,掌握这些可以加深对 Spring 的理解。 首先看下生命周期图: 再谈生命周期之前有一点需要先明确: Spring 只帮我们管理单例模...

素雷 ⋅ 今天 ⋅ 0

zblog2.3版本的asp系统是否可以超越卢松松博客的流量[图]

最近访问zblog官网,发现zlbog-asp2.3版本已经进入测试阶段了,虽然正式版还没有发布,想必也不久了。那么作为aps纵横江湖十多年的今天,blog2.2版本应该已经成熟了,为什么还要发布这个2.3...

原创小博客 ⋅ 今天 ⋅ 0

聊聊spring cloud的HystrixCircuitBreakerConfiguration

序 本文主要研究一下spring cloud的HystrixCircuitBreakerConfiguration HystrixCircuitBreakerConfiguration spring-cloud-netflix-core-2.0.0.RELEASE-sources.jar!/org/springframework/......

go4it ⋅ 今天 ⋅ 0

二分查找

二分查找,也称折半查找、二分搜索,是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于...

人觉非常君 ⋅ 今天 ⋅ 0

VS中使用X64汇编

需要注意的是,在X86项目中,可以使用__asm{}来嵌入汇编代码,但是在X64项目中,再也不能使用__asm{}来编写嵌入式汇编程序了,必须使用专门的.asm汇编文件来编写相应的汇编代码,然后在其它地...

simpower ⋅ 今天 ⋅ 0

ThreadPoolExecutor

ThreadPoolExecutor public ThreadPoolExecutor(int corePoolSize, int maximumPoolSize, long keepAliveTime, ......

4rnold ⋅ 昨天 ⋅ 0

Java正无穷大、负无穷大以及NaN

问题来源:用Java代码写了一个计算公式,包含除法和对数和取反,在页面上出现了-infinity,不知道这是什么问题,网上找答案才明白意思是负的无穷大。 思考:为什么会出现这种情况呢?这是哪里...

young_chen ⋅ 昨天 ⋅ 0

前台对中文编码,后台解码

前台:encodeURI(sbzt) 后台:String param = URLDecoder.decode(sbzt,"UTF-8");

west_coast ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部