[Algorithm] JAVA 중복 순열 알고리즘 (재귀)

안녕하세요. Limky 입니다. 

이번시간에는 경우의 수 중에 순열에 대해서 알아보겠습니다.

헌데, 순열은 순열이지 왜 중복순열이라고 했을까요??

당연 중복순열과 중복되지 않는 순열은 조금 다릅니다.

자기자신을 포함하냐 안하냐에 따라 순열과 중복순열로 구분합니다!

예제를 들어 설명해보겠습니다.

여기 구슬 3개가 있습니다.

1, 2, 3

중복이 없는 순열은 자기자신을 제외하고 모든 경우의 수를 생각하는 것입니다.

3개의 구슬중에 2개를 뽑는 경우의 수는 아래와 같습니다.

1, 2

1, 3

2, 1

2, 3

3, 1

3, 2

입니다. 총 3 X 2 = 6가지 이지요? 

하지만!! 중복순열은 다릅니다. 자기자신을 포함하죠....

똑같이 구슬 3개가 있습니다.

1, 2, 3

중복을 허용해서 뽑으면 아래와 같습니다.

1, 1

1, 2

1, 3

2, 1

2, 2

2, 3

3, 1

3, 2

3, 3

순서를 신경쓰고, 자기 자신을 또 뽑을수도 있습니다. 총 3 X 3 = 9가지 입니다. 

일단 자기자신을 포함하는 경우, 이를 그림으로 도식화 해보면 아래와 같습니다.

느낌이 오시나요....?ㅎㅎ

최초 1, 2, 3 에서 1을 뽑습니다.

다시 1, 2, 3 에서 1을 뽑습니다. 

어라? 2개 뽑았네, 그럼 1, 1 출력

다시 1, 2, 3 으로 돌아와 1이 아닌 2를 뽑습니다.

최초로 뽑은 1은 그대로 가지고 있습니다. 그럼 또 2개를 뽑게되겟죠? 1, 2 출력

다시 1, 2, 3 으로 돌아와 2가 아닌 3을 뽑습니다.

최초로 뽑은 1은 그대로 가지고 있습니다. 그럼 또 3개를 뽑았네요.. 1, 3 출력

이제 1, 2, 3을 모두 체크했어요.

다시 최초로 1을 뽑았던, 1, 2, 3 으로 돌아와 1을 최초로 뽑았을경우 모든 경우의 수를 체크했으니, 

이제 2을 최초로 뽑겠습니다.

최초로 1, 2, 3에서 2를 뽑습니다.

다시, 1, 2, 3 에서 1을 뽑습니다. 

어라? 2개 뽑았네, 여기선 최초에 뽑은 2를 가지고 있습니다. 결국 2, 1을 출력!

다시......

(생략)

느낌이 오시나요???

재귀입니다..이를 소스화 하면 아래와 같습니다.

추가로!!! 자기자신을 포함하기 싫은 경우 check 변수를 통해 자기자신은 제외하고 순열할 수 있도록 만들 수 있습니다. 

이거는 참고하세요 ㅎ 질문은 과감하게 댓글에 고고...

public class RePermutation {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int r = sc.nextInt();
		
		LinkedList
 rCom = new LinkedList();
		int []check = new int[n+1];
		
		System.out.println("자기자신도 포함한, 중복순열!!");
		rePermutation1(n, r, rCom);
		System.out.println("자기자신을 포함하지 않는, 순열!!");
		rePermutation2(n, r, rCom, check);
	}

	private static void rePermutation1(int n, int r, LinkedList rCom) {
		if(rCom.size() == r){
			for(int i : rCom)
			System.out.print(i+"");
			System.out.println();
			return;
		}
		
		for(int i=1; i<=n; i++){
			rCom.add(i);
			rePermutation1(n, r, rCom);
			rCom.removeLast();
		}
		
	}
	
	private static void rePermutation2(int n, int r, LinkedList rCom, int[] check) {
		if(rCom.size() == r){
			for(int i : rCom)
			System.out.print(i+"");
			System.out.println();
			return;
		}
		
		for(int i=1; i<=n; i++){
			if(check[i] == 0){
				check[i] = 1;
				rCom.add(i);
				rePermutation2(n, r, rCom, check);
				check[i] = 0;
				rCom.removeLast();
			}
		}
		
	}

}

결과!!!

3 2

자기자신도 포함한, 중복순열!!

11

12

13

21

22

23

31

32

33

자기자신을 포함하지 않는, 순열!!

12

13

21

23

31

32

알쏭달쏭 재귀ㅎㅎ 재미있는 녀석이네요...