-
Notifications
You must be signed in to change notification settings - Fork 36
/
strtk_nth_combination_example.cpp
155 lines (123 loc) · 4.82 KB
/
strtk_nth_combination_example.cpp
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
/*
*****************************************************************
* String Toolkit Library *
* *
* N'th Combination Example *
* Author: Arash Partow (2002-2020) *
* URL: http://www.partow.net/programming/strtk/index.html *
* *
* Copyright notice: *
* Free use of the String Toolkit Library is permitted under the *
* guidelines and in accordance with the most current version of *
* the MIT License. *
* http://www.opensource.org/licenses/MIT *
* *
*****************************************************************
*/
/*
Description: The objective of this example is to generate the
n'th combination for the purpose of n-choose-k.
Example: {ABCDEF}-choose-4
# Index Combination
0000 | 0123 | ABCD
0001 | 0124 | ABCE
0002 | 0125 | ABCF
0003 | 0134 | ABDE
0004 | 0135 | ABDF
0005 | 0145 | ABEF
0006 | 0234 | ACDE
0007 | 0235 | ACDF
0008 | 0245 | ACEF
0009 | 0345 | ADEF
0010 | 1234 | BCDE
0011 | 1235 | BCDF
0012 | 1245 | BCEF
0013 | 1345 | BDEF
0014 | 2345 | CDEF
Note: This technique is far more efficient and optimal than calling
strtk::next_combination routine n-times.
*/
#include <cstddef>
#include <iostream>
#include <vector>
#include "strtk.hpp"
// n choose k
static const std::size_t n = 6;
static const std::size_t k = 4;
void nth_combination_example01()
{
typedef std::vector<unsigned char> list_type;
list_type char_list;
strtk::iota(char_list,n,static_cast<unsigned char>('A'));
const std::size_t combination_count = static_cast<std::size_t>(strtk::n_choose_k(n,k));
for (std::size_t i = 0; i < combination_count; ++i)
{
std::vector<unsigned int> index_list;
strtk::nth_combination_sequence(i, n, k, std::back_inserter(index_list));
list_type nth_combination;
strtk::nth_combination_sequence(i,
k,
char_list.begin(), char_list.end(),
std::back_inserter(nth_combination));
std::cout << strtk::text::right_align(4, '0', i) << " | "
<< strtk::join("", index_list) << " | "
<< strtk::join("", nth_combination) << std::endl;
}
std::cout << std::endl << std::endl;
}
void nth_combination_example02()
{
typedef std::vector<unsigned char> list_type;
list_type char_list;
list_type next_comb_list;
strtk::iota(char_list,n,static_cast<unsigned char>('A'));
next_comb_list = char_list;
const std::size_t combination_count = static_cast<std::size_t>(strtk::n_choose_k(n,k));
for (std::size_t i = 0; i < combination_count; ++i)
{
std::vector<unsigned int> index_list;
strtk::nth_combination_sequence(i, n, k, std::back_inserter(index_list));
list_type nth_combination;
strtk::nth_combination_sequence(i,
k,
char_list.begin(), char_list.end(),
std::back_inserter(nth_combination));
std::cout << strtk::text::right_align(4, '0', i) << " | "
<< strtk::join("", index_list) << " | "
<< strtk::join("", nth_combination) << " | "
<< strtk::join("", next_comb_list) << std::endl;
strtk::next_combination(next_comb_list.begin(),
next_comb_list.begin() + k,
next_comb_list.end());
}
std::cout << std::endl << std::endl;
}
void nth_combination_example03()
{
typedef std::vector<unsigned char> list_type;
list_type char_list;
strtk::iota(char_list,n,static_cast<unsigned char>('A'));
// Obtain 5th combination
list_type nth_combination;
strtk::nth_combination_sequence(4,
k,
char_list.begin(), char_list.end(),
std::back_inserter(nth_combination));
//Iterate beginning from 5th combination to the end
std::size_t i = 4;
do
{
std::cout << strtk::text::right_align(4, '0', i++) << " | "
<< strtk::join("", nth_combination) << std::endl;
}
while (strtk::next_combination(nth_combination.begin(),
nth_combination.begin() + k,
nth_combination.end()));
}
int main()
{
nth_combination_example01();
nth_combination_example02();
nth_combination_example03();
return 0;
}