代码之家  ›  专栏  ›  技术社区  ›  Casebash

有人能解释一下这段代码是如何生成组合的吗?

  •  2
  • Casebash  · 技术社区  · 14 年前

    我找到了一些Java代码 generating combinations 但是我不明白它在做什么,因为它用比特做了一些奇怪的操作。

    import java.util.Collections;
    import java.util.LinkedList;
    
    public class Comb{
    
        public static void main(String[] args){
                System.out.println(comb(3,5));
        }
    
        public static String bitprint(int u){
                String s= "";
                for(int n= 0;u > 0;++n, u>>= 1)
                        if((u & 1) > 0) s+= n + " ";
                return s;
        }
    
        public static int bitcount(int u){
                int n;
                for(n= 0;u > 0;++n, u&= (u - 1));
                return n;
        }
    
        public static LinkedList<String> comb(int c, int n){
                LinkedList<String> s= new LinkedList<String>();
                for(int u= 0;u < 1 << n;u++)
                        if(bitcount(u) == c) s.push(bitprint(u));
                Collections.sort(s);
                return s;
        }
    }
    
    2 回复  |  直到 14 年前
        1
  •  5
  •   cHao    14 年前

    一组项目的特定组合可以表示为二进制数,其中位 n 表示组合是否包括项# n 这个组的

    代码只是循环通过足够多的二进制数来表示一组 n 项目(从0到 (1<<n) - 1 ,与2^n-1相同),并添加 c 列表中的1位(表示由这些位表示的项在给定的组合中)。

        2
  •  1
  •   JoshD    14 年前

    给定choose(r,n),它将创建一个n位宽的数字,然后从0到2^n计数。它检查每个值是否设置了r位。如果是,它会将其作为有效组合添加。有了这些数字,它就形成了有效的组合字符串。

    有更好的算法。我建议你到别处找。