BrynzaMasterZa228's blog

Best way to write 3^n without recursion like 2^n bitmask is there a way?
By BrynzaMasterZa228, history, 2 years ago, In English

I just solved a problem that need 3^n recursion 0,1,2 0=not choose, 1=choose one way, 2=choose 2nd way like this, and its messy cause we need the path we took also it itself doesnt seem nice, can you guys please write your ways of writing .

sorry i will reply hours late cause i will sleep rn

  • Vote: I like it
  • -1
  • Vote: I do not like it

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

Please send the link

→ Reply
»
2 years ago, # |
  Vote: I like it +21 Vote: I do not like it

You could generate 2^n masks and then iterate over submasks, it'll be 3^n in total (e.g. outer mask 0 => option #1, inner mask 0 => #2, inner mask 1 => #3)

  for (int mask = 0; mask < (1 << n); mask++) {
    for (int sub = mask;; sub = (sub - 1) & mask) {
      /* process */
      if (sub == 0) break;
    }
  }

Or just write a recursion, it's not really much code in modern c++ and a lot more flexible

  vector<int> a(n);
  function<void(int)> rec = [&](int i) {
    if (i < n) {
      for (a[i] = 0; a[i] <= 2; a[i]++) rec(i+1);
    } else {
      /* process */
    }
  };
  rec(0);
→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it 
int p = power(3, n);
for (int i = 0; i < p; ++i) {
    for (int j = i, k = 0; k < n; j /= 3, ++k) {
        cout << j % 3;
    }
    cout << "\n";
}

Similar to the power of two version but you can't use the bitwise operation here. You can also replace 3 with other positive integer to get a more generalized version.

→ Reply
»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

link

→ Reply