CODEWITHSUNDEEP
c++
Michiel
Michiel

Reputation: 1051

Trying to develop a sort of permutation algorithm

I want to develop the following put can't get it right. I have a vector of N length. Each element can become 0 to K. Here N and K are given by the user. Now I'm trying to create a function in which I can walk through all possible solutions.

So let's say N is 4 and K = 2, then I want to loop through all possible permutations (?).

I want to fill a vector with 0000, test it then fill the vector with 1000, test it then 0100 etc.

It's important to know that 0100 and 0010 are different. As are 1100 and 0011 etc.

For extra notice this is what the loop should print (it really doesn't matter is 0001 or 1000 comes after 0000 etc as long as all different possible sequences come up).

0000, 1000, 0100, 0010, 0001, 1100, 1010, 1001, 1110, 1101, 0111, 0101, ....., 2012, 2211 etc..

I've tried a combination of for loops but can't really get it. The application is in C++

Please help, tnx

Upvotes: 1

Views: 381

Answers (3)

Ken Bloom
Ken Bloom

Reputation: 58770

I don't think permutation is the word you're looking for. You're talking about counting, so what you want to do is essentially increment the vector, just like if you were doing addition long hand as you did in first grade

First value   0 0 0 0
Add 1               1
              =======
Second Value  0 0 0 1
Add 1               1
              =======
Third Value   0 0 1 0

So you'd do somethign like this:

// returns false when you've seen all of the possible values for this vector
bool increment(std::vector<int> & vector, int k) {
  for (int i = 0; i < vector.size(); ++i) {
    int j = vector[i] + 1;
    if (j <= k) {
      vector[i] = j;
      return true; 
    }
    else vector[i] = 0;
    // and carry a 1 by looping back again
  }
  return false;
}

This will return values in the following order, for k=1, assuming you start with the vector 0000: 1000, 0100, 1100, 0010, 1010, 0110, 1110, 0001, 1001, 0101, 1101, 0011, 1011, 0111, 1111. (Picture counting in binary -- I've merely reversed each of the numbers to fit our ordinary view of a vector as going from left to right.)

Upvotes: 4

amit
amit

Reputation: 178451

You might want a recursive solution to do it neatly.
Place the all the possibilities to the first element, and recursively invoke with decreasing size.

Pseudo code:

permutations(int n, int k, solution):
   if (n==0): //base clause
       print solution //or append to some extra data structure
       return
   for (i = 0 ; i <= k ; i++):
       solution.append(i)
       permutations(n-1,k,solution) //recursive call
       solution.removeLast() //clean up environment before moving to the next possibility

invoke with permutations(n,k,v) - where n,k are your parameters and v is an empty std::vector

EDIT: C++ code:

void permutations(int n, int k,vector<int> &solution) {
   if (n==0) { //base clause
       print(solution);
       return;
   }
   for (int i = 0 ; i <= k ; i++) {
       solution.push_back(i);
       permutations(n-1,k,solution); //recursive call
       solution.pop_back(); //clean up environment before moving to the next possibility
   }
}

a demo including the print() function can be found here

Upvotes: 1

Pheonix
Pheonix

Reputation: 6052

Something like this comes to my mind

bool increase(vector<int> &d, int index, int k){

  if(index == d.size()){
    return false;
  }

  if(d[index] == k){
    d[index] = 0;
    increase(d, index+1, k);
  }else{
    d[index]++;
  }

  return true;
}

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

int main(){
//int N, K predefined, and initialised.

  vector<int> D(N, 0);

  do{
    printvector(d);
  }while(increase(d, 0, K);


}

Upvotes: 2

Related Questions