[순열과 조합] 중복순열

중복순열(permutation with repitition): 서로다른 n개의 원소 중, 중복을 허락하여 r개를 뽑아서 나열한 것

 

기호 π (파이)로 표시

 

핵심

1. 1,2,3,4,5 에서 2개를 뽑는 중복순열은 5π2= 25개

2. 정의에 따라 (1,1),(2,2),(3,3),(4,4),(5,5)는 포함O

3. 중복순열은 순열에서 중복만 허용한 것 이므로 수의 순서가 있음

ex) (1,2), (2,1)는 다름

**중복조합, 조합은 수의 순서가 상관없음

 

4. 백트래킹 기법을 사용하여 구현한다.

(명시적으로 사용되진않았지만 가지치기를하며 수의 조합이 완성되므로 같음)

 

특징: 순열코드와 마찬가지로 함수의 인자는 cnt한개만 갖는다.

 

 

** 순열 코드에서 visited배열 체크 하는 부분만 지워주면 아래 코드랑 결과가 똑같습니다!

 

코드

#include<iostream>
using namespace std;
int arr[5] = { 1,2,3,4,5 };
int multi_per[5];
void dfs(int cnt)
{
    if (cnt == 2) {
        for (int i = 0; i <2 ;i++)
        {
            cout << multi_per[i] << " ";
        }
        cout << endl;
        return;
 
    }
    for (int i = 0; i < 5; i++)
    {
        multi_per[cnt] = arr[i];
        dfs(cnt+1);
    }
}
int main()
{
    dfs(0);
}
 

결과

5π2=25개