Permutations

This is a discussion on Permutations within the C++ Programming forums, part of the General Programming Boards category; Hey guys, this is my first post. I'm in this C++ competitions and I'm doing some tasks for practice. In ...

  1. #1
    Registered User
    Join Date
    Mar 2010
    Posts
    2

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

  2. #2
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,145
    std::next_permutation

  3. #3
    Registered User
    Join Date
    Mar 2010
    Posts
    15
    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. #4
    Registered User
    Join Date
    Mar 2010
    Posts
    2
    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?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Permutations
    By bumfluff in forum C++ Programming
    Replies: 2
    Last Post: 10-05-2008, 12:33 PM
  2. recursive permutations
    By wd_kendrick in forum C Programming
    Replies: 7
    Last Post: 06-02-2008, 03:11 PM
  3. permutations of a string
    By agarwaga in forum C Programming
    Replies: 1
    Last Post: 05-23-2006, 08:52 AM
  4. can't print all the permutations of a number
    By whizkid in forum C++ Programming
    Replies: 1
    Last Post: 12-11-2005, 09:41 AM
  5. Permutations
    By kiddy in forum C++ Programming
    Replies: 1
    Last Post: 02-11-2002, 08:53 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21