-> struct로 next_permutation 할때는 sort를 할수 없기 때문에 따로 vector 변수 만들어서 진행해야 한다.
: 순열은 순서를 변경하면서 경우의 수를 찾을 때.
조합은 고정된 순서에서 경우의 수를 찾을 때.
: n 개 중에서 순서에 상관없이 몇개를 선택해야 할 경우에 사용함.
필수 조건 : 정렬을 먼저 해야 함.
순열은 순서대로 나열한다라는 의미임.
1) 해당 카운트 숫자에 벡터가 도달시에 추출하도록 함.
2) combi 재귀 함수에서 for문으로 시작 인덱스를 설정해서 벡터에 넣어줌.
3) 그리고 바로 다음 인덱스의 원소로 재귀를 시작
4) 벡터에서 pop_back을 함으로써 완료시키고 다음 원소 집어넣음.
: 중복 발생할 수 없음.
: {1,2,3,4,5} 에서 3개를 뽑았을 때, 오름차순일 때만 추출하라.
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
#include <iostream>
int cnt = 3;
vector<int>res;
void combi(vector<int>&v , int start)
{
if (res.size() == cnt)
{
for (auto iter : res)
{
cout << iter << " ";
}
cout << endl;
}
for (int i = start; i < v.size(); ++i)
{
// 이걸로 하면, 첫인덱스에서 오류 발생함.
//if (v[i] > res.back())
// continue;
res.push_back(v[i]);
// 이렇게 하면 안됨.
//combi(v, start + 1);
// 다음 원소의 값을 넣어야 하므로
combi(v, i + 1);
res.pop_back();
}
return;
}
int main()
{
vector<int> v{ 1,2,3,4,5 };
combi(v, 0);
}
: 반드시 정렬 하자.
next_permutation() 의 3번째 인자는 비교함수임
, pair의 경우, first 끼리 동일할 경우, 다른 조건 처리를 해야 함.
: stl 철저 입문. p.406
-> pair로 비교 처리하기 위해서는 직접 비교 함수 만들자.
--> 이때는 불체크 배열을 사용해서 처리하자.
next_permutaion 할때는 반드시 1차원 벡터로 처리하자.
그리고 1차원 벡터와 pair를 동기화 하면서 진행하자.
: 64C3 : 64개 중에서 3개를 선택할 수 있는 모든 경우의 수를 뜻함.
계산 : 64! / (64- 3)! * 3!
next_permutation
특징
-> 반드시 오른차순으로 정렬된 상태에서 진행해야 함.
1) 오름 차순아닌 상태에서 조합 사용했을 경우.
2) 오름 차순으로 정렬된 상태에서 조합 진행할 경우
-> 1,2,3으로 조합 만들 수 있는 모든 경우의 수가 출력됨
https://programmers.co.kr/learn/courses/30/lessons/42839
: do_while 내부에서 v의 컨테이너들이 조합순으로 변경되는 것이다.
: 서로 다른 n개의 원소를 한 줄로 세우는 것이다.
해당 함수의 특징
1. 오름 차순으로 정렬된 값을 가진 컨테이너만 사용가능하다.
2. 디폴트로 operator < 를 사용한다.
3. 중복을 제외한다.
4. do - while문을 사용하자.
int main()
{
vector<int> v{ 1,2,3 };
do
{
for (auto iter : v)
{
cout << iter << " ";
}
cout << endl;
} while (next_permutation(v.begin(), v.end()));
}
정렬하기 않았을때 , 조합 수가 덜 나온것을 확인할 수 있다.
모든 조합이 나왔다.
: 컨테이너에 들어가 있는 수의 중복을 제외한다는 것이 아니라,
조합으로 나열했을 때 발생하는 경우의 중복을 의미하는 것이다.
: 벡터처럼 동작한다.