How to generate all possible combinations?

Example combinations without repetition:
Check-in:
4
Check out:
1,2,3,4
12,13,14,23,24,34
123,124,134,234
1234

How next_permutation used in this case?
Assuming the numbers are stored in a std::vector (or other container with bidirectional iterators) e.g. std::vector Vect = {1,2,3,4}; you can simply call std::next_permutation( Vect.begin(), Vect.end() ); to rearrange the elements to their 'next' (lexicographicaly, Google this word if you want to know more about how it works otherwise you can just assume "by magic") permutation. There will be N! (N factorial) permutations where N is the number of elements.
I probably wouldn't use next_permutation here, but if you must some indirection is called for:

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

std::string as_string(const std::vector<char>& vals, const std::vector<bool>& pattern)
{
    std::string result;

    for (unsigned i = 0; i < pattern.size(); ++i)
        if (pattern[i])
            result += vals[i];

    return result;
}

// Note: Only good for values greater than 0 and less than 10.
std::vector<std::string> unique_combinations(unsigned val)
{
    std::vector<std::string> result;

    std::vector<char> vals(val);
    std::iota(vals.begin(), vals.end(), '1');

    std::vector<bool> pattern(vals.size(), false);

    for (auto it = pattern.rbegin(); it != pattern.rend(); ++it)
    {
        *it = true;

        do
        {
            result.emplace_back(as_string(vals, pattern));
        } while (std::next_permutation(pattern.begin(), pattern.end()));
    }

    return result;
}

int main()
{
    for (unsigned i = 1; i < 6; ++i)
    {

        auto combos = unique_combinations(i);
 
        // to present them in the same order as the sample
        auto ordering = [](const std::string& a, const std::string& b)
        {
            if (a.size() < b.size())
                return true;

            if (a.size() > b.size())
                return false;

            return a < b;
        };

        std::sort(combos.begin(), combos.end(), ordering);

        auto combo = combos.begin();
        while (combo != combos.end())
        {
            unsigned size = combo->size();
            std::cout << *combo;

            while (++combo != combos.end() && combo->size() == size)
                std::cout << ", " << *combo;
            
            std::cout << '\n';
        }

        std::cout << '\n';
    }
}


http://ideone.com/6gKGca
Topic archived. No new replies allowed.