중복순열과 뭐가 다르지?

중복순열은 서로다른 n개에서 중복을 허용하여 r개를 뽑는것이다. 따라서 n^r 의 경우가 나온다.
예를 들어 500원, 100원, 50원, 10원 동전이 충분히 많이 있고, 10개를 뽑아서 만들수있는 총금액의 경우의 수는 4^10이다.
하지만, 같은 것을 포함한 순열은 그냥 [1, 1, 2, 3, 5, 5, 5] 를 순열하는 것이다. 따라서 경우의 수는 (7!)/(2! * 3!) 이다.

구현 방법 2가지

Next Permutaion 이용

next Permutation은 어떠한 순열의 결과(그냥 수열)에서 다름의 순열 경우를 딱 하나 배출하는 것을 말한다.

package ssafy.agorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class NextPermutationTest {
	static int N;
	static int R;
	static int[] input;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		input = new int[N];
		
		for (int i = 0; i < N; i++) {
			input[i] = sc.nextInt();
		}
		R = sc.nextInt();
		//오름차순정렬 필요
		Arrays.sort(input);
		
		do {
			System.out.println(Arrays.toString(input));
		}while(nextPermutation(input));
	}
	
	static boolean nextPermutation(int[] arr) {//현상태의 순열에서 사전식 다음 순열 생성후 다음순열 존재하면 true
		//step1 뒤쪽부터 탐색하며 꼭대기(i) 찾기 -> 교환위치(i-1)찾기 위함
		int i = N-1;
		while(i>0 && arr[i-1]>=arr[i]) --i;
		if(i==0) {
			//가장 큰 순열이라 더이상 다음 순열이 없다
			return false;
		}
		//step2 교환자리인 i-1의 값과 교환할 한단계 큰 수를 뒤쪽부터 찾기
		int j = N-1;
		while(arr[i-1] >= arr[j]) --j;
		
		//step3 i-1과 j의 값 교환
		swap(arr, i-1, j);
		
		//step4 i-1자리의 한단계 큰 수로 변화를 줬으니, i꼭대기 위치부터 맨 뒤까지 가장 작은 수를 만듬(오름차순정렬)
		int k = N-1;
		while(i<k) swap(arr, i++, k--);
		return true;
	}

	private static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}

number_counts를 이용한 dfs

[1, 1, 2, 3, 5, 5, 5]를 number_counts하면 {1:2, 2:1, 3:1, 5:3} 형태가 되고, dfs에서 for(number_counts.keys())를 한다. 그리고 다음 dfs를 가기전에 해당하는 key의 value를 하나 줄이고, dfs다음엔 다시 value를 원상복귀시킨다.

package ssafy.agorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class PermutationWithSameThing {
	
	private static BufferedReader br;
	private static LinkedHashMap<Integer, Integer> number_counts;
	private static int n;
	private static int[] perm;
	private static int perm_count;

	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		System.out.println("같은것을 포함한 수열을 적어주세요. 수열의 결과를 출력할게요.");
		number_counts = new LinkedHashMap<Integer, Integer>();
		n = 0;
		StringTokenizer st = new StringTokenizer(br.readLine());
		while(st.hasMoreTokens()) {
			n++;
			int num = Integer.parseInt(st.nextToken());
			if(!number_counts.containsKey(num))
				number_counts.put(num, 0);
			number_counts.replace(num, number_counts.get(num)+1);
		}
		
		//필요시 정렬을 하고 dfs돌림
		perm = new int[n];
		dfs(0);
		System.out.println(perm_count);
	}

	private static void dfs(int count) {
		if(count == n) {
			System.out.println(Arrays.toString(perm));
			perm_count++;
			
			return;
		}
		
		Iterator<Map.Entry<Integer, Integer>> it = number_counts.entrySet().iterator();
		while (it.hasNext()) {
			Map.Entry<java.lang.Integer, java.lang.Integer> entry = (Map.Entry<java.lang.Integer, java.lang.Integer>) it
					.next();
			if(entry.getValue() != 0) {
				entry.setValue(entry.getValue() - 1);
				perm[count] = entry.getKey();
				dfs(count+1);
				entry.setValue(entry.getValue() + 1);
			}
		}
		
	}
}
/*입력
* 1 2 2 5
* 출력
[1, 2, 2, 5]
[1, 2, 5, 2]
[1, 5, 2, 2]
[2, 1, 2, 5]
[2, 1, 5, 2]
[2, 2, 1, 5]
[2, 2, 5, 1]
[2, 5, 1, 2]
[2, 5, 2, 1]
[5, 1, 2, 2]
[5, 2, 1, 2]
[5, 2, 2, 1]
12
*/