순열 nPr

① 순열

   : 순서O, 중복X ('중복'은 자기자신 포함 여부를 의미)

 

     예) 1,2,3,4 중 2개 뽑는 경우

           (1,2) (1,3) (1,4) (2,1) (2,3) (2,4) (3,1) (3,2) (3,4) (4,1) (4,2) (4,3)

 

/*
N : 총 숫자 개수(num.length)
R : 숫자 중에서 뽑는 개수 (nPr에서 r을 의미)
int[] num : 숫자 집합
boolean[] checked : num[]의 숫자 사용 여부
List<Integer> ans : 순열(nPr) 결과를 담는 리스트

1. 숫자 사용X
   1) 사용표시(checked[i]=true), 결과리스트에 추가, 재귀
   2) 사용표시 원상복귀(checked[i]=false), 결과리스트에서 삭제, i++
2. ans.size()==M 이면 출력 후 종료
*/

private static void permutation(int[] num, boolean[] checked, List<Integer> ans){
	if(ans.size() == R){
		for(int i=0; i<ans.size(); i++){
			System.out.print(ans.get(i)+" ");
		}
		System.out.println();
		return;
	}

	for(int i=0; i<N; i++){
		if(!checked[i]){
			checked[i] = true;
			ans.add(num[i]);
			permutation(num, checked, ans);

			checked[i] = false;
			ans.remove(ans.size()-1);
		}
	}
}

 

 

 

 

② 중복 순열 

   : 순서O, 중복O

 

     예) 1,2,3,4 중 2개 뽑는 경우

           (1,1) (1,2) (1,3) (1,4) (2,1) (2,2) (2,3) (2,4) (3,1) (3,2) (3,3) (3,4) (4,1) (4,2) (4,3) (4,4)

 

/*
N : 총 숫자 개수(num.length)
R : 숫자 중에서 뽑는 개수 (nPr에서 r을 의미)
int[] num : 숫자 집합
List<Integer> ans : 순열(nPr) 결과를 담는 리스트

1. 결과리스트에 num[i] 추가
2. 1) 재귀 (1의 결과를 가지고 계속해서 결과리스트에 num[i]를 추가해줌)
   2) 추가한 num[i]를 결과리스트에서 제거 - i++
3. ans.size()==M 이면 출력 후 종료
*/

private static void permutation(int[] num, List<Integer> ans){
	if(ans.size() == R){
		for(int i=0; i<ans.size(); i++){
			System.out.print(ans.get(i)+" ");
		}
		System.out.println();
		return;
	}

	for(int i=0; i<N; i++){
		ans.add(num[i]);
		permutation(num, ans);
		ans.remove(ans.size()-1);
	}
}