Brute force C++, n numbers out of n*3 numbers

Question

I want to print out all possible n number subsets out of given n*3 numbers (random numbers within int). We also assume that n is small enough to do brute force. And for simplicity I assume n = 7.

P.S. We do not take number in the same position twice. So, if I have n*3 numbers like: 1,2,3,4,5,6 etc. n*3 I cannot use "1" twice and 1 1 2 3 4 5 6 is invalid way to ttake n-numbers.

But if I have n*3 numbers like 1 1 2 2 3 3 4 4 5 5 6 6 7 7 etc. then I can use "1" twice and one way to choose 7-numbers is 1 1 2 3 4 5 6.

I can do it in stupid way like this assuming n = 7.

int n = 7;
int n3 = 21;
for (int j = 0; j < n3; j++) {
        for (int k = 0; k < n3; k++) {
            if (j == k) {
                break;
            }
            for (int l = 0; l < n3; l++) {
                if ((l == k) || (j == l)) {
                    break;
                }
                for (int m = 0; m < n3; m++) {
                    if ((m == l) || (m == k) || (m == j)) {
                        break;
                    }
                  ... etc.

How can this can be rewritten using some data structures?

I am at school and I have just started learning algorithms. I have basic C++ knowledge and some basic data structures knowledge (array, vector, queue, set, map).

I think the technique you are looking for is not a data structure, but *recursion*. — john, Sep 05 '22 at 09:01
Not sure what is your expected result... Do you want `n` random distinct numbers? — Jarod42, Sep 05 '22 at 09:10
This is a bit unclear. If you have N*3 numbers, every permutation of them has N*3 elements. Do you want to select N elements from N*3 given elements or do you want to do something else? — molbdnilo, Sep 05 '22 at 09:19
@molbdnilo yes I want to take n elements in all possible ways out of n*3 given random numbers. — Jēkabs, Sep 05 '22 at 09:33
A _combination_ usually means a subset, so, for example, `(1, 3, 15)` would be the same as `(15, 1, 3)` and `(3, 15, 1)` and three other permutations (i.e., arrangings) of the same items. If you really mean combinations, you need to discard all but one representation of each `n`-element subset. But your sketch of code looks like an attempt to produce _every possible_ arrangement of each `n` _different_ numbers. Which one do you really need? — CiaPan, Sep 05 '22 at 09:45
I have not studied combinations yet in school so I misuse this term. I need n-element subset from n*3 givenelements. — Jēkabs, Sep 05 '22 at 09:58
Okay, so after your recent edits to the question I understand you want to print all subsets of given size (`n`) from a given array of integer number, without permuting or repeating input items; however, if the input array contains duplicates, they should also appear in the output. So, for example, 2-element subsets from `[1, 2, 1, 4]` will include `(1,2)` and `(2,1)` and `(1,1)` and `(1,4)` twice (with two 'different' `1`s), but not `(4,1)`. Am I right? — CiaPan, Sep 05 '22 at 10:05
Okay then, I suppose the @john 's suggestion from the [very first comment](https://stackoverflow.com/questions/73606860/brute-force-help-c-n-numbers-out-of-n3-numbers#comment129981875_73606860) is a solution you need. To be honest, recursion looks a bit too robust for beginners, much less intuitive than nested loops, but it is easily scallable for differerent values of limiting parameters (like an input array's length and the size of generated subsets). — CiaPan, Sep 05 '22 at 10:20
Related to [all-combinations-of-k-elements-out-of-n](https://stackoverflow.com/questions/5095407/all-combinations-of-k-elements-out-of-n). — Jarod42, Sep 05 '22 at 10:55

score 1 · Answer 1 · answered Sep 05 '22 at 10:52

Take n elements from m can be done with std::next_permutation:

template <typename F, typename T>
void CnP(F f, const std::vector<T>& elems, std::size_t n)
{
    std::vector<bool> v(n, true);
    v.resize(elems.size(), false); // { true, .., true, false, .., false}

    do {
        f(elems, v);
    } while (std::prev_permutation(v.begin(), v.end()));
}

Demo

Brute force C++, n numbers out of n*3 numbers

1 Answers1