Tyr's blog

By Tyr, 9 years ago, In English

Hi, I want to generate bit strings of length n and exactly m ones I came up with this algorithm but can't make it more efficient any Idea ? or am I doing optimization right ?


// cin >> number >> no; // sample input 3 1 // smaple output: // 0 0 1 // 0 1 0 // 1 0 0 int number, nOnes, no; int solution[10000]; void backtrack(int n) { if(n == number) { if(nOnes == no) print(); } else { int candidates[] = {0, 1}; for(int i = 0; i < 2; i++) { if(candidates[i] == 1) { nOnes += 1; if(nOnes > no){ nOnes--; return; } } solution[n] = candidates[i]; backtrack(n + 1); if(candidates[i]) nOnes -= 1; } } }
 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

O(c(n, k) * n) code

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thanks, really helpful.

»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    because I want to practice backtrack ! :)

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

yup, just try next_permutation as suggested by Scalar algo or use c++ STL for this. and feed lowest possible bit string of length n with m ones which will be (n-m) zeroes followed by m ones.