156

与えられたセット

{0, 1, 2, 3}

サブセットを作成するにはどうすればよいですか？

[set(),
 {0},
 {1},
 {2},
 {3},
 {0, 1},
 {0, 2},
 {0, 3},
 {1, 2},
 {1, 3},
 {2, 3},
 {0, 1, 2},
 {0, 1, 3},
 {0, 2, 3},
 {1, 2, 3},
 {0, 1, 2, 3}]
4

30 に答える 30

218

Pythonitertoolsページには、まさにpowersetこのためのレシピがあります。

from itertools import chain, combinations

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

出力：

>>> list(powerset("abcd"))
[(), ('a',), ('b',), ('c',), ('d',), ('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd'), ('a', 'b', 'c'), ('a', 'b', 'd'), ('a', 'c', 'd'), ('b', 'c', 'd'), ('a', 'b', 'c', 'd')]

最初の空のタプルが気に入らない場合は、rangeステートメントを変更して、range(1, len(s)+1)長さが0の組み合わせを回避することができます。

于 2009-09-26T22:18:15.053 に答える
71

パワーセットのコードは次のとおりです。これは最初から書かれています：

>>> def powerset(s):
...     x = len(s)
...     for i in range(1 << x):
...         print [s[j] for j in range(x) if (i & (1 << j))]
...
>>> powerset([4,5,6])
[]
[4]
[5]
[4, 5]
[6]
[4, 6]
[5, 6]
[4, 5, 6]

Mark Rushakoffのコメントは、ここに当てはまります。「最初の空のタプルが気に入らない場合は、オンにしてください。」範囲ステートメントをrange（1、len（s）+1）に変更するだけで、長さ0の組み合わせを回避できます。 "、私の場合を除いて、あなたはに変更for i in range(1 << x)しfor i in range(1, 1 << x)ます。

数年後に戻って、私は今それをこのように書くでしょう：

def powerset(s):
    x = len(s)
    masks = [1 << i for i in range(x)]
    for i in range(1 << x):
        yield [ss for mask, ss in zip(masks, s) if i & mask]

そして、テストコードは次のようになります。

print(list(powerset([4, 5, 6])))

使用yieldするということは、単一のメモリですべての結果を計算する必要がないことを意味します。メインループの外側のマスクを事前に計算することは、価値のある最適化であると見なされます。

于 2009-09-26T22:20:22.150 に答える
22

簡単な答えを探しているなら、私はグーグルで「python power set」を検索して、これを思いついた：Python Power Set Generator

そのページのコードからのコピー＆ペーストは次のとおりです。

def powerset(seq):
    """
    Returns all the subsets of this set. This is a generator.
    """
    if len(seq) <= 1:
        yield seq
        yield []
    else:
        for item in powerset(seq[1:]):
            yield [seq[0]]+item
            yield item

これは次のように使用できます。

 l = [1, 2, 3, 4]
 r = [x for x in powerset(l)]

これで、rは必要なすべての要素のリストになり、並べ替えて印刷できます。

r.sort()
print r
[[], [1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 4], [1, 3], [1, 3, 4], [1, 4], [2], [2, 3], [2, 3, 4], [2, 4], [3], [3, 4], [4]]
于 2009-09-26T22:21:05.987 に答える
13 
def powerset(lst):
    return reduce(lambda result, x: result + [subset + [x] for subset in result],
                  lst, [[]])
于 2009-09-26T22:54:12.663 に答える
12

次のアルゴリズムは非常に明確で単純であることがわかりました。

def get_powerset(some_list):
    """Returns all subsets of size 0 - len(some_list) for some_list"""
    if len(some_list) == 0:
        return [[]]

    subsets = []
    first_element = some_list[0]
    remaining_list = some_list[1:]
    # Strategy: get all the subsets of remaining_list. For each
    # of those subsets, a full subset list will contain both
    # the original subset as well as a version of the subset
    # that contains first_element
    for partial_subset in get_powerset(remaining_list):
        subsets.append(partial_subset)
        subsets.append(partial_subset[:] + [first_element])

    return subsets

べき集合を生成する別の方法は、nビットを持つすべての2進数を生成することです。べき集合として、n桁数の数は。です2 ^ n。このアルゴリズムの原則は、2進数が1または0である可能性があるが、両方ではない可能性があるため、要素がサブセットに存在する場合と存在しない場合があることです。

def power_set(items):
    N = len(items)
    # enumerate the 2 ** N possible combinations
    for i in range(2 ** N):
        combo = []
        for j in range(N):
            # test bit jth of integer i
            if (i >> j) % 2 == 1:
                combo.append(items[j])
        yield combo

MITxを使用していたときに両方のアルゴリズムを見つけました。6.00.2x計算思考とデータサイエンスの概要。これは、私が見た中で最も理解しやすいアルゴリズムの1つだと思います。

于 2017-03-11T18:57:43.110 に答える
11

パワーセットの改良があります：

def powerset(seq):
    """
    Returns all the subsets of this set. This is a generator.
    """
    if len(seq) <= 0:
        yield []
    else:
        for item in powerset(seq[1:]):
            yield [seq[0]]+item
            yield item
于 2013-09-29T13:43:39.570 に答える
11

TL; DR（簡略化に直接移動）

以前に回答を追加したことは知っていますが、新しい実装が本当に気に入っています。セットを入力として使用していますが、実際には反復可能である可能性があり、入力のべき集合であるセットのセットを返します。このアプローチは、べき集合（すべてのサブセットの集合）の数学的定義とより一致しているため、私はこのアプローチが好きです。

def power_set(A):
    """A is an iterable (list, tuple, set, str, etc)
    returns a set which is the power set of A."""
    length = len(A)
    l = [a for a in A]
    ps = set()

    for i in range(2 ** length):
        selector = f'{i:0{length}b}'
        subset = {l[j] for j, bit in enumerate(selector) if bit == '1'}
        ps.add(frozenset(subset))

    return ps

回答に投稿した出力が正確に必要な場合は、次を使用してください。

>>> [set(s) for s in power_set({1, 2, 3, 4})]
[{3, 4},
 {2},
 {1, 4},
 {2, 3, 4},
 {2, 3},
 {1, 2, 4},
 {1, 2},
 {1, 2, 3},
 {3},
 {2, 4},
 {1},
 {1, 2, 3, 4},
 set(),
 {1, 3},
 {1, 3, 4},
 {4}]

説明

べき集合の要素数はであることがわかっているので、ループ2 ** len(A)ではっきりと見ることができます。for

入力（理想的にはセット）をリストに変換する必要があります。これは、セットによって一意の順序付けされていない要素のデータ構造であり、サブセットを生成するために順序が重要になるためです。

selectorこのアルゴリズムの鍵です。は入力セットと同じ長さであることに注意しselectorてください。これを可能にするために、パディング付きのf文字列を使用しています。基本的に、これにより、各反復中に各サブセットに追加される要素を選択できます。入力セットに3つの要素{0, 1, 2}があるとすると、セレクターは0から7（両端を含む）の値を取ります。これはバイナリでは次のとおりです。

000 # 0
001 # 1
010 # 2
011 # 3
100 # 4
101 # 5
110 # 6
111 # 7

したがって、各ビットは、元のセットの要素を追加する必要があるかどうかのインジケーターとして機能する可能性があります。2進数を見て、各番号をスーパーセットの要素と考えてください。これ1は、インデックスの要素をj追加する必要があり0、この要素を追加しないことを意味します。

集合の内包的性質を使用して、各反復でサブセットを生成し、このサブセットをに変換して、 （べき集合）frozensetに追加できるようにします。psそうしないと、Pythonのセットは不変オブジェクトのみで構成されているため、追加できません。

簡素化

いくつかのPython内包表記を使用してコードを簡略化できるため、forループを取り除くことができます。zipインデックスの使用を回避するために使用することもできj、コードは次のようになります。

def power_set(A):
    length = len(A)
    return {
        frozenset({e for e, b in zip(A, f'{i:{length}b}') if b == '1'})
        for i in range(2 ** length)
    }

それでおしまい。私がこのアルゴリズムで気に入っているのはitertools、期待どおりに機能しているにもかかわらず、信頼できるように見えるため、他のアルゴリズムよりも明確で直感的であるということです。

于 2019-04-03T04:29:25.483 に答える
5 
def get_power_set(s):
  power_set=[[]]
  for elem in s:
    # iterate over the sub sets so far
    for sub_set in power_set:
      # add a new subset consisting of the subset at hand added elem
      power_set=power_set+[list(sub_set)+[elem]]
  return power_set

例えば：

get_power_set([1,2,3])

収率

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
于 2013-07-17T12:40:08.030 に答える
5

powerset()パッケージの関数を使用しますmore_itertools。

iterableのすべての可能なサブセットを生成します

>>> list(powerset([1, 2, 3]))
[(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

セットが必要な場合は、次を使用します。

list(map(set, powerset(iterable)))
于 2020-01-23T16:44:00.780 に答える
5

これは非常に自然に行うことができますitertools.product：

import itertools

def powerset(l):
    for sl in itertools.product(*[[[], [i]] for i in l]):
        yield {j for i in sl for j in i}
于 2020-10-12T15:13:30.893 に答える
5

手遅れだと思います

すでに他の多くの解決策がありますが、それでも...

def power_set(lst):
    pw_set = [[]]

    for i in range(0,len(lst)):
        for j in range(0,len(pw_set)):
            ele = pw_set[j].copy()
            ele = ele + [lst[i]]
            pw_set = pw_set + [ele]

    return pw_set
于 2020-10-18T09:05:20.000 に答える
3

最もわかりやすいソリューションであるアンチコードゴルフバージョンを提供したかっただけです。

from itertools import combinations

l = ["x", "y", "z", ]

def powerset(items):
    combo = []
    for r in range(len(items) + 1):
        #use a list to coerce a actual list from the combinations generator
        combo.append(list(combinations(items,r)))
    return combo

l_powerset = powerset(l)

for i, item in enumerate(l_powerset):
    print "All sets of length ", i
    print item

結果

長さ0のすべてのセット

[()]

長さ1のすべてのセット

[('x',), ('y',), ('z',)]

長さ2のすべてのセット

[('x', 'y'), ('x', 'z'), ('y', 'z')]

長さ3のすべてのセット

[('x', 'y', 'z')]

詳細については、itertoolsのドキュメント、およびパワーセットに関するウィキペディアのエントリを参照してください。

于 2013-02-16T03:56:58.790 に答える
3

すべてのサブセットの一部である空のセットでは、次を使用できます。

def subsets(iterable):
    for n in range(len(iterable) + 1):
        yield from combinations(iterable, n)
于 2019-06-25T11:56:43.137 に答える
2

簡単なパワーセットの復習！

セットXのべき集合は、空のセットを含むXのすべてのサブセットのセットです。

セット例X=（a、b、c）

べき集合={{a、b、c}、{a、b}、{a、c}、{b、c}、{a}、{b}、{c}、{}}

べき集合を見つける別の方法は次のとおりです。

def power_set(input):
    # returns a list of all subsets of the list a
    if (len(input) == 0):
        return [[]]
    else:
        main_subset = [ ]
        for small_subset in power_set(input[1:]):
            main_subset += [small_subset]
            main_subset += [[input[0]] + small_subset]
        return main_subset

print(power_set([0,1,2,3]))

ソースへの完全なクレジット

于 2019-01-15T07:45:46.157 に答える
2

特定の長さのサブセットが必要な場合は、次のように実行できます。

from itertools import combinations
someSet = {0, 1, 2, 3}
([x for i in range(len(someSet)+1) for x in combinations(someSet,i)])

より一般的には、任意の長さのサブセットの場合、範囲の大きさを変更できます。出力は

[（）、（0、）、（1、）、（2、）、（3、）、（0、1）、（0、2）、（0、3）、（1、2）、（1 、3）、（2、3）、（0、1、2）、（0、1、3）、（0、2、3）、（1、2、3）、（0、1、2、3 ）]

于 2020-08-12T05:57:20.790 に答える
2 
from itertools import combinations
def subsets(arr: set) -> list:
   subsets = []
   [subsets.extend(list(combinations(arr,n))) for n in range(len(arr))]
   return subsets 

a = {1,2,3}
print(subsets(a))

出力：

[(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3)]

ソートされたサブセットの場合、次のことができます。

# sorted subsets
print(sorted(subsets(a)))

出力：

[(), (1,), (1, 2), (1, 3), (2,), (2, 3), (3,)]
于 2021-11-18T15:25:28.473 に答える
1

簡単な方法は、2の補数演算の下で整数の内部表現を利用することです。

整数の2進表現は、0から7の範囲の数値の場合は{000、001、010、011、100、101、110、111}です。整数のカウンター値の場合、1をコレクションに対応する要素を含め、「0」と見なします。除外として、カウントシーケンスに基づいてサブセットを生成できます。数値はからまで生成する必要があります0。pow(2,n) -1ここで、nは配列の長さ、つまり2進表現のビット数です。

これに基づく簡単なサブセットジェネレータ関数は、次のように記述できます。それは基本的に依存しています

def subsets(array):
    if not array:
        return
    else:
        length = len(array)
        for max_int in range(0x1 << length):
            subset = []
            for i in range(length):
                if max_int & (0x1 << i):
                    subset.append(array[i])
            yield subset

そしてそれはとして使用することができます

def get_subsets(array):
    powerset = []
    for i in subsets(array):
        powerser.append(i)
    return powerset

テスト

ローカルファイルに以下を追加

if __name__ == '__main__':
    sample = ['b',  'd',  'f']

    for i in range(len(sample)):
        print "Subsets for " , sample[i:], " are ", get_subsets(sample[i:])

次の出力を提供します

Subsets for  ['b', 'd', 'f']  are  [[], ['b'], ['d'], ['b', 'd'], ['f'], ['b', 'f'], ['d', 'f'], ['b', 'd', 'f']]
Subsets for  ['d', 'f']  are  [[], ['d'], ['f'], ['d', 'f']]
Subsets for  ['f']  are  [[], ['f']]
于 2019-01-21T11:01:52.350 に答える
1

これらの回答のほとんどすべてが、私には少しごまかしのように感じたでlistはなく、を使用しています。それで、好奇心から、私は他の「Pythonに不慣れな」人々のためにset本当に簡単なバージョンを作成して要約しようとしました。set

Pythonのセット実装を扱う際にいくつかの奇妙な点があることがわかりました。私にとっての主な驚きは、空のセットを処理することでした。これは、RubyのSet実装とは対照的です。この実装では、空の1つを含むものを簡単に実行Set[Set[]]して取得できるため、最初は少し混乱します。SetSet

確認するために、sを使用する際powersetにset、2つの問題が発生しました。

  1. set()iterableを取るので、空のset iterableが空set(set())であるために戻ります（ええと、私は推測します:)）set()
  2. セットのセットを取得し、ハッシュ可能set({set()})ではないset.add(set)ため機能しませんset()

両方の問題を解決するために、私はを利用しましfrozenset()た。つまり、私は自分が望むものを完全には得られません（タイプは文字通りですset）が、全体的な相互作用を利用しますset。

def powerset(original_set):
  # below gives us a set with one empty set in it
  ps = set({frozenset()}) 
  for member in original_set:
    subset = set()
    for m in ps:
      # to be added into subset, needs to be
      # frozenset.union(set) so it's hashable
      subset.add(m.union(set([member]))
    ps = ps.union(subset)
  return ps

以下では、出力として2²（16）frozensetが正しく取得されます。

In [1]: powerset(set([1,2,3,4]))
Out[2]:
{frozenset(),
 frozenset({3, 4}),
 frozenset({2}),
 frozenset({1, 4}),
 frozenset({3}),
 frozenset({2, 3}),
 frozenset({2, 3, 4}),
 frozenset({1, 2}),
 frozenset({2, 4}),
 frozenset({1}),
 frozenset({1, 2, 4}),
 frozenset({1, 3}),
 frozenset({1, 2, 3}),
 frozenset({4}),
 frozenset({1, 3, 4}),
 frozenset({1, 2, 3, 4})}

Pythonsetでsを使用する方法はないため、これらをsに変換する場合は、それらを（ ）にマップし直すか、上記を変更する必要があります。setfrozensetsetlistlist(map(set, powerset(set([1,2,3,4]))))

于 2019-07-28T18:40:20.480 に答える
1

質問は古くなっているかもしれませんが、私のコードが誰かに役立つことを願っています。

def powSet(set):
    if len(set) == 0:
       return [[]]
    return addtoAll(set[0],powSet(set[1:])) + powSet(set[1:])

def addtoAll(e, set):
   for c in set:
       c.append(e)
   return set
于 2019-09-26T02:40:06.203 に答える
1

再帰を使用してすべてのサブセットを取得します。クレイジーアスワンライナー

from typing import List

def subsets(xs: list) -> List[list]:
    return subsets(xs[1:]) + [x + [xs[0]] for x in subsets(xs[1:])] if xs else [[]]

Haskellソリューションに基づく

subsets :: [a] -> [[a]]
subsets [] = [[]]
subsets (x:xs) = map (x:) (subsets xs) ++ subsets xs
于 2020-03-22T09:38:50.163 に答える
1 
def findsubsets(s, n): 
    return list(itertools.combinations(s, n)) 

def allsubsets(s) :
    a = []
    for x in range(1,len(s)+1):
        a.append(map(set,findsubsets(s,x)))      
    return a
于 2020-03-23T00:24:37.750 に答える
1

あなたはこのようにそれを行うことができます：

def powerset(x):
    m=[]
    if not x:
        m.append(x)
    else:
        A = x[0]
        B = x[1:]
        for z in powerset(B):
            m.append(z)
            r = [A] + z
            m.append(r)
    return m

print(powerset([1, 2, 3, 4]))

出力：

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3], [4], [1, 4], [2, 4], [1, 2, 4], [3, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]]
于 2020-09-10T20:14:06.490 に答える
0

これらの答えのどれも実際に実際のPythonセットのリターンを提供しないので、これはワイルドです。これは、実際にはPythonであるパワーセットを提供する厄介な実装ですset。

test_set = set(['yo', 'whatup', 'money'])
def powerset( base_set ):
    """ modified from pydoc's itertools recipe shown above"""
    from itertools import chain, combinations
    base_list = list( base_set )
    combo_list = [ combinations(base_list, r) for r in range(len(base_set)+1) ]

    powerset = set([])
    for ll in combo_list:
        list_of_frozensets = list( map( frozenset, map( list, ll ) ) ) 
        set_of_frozensets = set( list_of_frozensets )
        powerset = powerset.union( set_of_frozensets )

    return powerset

print powerset( test_set )
# >>> set([ frozenset(['money','whatup']), frozenset(['money','whatup','yo']), 
#        frozenset(['whatup']), frozenset(['whatup','yo']), frozenset(['yo']),
#        frozenset(['money','yo']), frozenset(['money']), frozenset([]) ])

ただし、より良い実装が見たいです。

于 2013-04-11T06:43:45.613 に答える
0

これは、組み合わせを使用しているが、組み込みのみを使用している私の簡単な実装です。

def powerSet(array):
    length = str(len(array))
    formatter = '{:0' + length + 'b}'
    combinations = []
    for i in xrange(2**int(length)):
        combinations.append(formatter.format(i))
    sets = set()
    currentSet = []
    for combo in combinations:
        for i,val in enumerate(combo):
            if val=='1':
                currentSet.append(array[i])
        sets.add(tuple(sorted(currentSet)))
        currentSet = []
    return sets
于 2013-09-20T23:06:30.973 に答える
0

セットとしての範囲nのすべてのサブセット：

n = int(input())
l = [i for i in range (1, n + 1)]

for number in range(2 ** n) :
    binary = bin(number)[: 1 : -1]
    subset = [l[i] for i in range(len(binary)) if binary[i] == "1"]
    print(set(sorted(subset)) if number > 0 else "{}")
于 2020-03-24T13:44:41.377 に答える
0 
import math    
def printPowerSet(set,set_size): 
    pow_set_size =int(math.pow(2, set_size))
    for counter in range(pow_set_size):
    for j in range(set_size):  
        if((counter & (1 << j)) > 0):
            print(set[j], end = "")
    print("")
set = ['a', 'b', 'c']
printPowerSet(set,3)
于 2020-03-27T09:06:15.163 に答える
0

質問のバリエーションは、「コンピュータサイエンスの発見：学際的な問題、原則、およびPythonプログラミング。2015年版」という本で見た演習です。その演習10.2.11では、入力は単なる整数であり、出力はべき集合である必要があります。これが私の再帰的な解決策です（基本的なpython3以外は何も使用していません）

def powerSetR(n):
    assert n >= 0
    if n == 0:
        return [[]]
    else:
        input_set = list(range(1, n+1)) # [1,2,...n]
        main_subset = [ ]
        for small_subset in powerSetR(n-1):
            main_subset += [small_subset]
            main_subset += [ [input_set[-1]] + small_subset]
        return main_subset

superset = powerSetR(4)
print(superset)       
print("Number of sublists:", len(superset))

そして出力は

[[]、[4]、[3]、[4、3]、[2]、[4、2]、[3、2]、[4、3、2]、[1]、[4、1 ]、[3、1]、[4、3、1]、[2、1]、[4、2、1]、[3、2、1]、[4、3、2、1]]の数サブリスト：16

于 2020-04-03T21:06:05.427 に答える
0

私はその機能に出くわしたことがなかったので、more_itertools.powersetそれを使用することをお勧めします。また、からの出力のデフォルトの順序を使用しないことをお勧めします。代わりに、位置間の距離itertools.combinationsを最小化し、距離が大きいアイテムの上/前に、位置間の距離が短いアイテムのサブセットを並べ替えます。

itertoolsレシピページはそれが使用することを示していますchain.from_iterable

  • ここで、二項係数rの下部の標準表記と一致することに注意してください。これは通常、数学のテキストや電卓で参照されます（「nChooser」）。sn
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

ここでの他の例は[1,2,3,4]、2タプルが「辞書式」順序でリストされるような方法でのべき集合を示しています（数値を整数として出力する場合）。数字の間の距離（つまり差）を書くと、それは私のポイントを示しています：

12 ⇒ 1
13 ⇒ 2
14 ⇒ 3
23 ⇒ 1
24 ⇒ 2
34 ⇒ 1

サブセットの正しい順序は、次のように、最初に最小距離を「使い果たす」順序である必要があります。

12 ⇒ 1
23 ⇒ 1
34 ⇒ 1
13 ⇒ 2
24 ⇒ 2
14 ⇒ 3

ここで数字を使用すると、この順序は「間違った」ように見えますが、たとえば文字を考えてみると、この順序でべき集合["a","b","c","d"]を取得するのになぜこれが役立つのかが明確になります。

ab ⇒ 1
bc ⇒ 1
cd ⇒ 1
ac ⇒ 2
bd ⇒ 2
ad ⇒ 3

この効果は、項目が多いほど顕著になります。私の目的では、べき集合のインデックスの範囲を意味のある形で記述できるかどうかに違いがあります。

（組み合わせ論におけるアルゴリズムの出力順序については、グレイコードなどで書かれていることがたくさんありますが、副次的な問題ではないと思います）。

私は実際に、この高速整数パーティションコードを使用して値を適切な順序で出力するかなり複雑なプログラムを作成しましたが、その後、次more_itertools.powersetのようにその関数を使用するだけで問題がないことを発見しました。

from more_itertools import powerset
from numpy import ediff1d

def ps_sorter(tup):
    l = len(tup)
    d = ediff1d(tup).tolist()
    return l, d

ps = powerset([1,2,3,4])

ps = sorted(ps, key=ps_sorter)

for x in ps:
    print(x)

⇣</p> 

()
(1,)
(2,)
(3,)
(4,)
(1, 2)
(2, 3)
(3, 4)
(1, 3)
(2, 4)
(1, 4)
(1, 2, 3)
(2, 3, 4)
(1, 2, 4)
(1, 3, 4)
(1, 2, 3, 4)

べき集合をうまく印刷する、より複雑なコードをいくつか書きました（ここに含まれていないきれいな印刷関数については、リポジトリを参照してください：、、、print_partitions）。print_partitions_by_lengthpprint_tuple

これはすべて非常に単純ですが、パワーセットのさまざまなレベルに直接アクセスできるコードが必要な場合は、それでも役立つ可能性があります。

from itertools import permutations as permute
from numpy import cumsum

# http://jeromekelleher.net/generating-integer-partitions.html
# via
# https://stackoverflow.com/questions/10035752/elegant-python-code-for-integer-partitioning#comment25080713_10036764

def asc_int_partitions(n):
    a = [0 for i in range(n + 1)]
    k = 1
    y = n - 1
    while k != 0:
        x = a[k - 1] + 1
        k -= 1
        while 2 * x <= y:
            a[k] = x
            y -= x
            k += 1
        l = k + 1
        while x <= y:
            a[k] = x
            a[l] = y
            yield tuple(a[:k + 2])
            x += 1
            y -= 1
        a[k] = x + y
        y = x + y - 1
        yield tuple(a[:k + 1])

# https://stackoverflow.com/a/6285330/2668831
def uniquely_permute(iterable, enforce_sort=False, r=None):
    previous = tuple()
    if enforce_sort: # potential waste of effort (default: False)
        iterable = sorted(iterable)
    for p in permute(iterable, r):
        if p > previous:
            previous = p
            yield p

def sum_min(p):
    return sum(p), min(p)

def partitions_by_length(max_n, sorting=True, permuting=False):
    partition_dict = {0: ()}
    for n in range(1,max_n+1):
        partition_dict.setdefault(n, [])
        partitions = list(asc_int_partitions(n))
        for p in partitions:
            if permuting:
                perms = uniquely_permute(p)
                for perm in perms:
                    partition_dict.get(len(p)).append(perm)
            else:
                partition_dict.get(len(p)).append(p)
    if not sorting:
        return partition_dict
    for k in partition_dict:
        partition_dict.update({k: sorted(partition_dict.get(k), key=sum_min)})
    return partition_dict

def print_partitions_by_length(max_n, sorting=True, permuting=True):
    partition_dict = partitions_by_length(max_n, sorting=sorting, permuting=permuting)
    for k in partition_dict:
        if k == 0:
            print(tuple(partition_dict.get(k)), end="")
        for p in partition_dict.get(k):
            print(pprint_tuple(p), end=" ")
        print()
    return

def generate_powerset(items, subset_handler=tuple, verbose=False):
    """
    Generate the powerset of an iterable `items`.

    Handling of the elements of the iterable is by whichever function is passed as
    `subset_handler`, which must be able to handle the `None` value for the
    empty set. The function `string_handler` will join the elements of the subset
    with the empty string (useful when `items` is an iterable of `str` variables).
    """
    ps = {0: [subset_handler()]}
    n = len(items)
    p_dict = partitions_by_length(n-1, sorting=True, permuting=True)
    for p_len, parts in p_dict.items():
        ps.setdefault(p_len, [])
        if p_len == 0:
            # singletons
            for offset in range(n):
                subset = subset_handler([items[offset]])
                if verbose:
                    if offset > 0:
                        print(end=" ")
                    if offset == n - 1:
                        print(subset, end="\n")
                    else:
                        print(subset, end=",")
                ps.get(p_len).append(subset)
        for pcount, partition in enumerate(parts):
            distance = sum(partition)
            indices = (cumsum(partition)).tolist()
            for offset in range(n - distance):
                subset = subset_handler([items[offset]] + [items[offset:][i] for i in indices])
                if verbose:
                    if offset > 0:
                        print(end=" ")
                    if offset == n - distance - 1:
                        print(subset, end="\n")
                    else:
                        print(subset, end=",")
                ps.get(p_len).append(subset)
        if verbose and p_len < n-1:
            print()
    return ps

例として、コマンドライン引数として文字列を受け取るCLIデモプログラムを作成しました。

python string_powerset.py abcdef

⇣</p> 

a, b, c, d, e, f

ab, bc, cd, de, ef
ac, bd, ce, df
ad, be, cf
ae, bf
af

abc, bcd, cde, def
abd, bce, cdf
acd, bde, cef
abe, bcf
ade, bef
ace, bdf
abf
aef
acf
adf

abcd, bcde, cdef
abce, bcdf
abde, bcef
acde, bdef
abcf
abef
adef
abdf
acdf
acef

abcde, bcdef
abcdf
abcef
abdef
acdef

abcdef
于 2020-06-22T18:56:42.120 に答える
0

これが私の解決策です。これは（概念的には）lmiguelvargasfの解決策と似ています。

-[数学項目]定義により、べき集合には空の集合-[個人の趣向]が含まれていること、また、凍結集合を使用するのは好きではないと言わせてください。

したがって、入力はリストであり、出力はリストのリストになります。関数はもっと早く閉じることができますが、私はべき集合の要素が辞書式順序であるのが好きです。それは本質的にうまく意味します。

def power_set(L):
    """
    L is a list.
    The function returns the power set, but as a list of lists.
    """
    cardinality=len(L)
    n=2 ** cardinality
    powerset = []
    
    for i in range(n):
        a=bin(i)[2:]
        subset=[]
        for j in range(len(a)):
            if a[-j-1]=='1':
                subset.append(L[j])
        powerset.append(subset)
        
    #the function could stop here closing with
    #return powerset

    powerset_orderred=[]
    for k in range(cardinality+1):
        for w in powerset:
            if len(w)==k:
                powerset_orderred.append(w)
        
    return powerset_orderred
于 2020-12-11T16:28:45.357 に答える
-2 
def powerset(some_set):
    res = [(a,b) for a in some_set for b in some_set]
    return res
于 2020-11-06T15:38:10.267 に答える