排列与组合问题

╰+攻爆jí腚メ 2021-11-15 12:08 328阅读 0赞

排列和组合问题是算法中比较常见的问题，在这一节里，我们将对常见的排列和组合问题进行探讨。

（1）给定数字位数和进制，打印出所有的组合。

对于这个问题，按照人的思维，就是对数字的每一个位进行不断选值，如3位2进制数，那么我们首先取最高位为0，取好后，再对次高位进行选值，次高位选好后，再对最低位取值位0，此时已经对所有位都取完值，直接输出即可。需要说明的是，这里需要事先声明一个数组用来保存每一位的取值。当输出完毕后，如果最低位已经遍历完所有的二进制数，则回朔到上一层，修改次高位的值，以此类推，直到最高位遍历完所有的进制数。

程序如下：

package com.majing.test;
    
    public class test1 {
    	
    	public static void main(String[] args) 
    	{
    		print(3,2);
    	}
    	
    	private static int[] array=null;
    	public static void print(int n,int b)
    	{
    		assert n>0 && b>1;
    		if(null==array)
    		{
    			array=new int[n];
    		}
    		print(n,n,b);
    	}
    	public static void print(int n,int cur,int b)
    	{
    		
    		if(cur<=0)
    		{
    			for(int i=n-1;i>=0;i--)
    			{
    				System.out.print(array[i]);
    			}
    			System.out.println();
    			return;
    		}
    		for(int i=0;i<b;i++)
    		{
    			array[cur-1]=i;
    			print(n,cur-1,b);
    		}
    	}
    }

测试结果如下所示：

000
    001
    010
    011
    100
    101
    110
    111

（2）给定N个数，输出这N个数的全排列（N个数各不相同）

对于这个问题，我们也可以采用递归的方式来进行求解，假设这N个数保存在大小为N的数组中，对于N个数的全排列，我们可以将其缩小为N-1个数的全排列，具体方法就是将这N个数都与第一个数进行交换（当然第一个数不需要交换，因为它们两是重合的），如1与2，1与3，...，1与N分别交换，对于每一次交换都递归求出剩下N-1个数的全排列，这样当1与2，1与3，...，1与N所有的组合都被遍历完后，N个数的全排列也就全部遍历出来了。

程序：

/**
    	 * 输出[1-n]的N个数的全排列
    	 */
    	private static int[] arrayfull={1,2,3,4};
    	public static void printfull(int[] array)
    	{
    		assert array!=null && array.length!=0;
    		printfull(arrayfull,arrayfull.length,0);
    	}
    	private static void printfull(int[] array,int n,int cur)
    	{
    		if(cur==n)
    		{
    			System.out.println(Arrays.toString(arrayfull));
    			return;
    		}
    		for(int i=cur;i<n;i++)
    		{
    			swap(arrayfull,cur,i);
    			printfull(arrayfull,n,cur+1);
    			swap(arrayfull,cur,i);
    		}
    	}
    
    	private static void swap(int[] array,int i,int j)
    	{
    		int tmp=array[i];
    		array[i]=array[j];
    		array[j]=tmp;
    	}

运行结果如下：

[1, 2, 3, 4]
    [1, 2, 4, 3]
    [1, 3, 2, 4]
    [1, 3, 4, 2]
    [1, 4, 3, 2]
    [1, 4, 2, 3]
    [2, 1, 3, 4]
    [2, 1, 4, 3]
    [2, 3, 1, 4]
    [2, 3, 4, 1]
    [2, 4, 3, 1]
    [2, 4, 1, 3]
    [3, 2, 1, 4]
    [3, 2, 4, 1]
    [3, 1, 2, 4]
    [3, 1, 4, 2]
    [3, 4, 1, 2]
    [3, 4, 2, 1]
    [4, 2, 3, 1]
    [4, 2, 1, 3]
    [4, 3, 2, 1]
    [4, 3, 1, 2]
    [4, 1, 3, 2]
    [4, 1, 2, 3]

（3）对于N个数，求出这N个数的全排列（数字可以重复）

对于这个问题，我觉得比上面的问题更加容易，只要对每一个数，将其可能的值全部遍历一遍就可以了，这里我们仍然采用递归的方式。

程序：

/**
    	 * 求N个数的全排列，可以重复
    	 */
    	private static int[] arrayfull2={1,2,3};
    	public static void printfull2(int[] array)
    	{
    		assert array!=null && array.length!=0;
    		int[] arr=new int[array.length];
    		printfull2(array,arr,arrayfull2.length,0);
    	
    	}
    	private static void printfull2(int[] array,int[] arr,int n,int cur)
    	{
    		if(cur==n)
    		{
    			System.out.println(Arrays.toString(arr));
    			return;
    		}
    		for(int i=0;i<n;i++)
    		{
    			arr[cur]=array[i];
    			printfull2(arrayfull2,arr,n,cur+1);
    		}
    	}

运行结果：

[1, 1, 1]
    [1, 1, 2]
    [1, 1, 3]
    [1, 2, 1]
    [1, 2, 2]
    [1, 2, 3]
    [1, 3, 1]
    [1, 3, 2]
    [1, 3, 3]
    [2, 1, 1]
    [2, 1, 2]
    [2, 1, 3]
    [2, 2, 1]
    [2, 2, 2]
    [2, 2, 3]
    [2, 3, 1]
    [2, 3, 2]
    [2, 3, 3]
    [3, 1, 1]
    [3, 1, 2]
    [3, 1, 3]
    [3, 2, 1]
    [3, 2, 2]
    [3, 2, 3]
    [3, 3, 1]
    [3, 3, 2]
    [3, 3, 3]

（4）未完待续...