tools_to_remember/combinations.cpp at master · timothyshull/tools_to_remember · GitHub

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
#include <string>
#include <vector>
#include <iostream>

template<typename Item_type>
void combinations1(
        std::vector<Item_type> &&prefix,
        std::vector<Item_type> &&items,
        std::vector<std::vector<Item_type>> &out
)
{
    if (items.empty()) { return; }
    auto t = prefix;
    t.push_back(items[0]);
    out.push_back(t);
    combinations1(std::move(t), {items.begin() + 1, items.end()}, out);
    combinations1(std::move(prefix), {items.begin() + 1, items.end()}, out);
}

template<typename Item_type>
std::vector<std::vector<Item_type>> combinations1(std::vector<Item_type> items)
{
    std::vector<std::vector<Item_type>> out;
    combinations1<Item_type>({}, std::move(items), out);
    return out;
}

void combinations1(std::string &&prefix, std::string &&in_string, std::vector<std::string> &out)
{
    if (in_string.empty()) { return; }
    auto t = prefix + in_string[0];
    out.push_back(t);
    combinations1(std::move(t), in_string.substr(1, std::string::npos), out);
    combinations1(std::move(prefix), in_string.substr(1, std::string::npos), out);
}

std::vector<std::string> combinations1(std::string in_string)
{
    std::vector<std::string> out;
    combinations1("", std::move(in_string), out);
    return out;
}

template<typename Item_type>
void combinations2(
        std::vector<Item_type> &&prefix,
        std::vector<Item_type> &&items,
        std::vector<std::vector<Item_type>> &out
)
{
    out.push_back(prefix); // add check for empty
    for (auto i = 0; i < items.size(); ++i) {
        auto t = prefix;
        t.push_back(items[i]);
        combinations2(std::move(t), {items.begin() + i + 1, items.end()}, out);
    }
}

template<typename Item_type>
std::vector<std::vector<Item_type>> combinations2(std::vector<Item_type> items)
{
    std::vector<std::vector<Item_type>> out;
    combinations2<Item_type>({}, std::move(items), out);
    return out;
}

void combinations2(std::string &&prefix, std::string &&in_string, std::vector<std::string> &out)
{
    out.push_back(prefix);
    for (std::size_t i{0}; i < in_string.size(); ++i) {
        combinations2(prefix + in_string[i], in_string.substr(i + 1, std::string::npos), out);
    }
}

std::vector<std::string> combinations2(std::string in_string)
{
    std::vector<std::string> out;
    combinations2("", std::move(in_string), out);
    return out;
}

int main()
{
    auto out = combinations1("abc");
    for (const auto &s : out) {
        std::cout << s << "\n";
    }

    std::cout << "\n";

    auto out2 = combinations2("abcd");
    for (const auto &s : out2) {
        std::cout << s << "\n";
    }

    std::cout << "\n";

    auto t = std::vector<int>({1, 2, 3});
    auto out3 = combinations1(t);
    for (const auto &v : out3) {
        for (const auto &i : v) {
            std::cout << i << " ";
        }
        std::cout << "\n";
    }

    std::cout << "\n";

    auto out4 = combinations2(t);
    for (const auto &v : out4) {
        for (const auto &i : v) {
            std::cout << i << " ";
        }
        std::cout << "\n";
    }
    return 0;
}