All possible combinations of algorithms
Let's say I have 2 characters consisting of A and B. I want to print the entire combination of A and B with a maximum length of n. n can be 3, 4, or 5.
for example, when n = 3, there are 8 general possibilities:
AAA
AAB
ABB
BBB
BBA
BAA
BAB
ABA
What's the easiest and most efficient way to do this? Thanks to
source to share
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 just loop over the numbers and get a binary representation using symbols 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>');
}
source to share
For a given n, there are always 2 ^ n ways, since for each position we can choose 2 different characters. For the total number of characters, the usual approach will return, but since you only have two characters, a simpler approach using bitmasks works.
Note that the numbers 0 through 2 ^ n - 1 written in binary contain all possible bitmasks with length n, so you can simply "print out the numbers in binary by typing A or B if the bit is 0 or 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;
}
}
source to share
Convert int to bit-bool array, then just loop over that array. As long as you know that it will be only 2 characters ( A
and B
) then the binary file 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
source to share
Since you only have two characters, you can just use the binary representation of the number N bits and replace the zeros with A and 1 with B. Here is some pseudo code 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
source to share