高效全组合算法

淡淡的烟草味﹌ 2022-05-24 08:19 170阅读 0赞

转载 https://blog.csdn.net/xx\_123\_1\_rj/article/details/58585092

算法说明：当n大于2时，n个数的全组合一共有(2^n)-1种。  
当对n个元素进行全组合的时候，可以用一个n位的二进制数表示取法。  
1表示在该位取，0表示不取。

例如，对ABC三个元素进行全组合，用二进制表示如下

001表示取C，      001=1

010表示取B，      010=2

011表示取BC，    011=3

100表示取A，      100=4

101表示取AC       101=5

110表示取AB，    110=6

111表示取ABC      111=7

很显然ABC三个元素全组合共有2^3-1=7种。

推广到对n个元素进行全排列，取法就是从1到2^n-1的所有二进制形式   
要取得2^n，只需将0xFFFFFFFF左移32-n位，再右移回来就可以了。0xFFFFFFFF>>>(32 - n) 结果既为（2的n次方减1）。

对于每一种情况，怎么快速检验一位被丢掉，哪一位被选中呀？假设这个标记数是i，想检测它的第j位是0还是1。int为4字节，占32位。首先先将i左移31-j位，就将第j移到了最高位，再将结果右移31位，此时原来的第j位移到了最低位，它左侧的所有位都被填充为原第j位的值。所以此时整个标记数的值只有两种情况0或-1，分别对应第j位被过滤或者是被选中的情况。

这里复习一下Java中的相关知识：

java中有三种移位运算符

<<      :     左移运算符，num << 1,相当于num乘以2

>>      :     右移运算符，num >> 1,相当于num除以2

>>>    :     无符号右移，忽略符号位，空位都以0补齐

0xffffffff表示的是一个十六进制数  
换为十进制数 ： 0xffffffff=16x10^7+16x10^6+...+16x10^0=4294967295  
换为二进制数 ： 十六进制转换为二进制就是直接把每位转换成二进制就可以了，就是直接f变成二进制：1111，

则 0xffffffff = 1111 1111 1111 1111 1111 1111 1111 1111 ， 即32位数都是1的二进制数

其中16进制数 0xFFFFFFFF 不用强制转换可以是int型，其值为 -1

因为int 为带符号类型，带符号类型最高为是符号位，又因为0xFFFFFFFF，也就是四个字节32 bits全是1, 符号位是1，所以这个数是负数。  
内存中的数值为补码表示，所以0xFFFFFFFF是一个负数的补码。负数从补码求原码，最高符号位不变，保持 1， 其余各位求反，末尾加1。

也就是 0xFFFFFFFF，二进制为：1111  1111  1111  1111  1111  1111 1111  1111

\->  10000000 00000000 00000000 00000000  
\->  10000000 00000000 00000000 00000001  
原码首位表示符号位，其余位表示绝对值大小，所以，这个数是 -1

Java实现代码如下：

\[java\]  [view plain][]   [copy][view plain]

1.  **public** **class** Test1 \{  
2.    
3.      **public** **static** **void** main(String\[\] args) \{  
4.          // TODO Auto-generated method stub  
5.              
6.          String str\[\] = \{ "A", "B", "C", "D", "E" \};    
7.          **int** nCnt = str.length;    
8.          //int nBit = (0xFFFFFFFF >>> (32 - nCnt));    
9.          **int** nBit = 1<<nCnt;    
10.         **for** (**int** i = 1; i <= nBit; i++) \{    
11.             **for** (**int** j = 0; j < nCnt; j++) \{    
12.                 **if** ((i << (31 - j)) >> 31 == -1) \{    
13.                     System.out.print(str\[j\]);    
14.                 \}    
15.             \}    
16.             System.out.println("");    
17.         \}    
18.     \}  
19. \}

其中 int nBit = (0xFFFFFFFF >>> (32 - nCnt));  与语句  int nBit = 1<<nCnt;  等价

[view plain]: https://blog.csdn.net/xx_123_1_rj/article/details/58585092#