一种求字符集子集的方法

        今天一个同学问我: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狂 阅读(2019) 评论(5)  编辑  收藏 所属分类: Java算法

评论

# re: 一种求字符集子集的方法[未登录] 2007-04-15 23:24 alex

....ju ran you zhe me sha d banfa  回复  更多评论   

# re: 一种求字符集子集的方法 2007-04-16 12:13 我为J狂

@alex
朋友,恕我才疏学浅,实在不明白您评论的意思!请您赐教。  回复  更多评论   

# re: 一种求字符集子集的方法 2011-05-13 19:52 Claude

他说:居然有这么傻的办法  回复  更多评论   

# re: 一种求字符集子集的方法 2011-05-13 19:53 Claude

我觉得这算法很牛呀,或许他知道更好的算法吧,不过看他这么不淡定,应该不咋地,呵呵  回复  更多评论   

# re: 一种求字符集子集的方法 2014-04-11 16:33 phenix

如果这个字符串中有字母重复,该怎么做呢?  回复  更多评论   


只有注册用户登录后才能发表评论。


网站导航:
 
<2007年4月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
293012345

导航

统计

常用链接

留言簿(11)

随笔分类(48)

文章分类(29)

常去逛逛

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜