This is codeEval challenge to count the number of chains possible to make with beads holding numbers. Constraint is sum of the consecutive beads of chain should be a prime number.
The standard algorithm std::next_permutation is very resource oriented in this case, so dropped the idea to use that one.
I created a simple algorithm. If the input number is 4, we have to consider numbers 1-4. If we take permutations of 2-4 and append 1 to all resultant permutations we will get all possible necklaces without repetition using numbers 1-4. The above stated is the basic approach.
By considering, beads should be placed in chain to satisfy the prime number constraints at least, they should be in even number after odd number order or vice versa. Since I am always starting with 1, I have chosen the odd number before even number order.
My solution is not yet accepted because of performance constraints in that it should output answers for 5 input even numbers within 10 seconds. On my Intel dual core system by using O3 compiler optimization, it is taking 35 seconds and without optimization in range of 180-200 seconds for the number 18. For all other numbers up to 16 it will execute before 10 seconds.
I created an array of possible eligible digits to get position in the chain.
If the last digit in so far calculated permutation set is 1 , the first index of of the prime_vec for further iteration is 1.
int candidate = prime_vec[ index ][ i++ ];
index will get value 1 and iterate over that specific dimension to consider all eligible values to accommodate the next probable position in permutation.
This is the Pseudo code for this solution:
Read the even number N from input file
if it is less than 2 or greater than 18, return 0
Create a std::vector> Vec to keep all possible permutations satisfying condition sum of consecutive elements should be prime.
create a std::vector temp and insert 1
In step 4 since we inserted with 1, an odd number, consider all even numbers <= N and append with temp. 2,4,6,10,12,16,18 are all candidates.
So if N==18, we will get {1,2}, {1,4}, {1,6}, {1,10}, {1,12}, {1,16},{1,18}. {1,8} is not a valid pair since sum of digits is 9 and not a prime.
On top of that we have to make sure the new digit that we are going to add in vector should not be present in that vector before we are adding.
So keep all eligible pair of digits as vectors inside vec
Iterate over each vector from vec. And consider the digit from 2nd position of vector. For example consider {1,2}.
So 2 is the 2nd position digit, so eligible digits to place in 3rd position are {3,5,9,11,15,17}. So we will get{1,2,3}, {1,2,5}, {1,2,9}, {1,2,11},
{1,2,15} and {1,2,17}. Digits 7 and 13 are not eligible , since addition with 2 for them will not generate prime numbers.
On top of that we have to make sure the new digit that we are going to add in vector should not be present in that vector before we are adding.
Repeat the steps 5 and 6 in order for all vectors from vector vec until we place the digits in all N positions.
Take the size of vector vec
Is there any way to improve its performance? Please let me know if I need to clarify any details more.