每种可能的组合算法

假设我有2个由A和B组成的符号。我想打印最大长度为n的A和B的所有组合。 n可以取为3，4，或5每种可能的组合算法

例如当n = 3，有总共8种可能性：

AAA 
AAB 
ABB 
BBB 
BBA 
BAA 
BAB 
ABA

什么是最简单和有效的方法是什么？感谢

来源

2014-11-21 Davita

对于最多三个字符会有另6个posibilities; AA，AB，BA，BB，A和B. – Guffa 2014-11-21 21:40:22

您的意思是PERMUTATIONS？，您列出了AAB和BAA。 – JosEduSol 2014-11-21 21:40:59

@Guffa没有长度不会少于n – Davita 2014-11-21 21:41:27

可能性对应的位模式为所有可能的号码，您可以用n位表示：

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

来源

2014-11-21 21:56:54 Guffa

完美的作品，谢谢:) – Davita 2014-11-21 22:04:19

对于给定的ň总有2^N的方式，为我们可以选择2个型动物符号的每个位置。对于一般数量的符号，通常的做法是回溯，但由于您只有两个符号，所以使用位掩码更容易。

注意和2^n的号码 - 写在二进制1包含lenght ň的所有可能的位掩码，所以你可以“以二进制打印的数字，书写A或B取决于如果该位是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; 
    } 
}

来源

2014-11-21 21:48:33 AlexAlvarez

转换整型成比特数组布尔，那么就循环该阵列，只要你知道它只会是2个字符（和AB），然后二进制应该工作。

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

来源

2014-11-21 21:48:40

因为你只有两个符号，你可以用二进制表示一个数N位，并通过A的替代零和1层的由B.下面是一些伪代码，因为没有指定语言

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

来源

2014-11-21 21:48:42

每种可能的组合算法

回答

相关问题