首页 > 代码库 > 蓝桥杯——说好的进阶之去重复元素的排列组合

蓝桥杯——说好的进阶之去重复元素的排列组合

将待排列(组合)的数组,先分别统计出种类和个数,然后进行避免重复的排列(组合)。

/* 1,1,2,3的排列组合 去重复
	 * (借此复习排列组合)
	 * 
	 * 1:2 2个1
	 * 2:1 1个2
	 * 3:1 1个3
	 * 
	 * */	
	static int[] iarr = new int[3];//目标序列
	static int[] carr = new int[] { 1, 2, 3 };//3种item
	static int[] used = new int[] { 2, 1, 1 };//每种item有几个可用
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		System.out.println("不重复的排列:");
		dfs(0);
		System.out.println("不重复的组合:(字典序)");
		cal(0, 0);		
		
	}	

	static void dfs(int p) {
		if (p == 3) {
			// find
			for (int i : iarr) {
				System.out.print(i + "");
			}
			System.out.println();
		} else {
			for (int i = 0; i < used.length; i++) {
				if (used[i] > 0) {
					used[i]--;
					iarr[p] = carr[i];
					dfs(p + 1);
					used[i]++;
				}
			}
		}
	}

	static void cal(int p, int j) {
		if (p == 3) {
			// find
			for (int i : iarr) {
				System.out.print(i + "");
			}
			System.out.println();
		} else {
			for (; j < used.length; j++) {
				if (used[j] > 0) {
					used[j]--;
					iarr[p] = carr[j];
					cal(p + 1, j);
					used[j]++;
				}
			}
		}
	}