Trying to develop a sort of permutation algorithm

Question

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

Sounds like, For given N, K... print all N digit numbers in Base K+1 — Pheonix, Feb 20 '12 at 13:06
maybe you should try std::next_permutation? Take a look at http://stackoverflow.com/questions/4972470/what-is-the-time-complexity-of-stdnext-permutation-function-in-c — innochenti, Feb 20 '12 at 13:14
@innochenti `std::next_permutation` does something totally different from what he's describing. — Ken Bloom, Feb 20 '12 at 13:19

Ken Bloom · Answer 1 · 2012-02-20T13:19:47.757

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.)

nice one :) increment() returns false in case of an overflow. So iterate through all permutations with while(increment(...)){...} — Ben, Feb 20 '12 at 13:24

score 2 · Answer 2 · answered Feb 20 '12 at 13:13

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


}

amit · Answer 3 · 2012-02-20T13:16:49.913

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

Thank you very much and sorry for the late response. This works well for small problems but when I try this with a big problem the recursion is not the way to go. Can someone help doing the same but using dynamic programming? — Michiel, Mar 20 '12 at 12:54
@Michiel: You are welcome. You are asking for all permutations, there are exponential number of those, any algorithm that produces all of them will suffer from long run time. — amit, Mar 20 '12 at 12:56

Trying to develop a sort of permutation algorithm

3 Answers3