一種求字符集子集的方法

        今天一個(gè)同學(xué)問(wèn)我：Java中有沒(méi)有二進(jìn)制數(shù)據(jù)類型，我在Baidu上搜了一下，得到結(jié)論Java中的整型變量只有十進(jìn)制，八進(jìn)制，十六進(jìn)制的表示形式。我問(wèn)這個(gè)同學(xué)為什么要問(wèn)這個(gè)問(wèn)題，他告訴我,他在編一個(gè)算法時(shí)用到二進(jìn)制轉(zhuǎn)換問(wèn)題。他是在為一個(gè)字符集求子集。他的算法如下：
        對(duì)于集合{A,B,C,D}，它的非空子集個(gè)數(shù)為2×2×2×2－1，用二進(jìn)制表示就是1111，我們規(guī)定從左到右第1位對(duì)應(yīng)A，第2位對(duì)應(yīng)B，第3位對(duì)應(yīng)C，第4位對(duì)應(yīng)D。如果相應(yīng)位為1，則表示存在該字符，否則不存在該字符。如1101就表示{A，B，D} 。這樣，對(duì)于一個(gè)n個(gè)字符組成的集合，根據(jù)n可以算法它的非空子集個(gè)數(shù)為m（2的n次冪－1），將m轉(zhuǎn)換為二進(jìn)制數(shù)，然后采用每次減1的方法，即可得到所有子集。
       這個(gè)時(shí)候我才理解同學(xué)尋找二進(jìn)制數(shù)據(jù)類型的原因，其實(shí)我們完全可以在javaAPI中選擇一個(gè)能將整型變量轉(zhuǎn)換為二進(jìn)制字符串的方法，先將整型變量-1，再轉(zhuǎn)換為二進(jìn)制字符串，最后根據(jù)二進(jìn)制字符串就可以得到相應(yīng)集合的子集。 我在JDK幫助文檔中查到一個(gè)方法：Integer類中有一個(gè)static方法toBinaryString(int i),這個(gè)方法就是將整型i轉(zhuǎn)換為二進(jìn)制字符串，這下一切都解決了，代碼如下：

/**//*
 *@author 我為J狂 建立日期 2007-4-15
 *
 */
package net.blogjava.lzqdiy;

public class IntegerToBinary
{

    /** *//**
     * @param args
     */
    public static void main(String[] args)
    {
        // TODO Auto-generated method stub
        int n = 4;
        int m = (int) Math.pow(2, n) - 1;
        for (int i = m; i >= 1; i--)
        {
            StringBuffer str = new StringBuffer(Integer.toBinaryString(i));

            switch (str.length())
            {
            case 1:
                str.insert(0, "000");

                break;
            case 2:
                str.insert(0, "00");

                break;
            case 3:
                str.insert(0, "0");

                break;

            default:
                break;
            }
            System.out.println(str);
        }
    }
}

本算法的輸出是：
1111
1110
1101
1100
1011
1010
1001
1000
0111
0110
0101
0100
0011
0010
0001

posted on 2007-04-15 12:28 我為J狂 閱讀(2040) 評(píng)論(5)  編輯  收藏 所屬分類: Java算法