Powerset與Pythonset中的frozenset

我在這裏坐了近5個小時試圖解決問題，現在我希望你的幫助。Powerset與Pythonset中的frozenset

這裏是我的Python代碼：

def powerset3(a): 

     if (len(a) == 0): 
      return frozenset({}) 
     else: 
      s=a.pop() 
      b=frozenset({}) 
      b|=frozenset({}) 
      b|=frozenset({s}) 
      for subset in powerset3(a): 

       b|=frozenset({str(subset)}) 
       b|=frozenset({s+subset}) 
      return b

如果我和運行程序：

print(powerset3(set(['a', 'b'])))

我獲得以下解決方案

frozenset({'a', 'b', 'ab'})

但我想有

{frozenset(), frozenset({'a'}), frozenset({'b'}), frozenset({'b', 'a'})}

我不想使用庫，它應該遞歸！

感謝您的幫助

來源

2014-10-26 user3581050

我想你不想使用任何庫來做到這一點？ – 2014-10-26 17:59:21

是沒有庫和遞歸！ – user3581050 2014-10-26 18:04:55

您應該將其添加到您的問題中 – 2014-10-26 18:08:37

下面是使用itertools一個稍微更可讀的實施，如果你不希望使用一個lib的組合，可以對其實施例如更換組合代碼從https://docs.python.org/2/library/itertools.html#itertools.combinations

def powerset(l): 
    result = [()] 
    for i in range(len(l)): 
     result += itertools.combinations(l, i+1) 
    return frozenset([frozenset(x) for x in result])

測試上IPython的，具有不同長度的

In [82]: powerset(['a', 'b']) 
Out[82]: 
frozenset({frozenset(), 
      frozenset({'b'}), 
      frozenset({'a'}), 
      frozenset({'a', 'b'})}) 

In [83]: powerset(['x', 'y', 'z']) 
Out[83]: 
frozenset({frozenset(), 
      frozenset({'x'}), 
      frozenset({'x', 'z'}), 
      frozenset({'y'}), 
      frozenset({'x', 'y'}), 
      frozenset({'z'}), 
      frozenset({'y', 'z'}), 
      frozenset({'x', 'y', 'z'})}) 

In [84]: powerset([]) 
Out[84]: frozenset({frozenset()})

來源

2014-10-26 17:48:30 bakkal

你那種有正確的想法。如果a非空，那麼a的powerset可以通過從a獲取某些元素s而形成，我們稱之爲rest的剩餘部分。然後從rest的權力集合中增加s的權力，中的每一個powerset3(rest)均爲subset本身，subset | frozenset({s})。

最後一點，做subset | frozenset({s})而不是字符串連接是您的解決方案缺少的一半。另一個問題是基本情況。空集的powerset是而不是的空集，是包含空集的一個元素的集合。

還有一個問題，您的解決方案是，你試圖使用frozenset，這是不可改變的，在可變的方式（如pop()，b |= something等）

這裏是一個有效的解決方案：

from functools import partial 

def helper(x, accum, subset): 
    return accum | frozenset({subset}) | frozenset({frozenset({x}) | subset}) 

def powerset(xs): 
    if len(xs) == 0: 
     return frozenset({frozenset({})}) 
    else: 
     # this loop is the only way to access elements in frozenset, notice 
     # it always returns out of the first iteration 
     for x in xs: 
      return reduce(partial(helper, x), powerset(xs - frozenset({x})), frozenset({}))   

a = frozenset({'a', 'b'}) 
print(powerset(a))

來源

2014-10-26 18:35:54

Powerset與Pythonset中的frozenset

回答

相關問題