2
\$\begingroup\$

I have to find a method (using backtracking) to list all possible combinations, in lexicographical order,of k numbers out of the interval [1,n].. duplicates are not allowed.
i.e: input: 5 3
output:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

I know using namespace std; is bad practice, but that's the way we've been taught to write code, we always use iostream library and sometimes cmath iomanip and string, so the point is that I don't have a lot of knowledge in C++.. All I would like is a faster method than the one that I implemented, and if you can, don't use advanced syntax.. I understand that "advanced" might mean different things for different people, but maybe the code bellow will give you an uderstanding of the level of C++ knowledge I have

#include <iostream>
using namespace std;
int sol[20], n , el_maxim;
void display()
{
    for (int i = 0; i < n; i++)
        cout << sol[i] << " ";
    cout << endl;
}
int okay()
{
    for (int i = 0; i < n - 1; i++)
        if (sol[i] >= sol[i + 1])
            return 0;
    return 1;
}
void bkt(int poz)
{
    if (poz == n)
    {
        okay();
        if (okay() == 1)
            display();
    }
    else
        for (int i = 1; i <= el_maxim; i++)
        {
            sol[poz] = i;
            bkt(poz + 1);
        }
}
int main()
{
    cin >> el_maxim >> n;
    bkt(0);
    return 0;
}
\$\endgroup\$
1
\$\begingroup\$

Preface:

if you can, don't use advanced syntax

I understand why you say this, but do not shy away from strange looking syntax. When you encounter something you cannot read, take the time to lookup what the syntax does (even experienced developers do this). The weird looking syntax may be doing useful stuff. And after you understand what's going on, the syntax usually doesn't look weird anymore.

Another algorithm:

First off, for a beginner, this is a great start. It's very simple code which is good.

If you want faster code, the first thing to do is make sure your general approach is reasonable or better yet optimal. Your algorithm generates all possible sets of length K with elements from {1,2,...N} and then checks if the sets are sorted. Note that I have used N for the size of the input set and K for the size of the combinations -- this is a convention I have seen in many places but is different from your code.

There are $$K^N$$ possible sets of length K from a set of N objects. For the same set of N objects, there are $$\frac{N!}{K!(N-K)!}$$ combinations. Since the combinations are a subset of the possible sets, they are a smaller set and in many cases they are a much smaller set. Interestingly there are some non integer solutions for K^N < (N choose K) e.g. K = 0.5 and N = 1.5. maybe someone else can shed some light on that. But they key takeaway is that only generating combinations will be a lot faster.

How can you only generate combinations? There's more than one way to do this, but I will describe one way.

Consider the n=5, k=3 example. The set of numbers to maybe print is 1,2,3,4,5, and the set of numbers to definitely print is {} (empty set). I'll simplify this as ({}, {1,2,3,4,5}). Some of the combinations have 1 and some don't. So we now have to consider both the possibilities ({1},{2,3,4,5}) and ({}, {2,3,4,5}). We repeat this recursively, and when we have a set of things of size el_maxim (or, by convention, k), we print. In psuedo-code:

void recurse(int indexK, int indexN) {
    if (indexK == K) {
        print(result);
        return;
    }

    // "if there more slots to fill than numbers to fill them"
    // could also say `if (indexN == N)` ... correct but slower
    if (N - indexN < K - indexK) {
        return;
    }

    result[indexK] = indexN;

    recurse(indexK + 1, indexN + 1);
    recurse(indexK, indexN + 1);
}

I encourage you to try getting this function to compile and then benchmarking to make sure you see the speedup you would expect. You'll have to try a few different values of N and K. For some inputs <10, the improved algorithm should run 1000s of times faster!

Review of your code:

Since my main advice is to use a better algorithm, I haven't given any specific comments on your code. I'll do that here:

Your program should be based around a function that can generate combinations. The function should take N and K as input, and it should return all the combinations. Something like this:

/// This function generates all combinations of integers {1,2,...,N}
/// @param N    the size of the set
/// @param K    the size of the combinations
ResultType generateCombinations(int N, int K) { ... }

Then your main function should call generateCombinations. This has several advantages over your method:

  • The compiler will make sure you set all the inputs. In your version, if you forget to set a global variable, then you'll get the wrong answer.

  • You have a convenient place to put a big comment about what the function does. The comment I've placed above is in Doxygen's format so you can generate documentation from your comments. It also looks pretty good in my opinion.

  • You can easily call the function in several places.

  • You don't have to worry about name collisions.

  • The compiler can optimize arguments better than global variables. In general, compilers are really good with functional code and not so good with code that uses lots of memory.

  • I could go on but I think you get the point.


Separate printing the combinations from generating the combinations. You've sort of done that with the display function, but not really since anyone who calls bkt is forced to print the result. There are two main ways to do this. The first way is to return a big data structure, and then print it:

std::vector<std::vector<int>> generateCombinations(int N, int K) { ... }

for (auto& vec : genCombinations(5, 3)) { print(vec); }

This way is pretty easy/simple. The downside is it uses a lot of memory.

The second way is to accept an argument that says what to do with each result:

void genCombinations(int N, int K, std::function<void(vector<int>&)> func) { ... }

genCombinations(5, 3, [](auto& vec) { print(vec); });

This is probably harder to read for many people, but it saves a large amount of memory in this case!


Your names are a little weird. el_maxim instead of maximum_element or N as dictated by convention. n instead of num_elements or K per the convention. Also bkt and okay seem like they were chosen because they are short rather than because they are good descriptions of what they do.


okay();
if (okay() == 1)

Is this intended?

P.S.

I encourage you to rewrite and post another code review using a faster algorithm! You may get more comments on your code rather than on your approach.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Of course it's too low. You're building all the sequences of n numbers ≤ el_maxim and then display only those increasing. So, for m=5 and n=3 you print ten sequences out of 125, but you build and check all those 125.

Build them incrementally: once you've set the first array element to 1 you only need to iterate from 2 to e_m - (n - 2) for the second element; and once that latter reaches 3, then the third element only goes from 4 to e_m - (n - 3), etc. And you wouldn't need to check them (which btw you currently do twice, first time discarding the result of the check).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I don't know how to generate them directly, could you share a code snippet please? I tried this:ideone.com/K2w9zr \$\endgroup\$ – nultype Apr 27 at 14:48
  • 1
    \$\begingroup\$ nevermind, I managed, thanks!! \$\endgroup\$ – nultype Apr 27 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.