Все возможные комбинации алгоритмов

Question

Скажем, у меня есть 2 символа, состоящих из A и B. Я хочу напечатать всю комбинацию A и B с максимальной длиной n. п может быть 3, 4 или 5.

, например, при п = 3, существует всего 8 возможностей:

AAA 
AAB 
ABB 
BBB 
BBA 
BAA 
BAB 
ABA 

Что самый простой и эффективный способ сделать это? Благодаря

Answer 1

Возможность соответствует битовым шаблонам для всех возможных чисел, которые можно представить с п битами:

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

вы можете просто цикл, хотя число и получить двоичное представление с использованием символов вместо двоичных цифр.

Пример:

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

Answer 2

Для данного п всегда есть 2^п способы, как для каждой позиции мы можем выбрать 2 Differents символов. Для общего числа символов обычный подход будет возвращаться, но поскольку у вас есть только два символа, работает более простой подход, использующий битмаски.

Обратите внимание, что число между и 2^п - 1 записанным в двоичной системе содержит все возможные битмаски от длины п, так что вы можете просто «напечатать число в двоичной системе, писать А или В в зависимости от того бит равен 0 или 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; 
    } 
} 

Answer 3

Преобразование Int в массив битов BOOL, то только петлевой этот массив. до тех пор, как вы знаете, это будет только 2 символа (A и B), то бинарные должны работать.

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 

Answer 4

Поскольку у вас есть только два символа, вы можете просто использовать бинарное представление ряда N битов и заменить нули на А, и 1-х Б. Вот некоторые псевдокод, так как не указан язык

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