순열과 중복순열, 조합 이해하기

한 배열의 요소가 사과, 오렌지, 레몬 3개인 경우를 예시로 들며 조합, 순열, 중복순열에 대해 알아보자

조합

조합은 순서에 상관없이 조합할 수 있는 모든 경우의 수를 구한다.
주어진 총 요소의 개수 N 보다 조합하려는 개수 R이 클 수 없다. (총 요소 3개 > 2개씩 조합)
조합은 중복을 허용하지 않기에 항상 아래 부등식을 만족해야한다.

R <= N

예를들어 총 개수가 3개인데 만약 4개 씩 조합하거나 것은 말이 안된다.

ex) 과일 총 3개 중 2개로 순서 상관없이 조합할 수 있는 모든 경우의 수

순열

순열은 순서를 부여하여 조합할 수 있는 모든 경우의 수를 구한다.
순서를 바꾸는 경우의 수도 있어서 조합보다 경우의 수가 2배이다.

• 조합과 공통점 : 주어진 총 요소의 개수 N 보다 조합하려는 개수 R이 클 수 없다.
• 조합과 공통점 : 중복을 허용하지 않기에 항상 부등식을 만족해야한다.

R <= N

ex) 과일 총 3개 중 2개로 순서를 부여하여 조합할 수 있는 모든 경우의 수

중복순열

중복순열은 요소의 중복을 허용하고 순서을 부여하여 조합할 수 있는 모든 경우의 수를 구한다.
중복을 허용하기 때문에, 총 요소의 개수 N 보다 조합하려는 개수 R이 클 수 있다.

R >= N || R < N

ex) 과일 총 3개 중 2개로 요소의 중복을 허용하고 순서을 부여하여 조합할 수 있는 모든 경우의 수

코드로 구현한다면? 어떤 방식으로 동작해야할까요?

한번 씩은 모든 요소가 전부 들어가야 하기 떄문에 순회를 반복문, 재귀로 할 수 있다.
=> 조합, 순열, 중복순열의 기본 템플릿 알아보기 (활용할 템블릿)

출처
코드스테이츠