fork download
copy 
  1. # Generating the subsets of a Set = { 1, 2, 3 }
  2. # Sonata Alla Turca no 11 in A major K 331
  3. def main():
  4.     n = 3
  5.     stack = [0] * (n+1);
  6.     stack2 = [0] * (n+1)
  7.  
  8.     #method 0 using Backtracking iteratively
  9.     def init():
  10.         stack2[summit] = -1
  11.  
  12.     def succ():
  13.         if stack2[ summit ] < 1:
  14.             stack2[ summit ]+=1
  15.             return 1
  16.         return 0
  17.  
  18.     def valid():
  19.         return 1
  20.  
  21.     def sol():
  22.         return summit == n
  23.  
  24.     def print_solution():
  25.         for i in range( 1, n + 1 ):
  26.             if stack2[ i ] == 1:
  27.                 print(i, end=" ")
  28.         print()
  29.  
  30.     def bk():
  31.         global summit
  32.         summit = 1
  33.         init()
  34.  
  35.         while summit > 0:
  36.  
  37.             s = 1
  38.             v = 0
  39.             while s and v == 0:
  40.                 s = succ()
  41.                 if s:
  42.                     v = valid()
  43.             if s:
  44.                 if sol() is True:
  45.                     print_solution()
  46.                 else:
  47.                     summit+=1
  48.                     init()
  49.             else:
  50.                 summit-=1
  51.  
  52.     print("method#0 Backtracking iterative")
  53.     bk()
  54.  
  55.     def solution(k):
  56.         for i in range(1, k+1):
  57.             print(stack[i], end = " ")
  58.         print()
  59.  
  60.     #method 1 using Backtracking recursively
  61.     def subsets(k):
  62.         if k<=n:
  63.             for i in range(stack[k-1]+1, n+1):
  64.                 stack[k] = i
  65.                 solution( k )
  66.                 subsets( k + 1 )
  67.  
  68.     print("Method#1 Backtracking recursive")
  69.     subsets(1)
  70.  
  71.     #method 2 based on Bitwise
  72.     def subsets_bitwise(n):
  73.         size = 2**n
  74.         mask = 1
  75.         print("Subsets(%d) = ( "%n,end="")
  76.         for i in range(1, size):
  77.             print("{", end="")
  78.             for j in range(0, n):
  79.                 if (mask<<j)&i:
  80.                     print(j+1, end =",")
  81.             print("\b}", end=" ")
  82.         print(")")
  83.     print("method#3 Bitwise")
  84.     subsets_bitwise(5)
  85.  
  86.     #method 3 based on Elegant List Comprehension
  87.     def subsets_elegant( working_set, level, n ):
  88.         if level == n:
  89.             sol = [k for k in working_set if working_set[k] == 1]
  90.             print(sol)
  91.         else:
  92.             level+=1
  93.             for i in [0,1]:
  94.                 working_set[level] = i
  95.                 subsets_elegant(working_set, level, n)
  96.     print("method#4 (Elegant List Comprehensive)")
  97.     subsets_elegant({},0,n)
  98. main()
  99.  
  100. def gen_sub():
  101.     n = 3
  102.     vec = [0] * (n)
  103.     s = 0
  104.  
  105.     while not (s == n):
  106.         vec[n-1]+=1
  107.         for i in range(n-1,-1,-1):
  108.             if vec[i] > 1:
  109.                 vec[i-1] += 1
  110.                 vec[i] = 0
  111.         s = 0
  112.         for i in range(0,n):
  113.             if vec[i]:
  114.                 print(i+1, end= " ")
  115.             s += vec[i]
  116.         print()
  117.  
  118. print("method#5 Binary Addition")
  119. gen_sub()
  120.  
  121. def gen_subsets_stack():
  122.     stack = []
  123.     n = 3
  124.     stack.append(1)
  125.     while len(stack)>0:
  126.         print(stack)
  127.         if stack[-1] < n:
  128.             stack.append(stack[-1]+1)
  129.         else:
  130.             stack.pop()
  131.             if len(stack)>0:
  132.                 stack[-1]+=1
  133.  
  134. print("method#6 Generating Subsets using a Stack")
  135. gen_subsets_stack()
  136.  
  137. print("method#7 Bk Rec")
  138. def gen_subsets_bk_rec():
  139.     n = 3
  140.     stack = [ 0 ] * (n+1)
  141.     def init(k):
  142.         stack[k]=-1
  143.     def succ(k):
  144.         if stack[k]<1:
  145.             stack[k]+=1
  146.             return 1
  147.         return 0
  148.     def sol(k):
  149.         return k == n
  150.     def printf(k):
  151.         for i in range(1, n+1):
  152.             if stack[i] == 1:
  153.                 print(i, end = " ")
  154.         print()
  155.  
  156.     def bk(k):
  157.         init(k)
  158.         while succ(k):
  159.             if sol(k):
  160.                 printf(k)
  161.             else:
  162.                 bk(k+1)
  163.     bk( 1 )
  164.  
  165. gen_subsets_bk_rec()
  166.  
Success #stdin #stdout 0.03s 9588KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
method#0 Backtracking iterative

3 
2 
2 3 
1 
1 3 
1 2 
1 2 3 
Method#1 Backtracking recursive
1 
1 2 
1 2 3 
1 3 
2 
2 3 
3 
method#3 Bitwise
Subsets(5) = ( {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,} {5,} {1,5,} {2,5,} {1,2,5,} {3,5,} {1,3,5,} {2,3,5,} {1,2,3,5,} {4,5,} {1,4,5,} {2,4,5,} {1,2,4,5,} {3,4,5,} {1,3,4,5,} {2,3,4,5,} {1,2,3,4,5,} )
method#4 (Elegant List Comprehensive)
[]
[3]
[2]
[2, 3]
[1]
[1, 3]
[1, 2]
[1, 2, 3]
method#5 Binary Addition
3 
2 
2 3 
1 
1 3 
1 2 
1 2 3 
method#6 Generating Subsets using a Stack
[1]
[1, 2]
[1, 2, 3]
[1, 3]
[2]
[2, 3]
[3]
method#7 Bk Rec

3 
2 
2 3 
1 
1 3 
1 2 
1 2 3
https://ideone.com/CQbvd3
Seven Methods to Generating the Subsets of a Set
language:
Python 3 (python  3.9.5)
created:
148 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!