在Python 3.x中生成位排列的最快方法

我需要生成所有可能的N個選擇其中K位被設置的K個N位數。我能夠拿出最好的和最簡潔的選擇是極其緩慢：在Python 3.x中生成位排列的最快方法

def kbits(n, k): 
    result = set() 
    for bits in itertools.combinations(range(n), k): 
     s = 0 
     for bit in bits: 
      s |= 1 << bit 
     result.add(s) 
    return result

kbits(25, 12)我的機器上花了8.3s。

我該如何加快速度？例如，也許有一種方法可以批量設置所有位，而不需要遍歷所有這些位？

來源

2016-11-06 Nick Slavsky

什麼是你真正想實現與這樣的結果？你有什麼樣的性能要求？ – jonrsharpe

好吧，這是使用DP解決旅行商問題的一部分。我生成城市的所有2 **（n-1）個子集，然後遍歷它們。實際上，除了儘可能快地使用它之外，沒有強加給我的性能要求:) –

你的kbits(25, 12)正在計算12個相同的25個功率超過500萬次，當它只需要計算它們每個一次（並且已經這樣做，可以使用內建的sum()而不是逐個建立結果）。

這裏有一個更短的解決方案，這也是對快3倍我的機器上：

def kbits(n, k): 
    powers = [1 << e for e in range(n)] 
    return {sum(bits) for bits in itertools.combinations(powers, k)}

來源

2016-11-06 13:06:34

在Python 3.x中生成位排列的最快方法

回答

相關問題