題目描述
有一個集合S，要求列印出其所有子集，子集元素用逗號隔開，其中集合S本身和空集NULL都認為是集合S的子集，例如，有一個集合S，它的內容為“S={"A", "B", "C"}”，那么該集合S的所有子集為“A,B,C”、“A,B”、“AC”、“BC”、“A”、“B”、“C”、“NULL”，
解題思路
先要思考如何將集合求子集這個操作與二進制聯系起來，首先可以確定，集合S、空集以及單個元素的子集很容易確定，不用與二進制關聯也可以輕松得到，剩下的子集的求解思路就是某個元素不在子集中時，剩下的所有元素為一個子集，然后依次是某兩個元素不在子集中時剩下的元素為一個子集，以此類推，就可以得到所有子集，聯想二進制的特點，一個位元位上要么是0，要么就是1，那么可以使用位元位代表每個元素，它的值為1時表示此元素在子集中，值為0時表示此元素不在子集中，然后根據“題目”中的例子，將集合S的所有子集用二進制表示出來，然后寫出對應的十進制就可以看到對應的規律了，
| 子集 | 二進制 | 十進制 |
|---|---|---|
| A,B,C | 0b111 | 7 |
| A,B | 0b110 | 6 |
| A,C | 0b101 | 5 |
| A | 0b100 | 4 |
| B,C | 0b011 | 3 |
| B | 0b010 | 2 |
| C | 0b001 | 1 |
| NULL | 0b000 | 0 |
解題代碼
def print_sub(val, s):
# 獲取對應位數的二進制位字串
bin_str = bin(val).replace('0b', '').rjust(len(s), '0')
idx = 0
is_null = True
while idx < len(s):
# 如果該位元位為1，則列印對應的元素
if bin_str[idx] == '1':
if not is_null:
print(',', end='')
is_null = False
print(s[idx], end='')
idx += 1
if is_null:
print('NULL', end='')
print(';')
def func(s):
# 使用二進制的方式得到所有元素都存在時的二進制表示方式對應的十進制數
# 當然，也可以使用其他方式得到這個值
val = 0
for i in range(len(s)):
val |= (1 << i)
# 遍歷并列印每一個子集
while val >= 0:
print_sub(val, s)
val -= 1
if __name__ == '__main__':
collection = ['A', 'B', 'C', 'D']
func(collection)
輸出：
A,B,C,D;
A,B,C;
A,B,D;
A,B;
A,C,D;
A,C;
A,D;
A;
B,C,D;
B,C;
B,D;
B;
C,D;
C;
D;
NULL;
總結
求集合的子集，在Python中itertools.combinations也可以做到，或者自己撰寫另外的演算法，但是就此題而言，相當于是提供了另一種解題思路或者說是二進制的一種操作方法，可以參考下，
題目及解題演算法來自：書籍《Python程式員面試寶典》，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/234137.html
標籤：其他
上一篇：一致性哈希看這篇就夠了！【轉】
下一篇：ab test壓力測驗