文档章节

排列与组合

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

 

© 著作权归作者所有

共有 人打赏支持
Cobbage

Cobbage

粉丝 48
博文 136
码字总数 70152
作品 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
一个算法问题,请各位大神帮忙!

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

WilliamHoward
2014/08/20
249
4
【递归】阶乘、全排列 、组合、二分查找

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

SibylY
2016/07/03
32
0

没有更多内容

加载失败,请刷新页面

加载更多

AOSP Build System —— Soong

Soong Soong is the replacement for the old Android make-based build system. It replaces Android.mk files with Android.bp files, which are JSON-like simple declarative descriptio......

雪落青山
33分钟前
1
0
Unity C# lock关键字的坑

Unity 5.6 环境下的 lock关键字,在特定的多线程环境下会死锁 崩溃 其中一种情况: 异步socket 操作,由于内部是一个线程池回调的异步回调,操作同一个对象时 lock关键字会概率出现死锁 闪退...

梦想游戏人
45分钟前
1
0
redis-hash

哈希类型是指健值本身又是一个键值对结构 基本命令: hset key field value 设置值 hget(获取),hdel(删除),hlen(计算field个数),hmget(批量设置),hexists(是否存在),hkeys(获取所有的...

拐美人
今天
2
0
简单的svm例子

数据来源:https://github.com/oumiga1314/Coursera-ML-AndrewNg-Notes/blob/master/code/ex6-SVM/data/ex6data1.mat import pandas as pd import numpy as np import scipy.io as sio impor......

南桥北木
今天
1
0
android 关于View的一些整理

1、Button text的值为英文时,会自动转换成大写。如需取消,设置android:textAllCaps="false" 2、控件的可见性 可以在layout的配置文件中,配置android:visibility属性 调用setVisibility()...

西米小娅
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部