與心靈對話

posts - 195, comments - 34, trackbacks - 0, articles - 1

輸出組合的一個非遞歸算法

Posted on 2007-04-01 21:15 小強摩羯座閱讀(485) 評論(0) 編輯收藏

算法利用了從1到pow(2,n)-1的所有整數的二進制表示中1的位置組合剛好是所要取的所有組合的性質。

static void combin(char []list)
2

{
3

int count = (int)Math.pow(2, list.length)-1 ;
4

int [] b = new int[list.length];
5

for(int i = 1; i <= count;i++)
6

{
7

for(int j =0 ;j < list.length;j++)
9

{
10

b[j] = (i>>j) & 1;
11

}
12

for(int k = 0;k < list.length;k++)
13

{
14

if(b[k] == 1)
15

System.out.print(list[k]);
16

}
17

// if(i < count) System.out.print(", ");
18

System.out.println();
19

}
20

}

一個輸出結果是，如此調用

char []str={'1', '2', '3', '4'};

combin(str);

結果如下：
1
2
12
3
13
23
123
4
14
24
124
34
134
234
1234