一种求字符集子集的方法

        今天一个同学问我：Java中有没有二进制数据类型，我在Baidu上搜了一下，得到结论Java中的整型变量只有十进制，八进制，十六进制的表示形式。我问这个同学为什么要问这个问题，他告诉我,他在编一个算法时用到二进制转换问题。他是在为一个字符集求子集。他的算法如下：
        对于集合{A,B,C,D}，它的非空子集个数为2×2×2×2－1，用二进制表示就是1111，我们规定从左到右第1位对应A，第2位对应B，第3位对应C，第4位对应D。如果相应位为1，则表示存在该字符，否则不存在该字符。如1101就表示{A，B，D} 。这样，对于一个n个字符组成的集合，根据n可以算法它的非空子集个数为m（2的n次幂－1），将m转换为二进制数，然后采用每次减1的方法，即可得到所有子集。
       这个时候我才理解同学寻找二进制数据类型的原因，其实我们完全可以在javaAPI中选择一个能将整型变量转换为二进制字符串的方法，先将整型变量-1，再转换为二进制字符串，最后根据二进制字符串就可以得到相应集合的子集。 我在JDK帮助文档中查到一个方法：Integer类中有一个static方法toBinaryString(int i),这个方法就是将整型i转换为二进制字符串，这下一切都解决了，代码如下：

/**//*
 *@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狂 阅读(2029) 评论(5)  编辑  收藏 所属分类: Java算法