CODEWITHSUNDEEP
algorithm
Davita
Davita

Reputation: 9114

Every possible combination algorithm

Say I've got 2 symbols consisting of A and B. I want to print all combination of A and B with a maximum of n length. n could be 3, 4, or 5.

for example when n=3, there is 8 total possibilities:

AAA
AAB
ABB
BBB
BBA
BAA
BAB
ABA

What's the easiest and efficient way to do this? Thanks

Upvotes: 3

Views: 930

Answers (4)

Guffa
Guffa

Reputation: 700152

The possibilities correspond to bit patterns for all possible numbers that you can represent with n bits:

0 = 000 -> AAA
1 = 001 -> AAB
2 = 010 -> ABA
3 = 011 -> ABB
4 = 100 -> BAA
5 = 101 -> BAB
6 = 110 -> BBA
7 = 111 -> BBB

You can simply loop though the numbers, and get the binary representation using the characters instead of binary digits.

Example:

var n = 3;
var chars = [ 'A', 'B' ];

var max = Math.pow(2, n);

for (var i = 0; i < max; i++) {
  var s = '', x = i;
  while (s.length < n) {
    s = chars[x & 1] + s;
    x >>= 1;
  }
  document.write(s + '<br>');
}

Upvotes: 2

But I&#39;m Not A Wrapper Class
But I&#39;m Not A Wrapper Class

Reputation: 14276

Convert the int to a bit-bool array, then just loop that array. As long as you know it will only be 2 characters (A and B), then binary should work.

permutations(int n):
    for(int i = 0; i < 2^n; i++)
        print convert(toBitArray(int));

string convert(bool[] bits)
    string retStr = "":
    for(int b = 0; b < bits.size; b++)
        if(bits[b])
            retStr += "A";
        else
            retStr += "B";

bool[] toBitArray(int i):
    //converts int to a a bit-bool array

Upvotes: 0

Eugene Sh.
Eugene Sh.

Reputation: 18299

Since you have only two symbols, you can just use binary representation of a number of N bits and replace zeros by A's, and 1's by B. Here is some pseudocode, since no language is specified

for k in range 0 to 2^N-1
  printString(k, N)
end for

printString(k,N)
  for N times 
      if LSB(k)==0  //(or mod 2 is 0)
          print A
      else
          print B
      shift k right one bit //(or divide by 2)
  print newline

Upvotes: 0

AlexAlvarez
AlexAlvarez

Reputation: 829

For a given n there are always 2^n ways, as for each position we can choose 2 differents symbols. For a general number of symbols, the usual approach would be backtracking, but since you only have two symbols, an easier approach using bitmasks works.

Notice that the numbers between 0 and 2^n - 1 written in binary contain all possible bitmasks of lenght n, so you can just "print the numbers in binary, writing A or B depending if the bit is a 0 or a 1.

#include <iostream>
using namespace std;

int main() {
  int n;
  cin >> n;

  for (int i = 0; i < (1 << n); ++i) {
    for (int j = 0; j < n; ++j) {
      cout << (((i >> j) & 1) ? "B" : "A");
    }
    cout << endl;
  }
}

Upvotes: 0

Related Questions