Thread: 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.

Thanks in advance.



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;
}

std::next_permutation

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.

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?