중복순열(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배열 체크 하는 부분만 지워주면 아래 코드랑 결과가 똑같습니다!

 

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#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);
}
 
 cs
결과
5π2=25개

 

 

 

 

저작자표시

'알고리즘 > 순열과 조합' 카테고리의 다른 글

[순열과 조합] 중복조합  (0) 2020.02.07
[순열과 조합] 조합  (0) 2020.02.07
[순열과 조합] 순열  (0) 2020.02.07

중복조합(combination with repitition) : 서로 다른 n개의 원소 중, 중복을 허락하여 r개를 뽑는 것



기호 H로 표시



핵심

1. 1,2,3,4,5중 2개를 뽑는 중복조합의 수는 2+(5-1)C2=15개

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

3. 중복조합은 조합에서 중복만 허용한 것이므로 똑같이 수의 순서는상관X

ex) (1,2)와 (2,1)는 같음

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

(순열코드처럼 명시적으로 백트래킹기법을 사용하진않았지만, 가지치기를하며 진행되므로 같음)


특징: 조합에서 중복만 허용하므로 조합 코드와 거의 똑같다.

(dfs함수내부에서, 재귀를 타고 넘어가는 dfs함수의 첫번째 인자가 i+1일 때 조합, i일때 중복조합)


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;
int arr[5] = { 1,2,3,4,5 };
int combi[5];
void dfs(int index,int cnt)
{
    if (cnt == 2)
    {
        for (int i = 0; i < 2; i++)
        {
            cout << combi[i] << " ";
        }cout << endl;
        return;
    }
    for (int i = index; i < 5; i++)
    {
        combi[cnt] = arr[i];
        dfs(i, cnt + 1);
    }
}
int main()
{
    dfs(0,0);
}
cs



결과
5H2=15개






저작자표시

'알고리즘 > 순열과 조합' 카테고리의 다른 글

[순열과 조합] 중복순열  (0) 2020.02.07
[순열과 조합] 조합  (0) 2020.02.07
[순열과 조합] 순열  (0) 2020.02.07

조합(combination) : 서로 다른 n개의 원소 중, 순서에 상관없이 r개를 선택 하는 것


기호 C로 표시


핵심

1. 1,2,3,4 중 2개를 뽑는 조합은 4C2= 4*3*2*1 / 2*1 = 12개

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

3. 조합은 수의 순서가 상관없으므로 (1,2)와 (2,1)는 같음

*순열: 순서가 상관 있으므로 (1,2)와 (2,1)는 다름

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

(순열코드처럼 명시적으로 백트래킹기법을 사용하진않았지만, 가지치기를하며 진행되므로 같음)


구현: 1,2,3,4중 2개를 뽑는 조합


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;
int arr[4] = { 1,2,3,4};
int combi[4];
void dfs(int index,int cnt)
{
    if (cnt == 2)
    {
        for (int i = 0; i < 2; i++)
        {
            cout << combi[i] << " ";
        }cout << endl;
        return;
    }
    for (int i = index; i < 4; i++)
    {
        combi[cnt] = arr[i];
        dfs(i+1, cnt + 1);
    }
}
int main()
{
    dfs(0,0);
}
cs



결과
4C2=6개




저작자표시

'알고리즘 > 순열과 조합' 카테고리의 다른 글

[순열과 조합] 중복순열  (0) 2020.02.07
[순열과 조합] 중복조합  (0) 2020.02.07
[순열과 조합] 순열  (0) 2020.02.07

순열(permutation) :  서로 다른 n개의 원소 중에서, r개를 뽑아서 나열한 것


기호 P로 표시 




핵심

1. 1 2 3 4 에서 2개를뽑는 순열은 4P2= 4*3=12개

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

3. 순열은 수의 순서가 상관이 있으므로, (1,2)과 (2,1)는 다름.

*조합: 순서가 상관 없으므로 (1,2)과 (2,1)는 같음 

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



구현: 1,2,3,4 중 2개를 뽑는 순열


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<vector>
using namespace std;
int arr[4] = { 1,2,3,4};
vector<int>v;
bool check[4];
void dfs(int cnt)
{
    if (cnt == 2) {
        for (int i = 0; i < v.size(); i++)
        {
            cout << v[i] << " ";
        }
        cout << endl;
        return;
 
    }
    for (int i = 0; i < 4; i++)
    {
        if (check[i] == true)continue;
        check[i] = true;
        v.push_back(arr[i]);
        dfs(cnt + 1);
        v.pop_back();
        check[i] = false;
    }
}
int main()
{
    dfs(0);
}
cs


결과
4P2= 12개





저작자표시

'알고리즘 > 순열과 조합' 카테고리의 다른 글

[순열과 조합] 중복순열  (0) 2020.02.07
[순열과 조합] 중복조합  (0) 2020.02.07
[순열과 조합] 조합  (0) 2020.02.07

+ Recent posts

티스토리툴바