algorithm-examples/cpp-algorithm/src/math/combination.h at main · codejsha/algorithm-examples · 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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#ifndef CPP_ALGORITHM_COMBINATION_H
#define CPP_ALGORITHM_COMBINATION_H

#include <string>
#include <vector>

namespace Combination
{
    /**
     * \brief Generate all possible combinations of integer elements in a sequence.
     * \param seq sequence of integer elements
     * \param k size of the subset
     * \return combinations of integer elements
     */
    std::vector<std::vector<int>> GenerateCombination(
        const std::vector<int>& seq,
        int k);

    /**
     * \brief Generate all possible combinations of string elements in a sequence.
     * \param seq sequence of string elements
     * \param k size of the subset
     * \return combinations of string elements
     */
    std::vector<std::vector<std::string>> GenerateCombination(
        const std::vector<std::string>& seq,
        int k);

    /**
     * \brief Generate all possible combinations of chars in a string.
     * \param str given string
     * \param k size of the subset
     * \return combinations of chars in a string
     */
    std::vector<std::string> GenerateCombination(
        const std::string& str,
        int k);
}

// ----------------------------------------------------------------------------
inline void GenerateCombinationHelper(
    const std::vector<int>& seq,
    const int k, std::vector<std::vector<int>>& result,
    std::vector<int>& current,
    const int start)
{
    if (static_cast<int>(current.size()) == k)
    {
        result.push_back(current);
        return;
    }

    for (int i = start; i < static_cast<int>(seq.size()); ++i)
    {
        current.push_back(seq[i]);
        GenerateCombinationHelper(seq, k, result, current, i + 1);
        current.pop_back();
    }
}

// ----------------------------------------------------------------------------
inline std::vector<std::vector<int>> Combination::GenerateCombination(
    const std::vector<int>& seq,
    const int k)
{
    std::vector<std::vector<int>> result;
    std::vector<int> combination;
    GenerateCombinationHelper(seq, k, result, combination, 0);
    return result;
}

// ----------------------------------------------------------------------------
inline void GenerateCombinationHelper(
    const std::vector<std::string>& seq,
    const int k,
    std::vector<std::vector<std::string>>& result,
    std::vector<std::string>& current,
    const int start)
{
    if (static_cast<int>(current.size()) == k)
    {
        result.push_back(current);
        return;
    }
    for (int i = start; i < static_cast<int>(seq.size()); ++i)
    {
        current.push_back(seq[i]);
        GenerateCombinationHelper(seq, k, result, current, i + 1);
        current.pop_back();
    }
}

// ----------------------------------------------------------------------------
inline std::vector<std::vector<std::string>> Combination::GenerateCombination(
    const std::vector<std::string>& seq,
    const int k)
{
    std::vector<std::vector<std::string>> result;
    std::vector<std::string> combination;
    GenerateCombinationHelper(seq, k, result, combination, 0);
    return result;
}

// ----------------------------------------------------------------------------
inline void GenerateCombinationHelper(
    const std::string& str,
    const int k, std::vector<std::string>& result,
    const std::string& current,
    const int start)
{
    if (k == 0)
    {
        result.push_back(current);
        return;
    }

    for (int i = start; i <= static_cast<int>(str.length()) - k; ++i)
    {
        std::string new_current = current + str[i];
        GenerateCombinationHelper(str, k - 1, result, new_current, i + 1);
    }
}

// ----------------------------------------------------------------------------
inline std::vector<std::string> Combination::GenerateCombination(
    const std::string& str,
    const int k)
{
    std::vector<std::string> result;
    const std::string combination;
    GenerateCombinationHelper(str, k, result, combination, 0);
    return result;
}

#endif