任何人都可以解釋這段代碼如何生成組合？

我發現了generating combinations的一些Java代碼，但是我不明白它在做什麼，因爲它用位進行一些奇怪的操作。任何人都可以解釋這段代碼如何生成組合？

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; 
    } 
}

來源

2010-10-24 Casebash

哇，這真的很低效。這是一個2^n算法。你應該使用別的東西。 – JoshD 2010-10-24 09:11:14

一組項目的特定組合可以表示爲二進制數字，其中數字的位n表示該組合包括該組的項目＃n。

該代碼是簡單地通過足夠的二進制數的循環來表示一整套n項（從0到(1<<n) - 1，這是相同的2^N-1），並加入每一個具有完全相同c 1位在其中（意思是那些將由這些位表示的項目在給定的組合中）列表。

來源

2010-10-24 09:14:25 cHao

給定選擇（r，n），它會創建一個數字n位寬，然後從0到2^n計數。它會檢查每個值，看它是否有r位置位。如果確實如此，它會將其添加爲有效組合。使用這些數字，它會形成有效的組合字符串。

對此有更好的算法。我建議你在其他地方搜索。

來源

2010-10-24 09:13:31 JoshD

任何人都可以解釋這段代碼如何生成組合？

回答

相關問題