조합을 구하려다 한참을 삽질하고,
결국 로제타 코드에서 큰 도움을 받았다.
( https://rosettacode.org/wiki/Combinations#C.2B.2B )
어찌나 쉽고 심플하게 짜놨는지... 허망~
|
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 <algorithm>
#include <iostream>
#include <string>
void comb(int N, int K)
{
std::string bitmask(K, 1); // K leading 1's
bitmask.resize(N, 0); // N-K trailing 0's
// print integers and permute bitmask
do {
for (int i = 0; i < N; ++i) // [0..N-1] integers
{
if (bitmask[i]) std::cout << " " << i;
}
std::cout << std::endl;
} while (std::prev_permutation(bitmask.begin(), bitmask.end()));
}
int main()
{
comb(5, 3);
}
|
위 코드를 참고하여 써먹기 쉽게 아래처럼 클래스화 시켜 보았다.
|
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82 |
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
using namespace std ;
class CCombination
{
public :
CCombination(vector<int>* vecInt, int r) ;
int getNext(vector<int>* vecCombi) ;
private :
string m_bitmask ;
vector<int>* m_vecInt ;
};
CCombination::CCombination(vector<int>* vecInt, int r)
{
m_vecInt = vecInt ;
m_bitmask.clear() ;
m_bitmask.resize(r, 1) ;
m_bitmask.resize(vecInt->size(), 0) ;
}
int CCombination::getNext(vector<int>* vecCombi)
{
vecCombi->clear() ;
int size = m_bitmask.size() ;
for(int ii = 0; ii < size; ii++)
{
if(m_bitmask[ii])
vecCombi->push_back((*m_vecInt)[ii]) ;
}
if(!prev_permutation(m_bitmask.begin(), m_bitmask.end()))
return 0 ;
return 1 ;
}
int main()
{
vector<int> vecInt ;
vector<int> vecCombi ;
int n = 6 ;
int r = 4 ;
for(int ii = 1; ii <= n; ii++)
vecInt.push_back(ii) ;
CCombination combination(&vecInt, r) ;
int flagBreak ;
while(1)
{
flagBreak = combination.getNext(&vecCombi) ;
for(int ii = 0; ii < r; ii++)
printf("%d ", vecCombi[ii]) ;
printf("\n") ;
if(!flagBreak)
break ;
}
return 1 ;
}
|
뭔가 썩 마음에 들진 않는데 딱히 개선안이 떠오르지 않는다. 허망함 때문인가? ㅋㅋ
시간이 지나면 떠오를 때가 있겠지.
'삽질미학 > C,C++' 카테고리의 다른 글
| 함수 strtok() 의 대안, strsep() (0) | 2018.07.12 |
|---|---|
| [C++] 삼각형 구조의 하향식 길찾기 (0) | 2017.07.18 |
| [C++] 순열 구하기 (0) | 2017.07.12 |
| sleep 을 이용한 타이머 모듈 - RoughTimer (0) | 2017.06.22 |
| [Linux C++] 메시지큐 기반 task 처리하기 (0) | 2017.06.16 |