Efficient coding help

Question

I am currently writing code in C++ to find all possible permutations of 6 integers and store the best permutation (i.e. the one whose total is closest to a given value).

I am trying to write this code as efficiently as possible and would apreciate any advice or examples.

I was considering storing the integers in an array and performing the permutations using pointers within a loop. Is this a good approach?

Answer 1

Take a look at this excellent post @ Coding the Wheel: Exhaustively Enumerating Combinations and Permutations in Code. It has full code and was written by a fellow SO'r, it should be enough to get you on the right track.

Answer 2

They already thought of this one for you:

#include <algorithm>

int ra[6] = { 1, 2, 3, 4, 5, 6 };

do {
    // whatever
} while (std::next_permutation(ra, ra+6));

Note that the elements have to start in increasing order (by comparison via operator<), or else the loop will terminate before you've seen every permutation. See http://www.sgi.com/tech/stl/next_permutation.html for details.

It probably doesn't give the fastest runtime possible, because at each step it has to examine the array to work out what to change. But it's certainly the most efficient in programmer effort, and without knowing the compiler and platform it's not really possible to micro-optimise the nested loop approaches anyway.

Answer 3

Assuming duplicated numbers aren't an issue, there are n! perumations of n integers (taken n at a time). So no matter what you do, your algorithm is going to have factorial time behavior ( O (n^n) ).

In other words, when n gets big, it will be slow. Sorry.

There are actually algorithms to do this on the permutation wikipedia page.

Answer 4

I was considering storing the integers in an array and performing the permutations using pointers within a loop. Is this a good approach?

No, it's not really a good approach. Instead of swapping pointers to items in the array, just swap the items in the array instead. The pointers would just be an extra step of indirection without any real purpose.