排列与组合
博客专区 > Cobbage 的博客 > 博客详情
排列与组合
Cobbage 发表于4年前
排列与组合
  • 发表于 4年前
  • 阅读 70
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 新注册用户 域名抢购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
粉丝 45
博文 109
码字总数 54478
×
Cobbage
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: