1. ## Permutations

Hey guys, this is my first post.
I'm in this C++ competitions and I'm doing some tasks for practice.
In some tasks I need to shuffle elements in an array and find the permutation that is correct.
For example, user inputs an array of numbers and I have to output a permutation of that array to that no sum of adjacent 2 numbers is a prime number.

I had an idea about making a recursion that tries every combination and finds the one that works but as I began coding it, it became so confusing that I couldn't keep up with my own code.

So I ask you, what is the best way of approaching problem such as this?

And before you say do your own homework know that this isn't homework but a hobby and I just want to know what the best method to solve that kind of problems is.

Here's the unfinished code that you can look at, tho I doubt you'll understand anything since I don't even understand it =P

Code:
```#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <cstring>
#include <queue>
using namespace std;

int from, to;
vector<int>niz;

bool isPrim( int n ) {
for (int i=2; i<sqrt(n); ++i){
if (!n%i) return false;
}
return true;
}

bool rek (vector<int> o, int step){
if (step==to-from) {
vector<int> noviNiz(step);
for (int i=0; i<step; ++i){
noviNiz[i]=niz[o[i]];
}
niz=noviNiz;
return true;
}
vector<pair <int, int> > noviNiz(to-from-step);
int skip=0;
for (int i=0; i<to-from; i++){
for (int j=0; j<step; ++j){
if (o[j]==i){
skip=1;
break;
}

}
pair <int,int> tempPair;
tempPair.first=niz[i];
tempPair.second=i;
if (!skip) noviNiz.push_back(tempPair);

}
for (int i=0; i<noviNiz.size(); ++i){
if (isPrim(niz[o[step]]+noviNiz[i].first)) continue;
vector <int> o2=o;
o2.resize(o2.size()+1);
o2.push_back(noviNiz[i].second);

rek(o2,step+1);

}

}

int main (){
cin >> from >> to;
niz.resize(to-from);
for (int i=0; i<to-from;++i){
niz[i]=i+to;
}
for (int i=0; i<to-from;++i){
vector<int> niz2(1);
niz2[0]=i;
if (rek(niz2,1)) break;
}
for (int i=0; i<to-from;++i){
cout << niz[i];
if (i!=to-from-1) cout << endl;

}

system("PAUSE");
return 0;
}```

2. std::next_permutation

3. Let's take the example with adjacent numbers not having a prime sum. You have an implicit static evaluation function for any state of the array (permutation): the number of errors. Each pair of adjacent numbers with prime sum is an error. You should look for a transposition that yields the greatest reduction in this error function. A transposition is swapping two elements of the array, for instance element i and j. It can reduce the number of errors by up to 4. Continue in this way until there are no more errors.

4. Code:
```#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <cstring>
#include <queue>
using namespace std;

int from, to;
vector<int>niz;
map <int, int> prim;

bool isPrim( int n ) {
int i=2;
while (i<=sqrt(n)){

if (!(n%i)) return false;
if (i==2) --i;
i+=2;
}
return true;
}

void trace(vector<int> a){
for (int i=0; i<a.size(); ++i){
cout << a[i] << " ";

}
cout << endl;

}

bool isValid (vector<int> o){
int i=0;
while ( i<o.size()){

if (i) if (isPrim(o[i]+o[i-1])) {
while (true){
int done=0;
int j=i;
while (j<o.size()) {
if (niz[j]==o[i]+1) swap(niz[j], niz[i]), sort (niz.begin()+j, niz.end()), done=1;
j++;
}
if (done || !i) break;
else --i;

}
return 0;
}
++i;
}
return 1;

}

int main (){

cin >> from >> to;
to++;
niz.resize(to-from);
for (int i=0; i<to-from;++i){
niz[i]=i+from;
}
while (true){
if (!next_permutation(niz.begin(), niz.end())) {cout << 0; system("pause"); return 0;}
else if (isValid(niz)) break;

}
for (int i=0; i<to-from;++i){
cout << niz[i];
if (i!=to-from-1) cout << endl;

}

system("PAUSE");
return 0;
}```
This code works but it's not fast enough to pass all the tests, it passes 12/20.

Do you have any ideas how to optimize it more?

You should look for a transposition that yields the greatest reduction in this error function.
I don't think this code uses that method but that's the problem, how to I cycle trough the transpositions?