CODEWITHSUNDEEP
c++algorithmbrute-force
Jēkabs
Jēkabs

Reputation: 17

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

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).

Upvotes: 1

Views: 258

Answers (1)

Jarod42
Jarod42

Reputation: 217398

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

Upvotes: 1

Related Questions