안녕하세요. 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
알쏭달쏭 재귀ㅎㅎ 재미있는 녀석이네요...
'Algorithm > Algorithm' 카테고리의 다른 글
[알고리즘] java로 순열, 중복순열, 조합, 중복조합 구하기 (0) | 2019.04.07 |
---|---|
[알고리즘] 스택2개로 큐 구현하기 (3) | 2019.04.05 |
[Algorithm] SW Expert Academy - 1953. [모의 SW 역량테스트] 탈주범 검거 해설 (0) | 2019.03.24 |
[알고리즘] 다익스트라 최단거리 알고리즘(Dijkstra) (1) | 2018.12.25 |
[Algorithm] JAVA로 중복이 없고, 순서도 없는 조합(Combination) 구하기! (4) | 2018.06.13 |
댓글