fork download
copy 
  1. import numpy as np
  2. ##
  3. ## Partitions: numbers and sets.
  4. ## Arrangements.
  5. ## Combinations.
  6. ## Permutations.
  7. ## Subsets.
  8. ##
  9.  
  10. # iteratively variant
  11. def partitionNum():
  12.     def init():
  13.         stack[level] = 0
  14.     def succ():
  15.         global sum
  16.         if stack[level] < n - sum:
  17.             stack[level] += 1
  18.             return True
  19.         else:
  20.             sum -= stack[level-1]
  21.  
  22.     def valid():
  23.         global sum
  24.         if stack[level] <= n - sum:
  25.            sum += stack[level]
  26.            return True
  27.         return False
  28.  
  29.     def sol():
  30.         return sum == n
  31.  
  32.     def printf():
  33.         global sum
  34.         for i in range(1,level+1):
  35.             print(stack[i], end = " ")
  36.         print()
  37.         sum -= stack[level]
  38.  
  39.     def solve():
  40.         global level
  41.         level = 1
  42.         init()
  43.         while level > 0:
  44.             s = True
  45.             v = False
  46.             while s and not v:
  47.                 s = succ()
  48.                 if s:
  49.                     v = valid()
  50.             if s:
  51.                 if sol():
  52.                     printf()
  53.                 else:
  54.                     level +=1
  55.                     init()
  56.             else:
  57.                 level -= 1
  58.     global sum
  59.     sum = 0
  60.     n = 3
  61.     stack = [0] * (n+1)
  62.     solve()
  63.  
  64. partitionNum()
  65.  
  66. print()
  67.  
  68. def partitionSet():
  69.  
  70.     def init(level):
  71.         stack[level] = 0
  72.  
  73.     def succ(level):
  74.         if stack[level] < stack[level-1] + 1:
  75.             stack[level] += 1
  76.             return True
  77.         return False
  78.  
  79.     def valid(level):
  80.         return True
  81.  
  82.     def sol(level):
  83.         return level == n
  84.  
  85.     def printf(level):
  86.         maxv = np.max(stack)
  87.         for i in range(1, maxv+1):
  88.             print("{", end="")
  89.             for k in range(1, n+1):
  90.                 if i == stack[k]:
  91.                     print(k, end = ",")
  92.             print("\b}", end="")
  93.         print()
  94.  
  95.     def solve(level):
  96.         init(level)
  97.         while succ(level):
  98.             if valid(level):
  99.                 if sol(level):
  100.                     printf(level)
  101.                 else:
  102.                     solve(level+1)
  103.     n = 3
  104.     stack = [0] * (n+1)
  105.     solve(1)
  106.  
  107. partitionSet()
  108.  
  109. print()
  110.  
  111. def arrange():
  112.     def ok(level):
  113.         for i in range(1, level):
  114.             if stack[level] == stack[i]:
  115.                 return False
  116.         return True
  117.  
  118.     def solve(level):
  119.         if level == k + 1:
  120.             for i in range(1, k + 1):
  121.                 print(stack[i], end = " ")
  122.             print()
  123.         else:
  124.             for i in range(1, n + 1):
  125.                 stack[level] = i
  126.                 if ok(level):
  127.                     solve(level+1)
  128.     n = 3
  129.     k = 2
  130.     stack = [0] * (n+1)
  131.     solve(1)
  132. arrange()
  133.  
  134. def comb():
  135.     def ok(level):
  136.         for i in range(1, level):
  137.             if stack[level] == stack[i]:
  138.                 return False
  139.         return True
  140.  
  141.     def solve(level):
  142.         if level == k + 1:
  143.             for i in range(1, k + 1):
  144.                 print(stack[i], end = " ")
  145.             print()
  146.         else:
  147.             for i in range(stack[level-1]+1, n + 1):
  148.                 stack[level] = i
  149.                 if ok(level):
  150.                     solve(level+1)
  151.     n = 3
  152.     k = 2
  153.     stack = [0] * (n+1)
  154.     solve(1)
  155. comb()
  156.  
  157.  
  158. def perm():
  159.     def ok(level):
  160.         for i in range(1, level):
  161.             if stack[level] == stack[i]:
  162.                 return False
  163.         return True
  164.  
  165.     def solve(level):
  166.         if level == n + 1:
  167.             for i in range(1, n + 1):
  168.                 print(stack[i], end = " ")
  169.             print()
  170.         else:
  171.             for i in range(1, n + 1):
  172.                 stack[level] = i
  173.                 if ok(level):
  174.                     solve(level+1)
  175.     n = 3
  176.     stack = [0] * (n+1)
  177.     solve(1)
  178. perm()
  179.  
  180. def _subsets():
  181.     def solve(level):
  182.         if level <= n:
  183.             for i in range(stack[level-1]+1, n+1):
  184.                 stack[level] = i
  185.                 for i in range(1,level+1):
  186.                     print(stack[i], end=" ")
  187.                 print()
  188.                 solve(level+1)
  189.  
  190.     n = 3
  191.     stack = [0] * (n+1)
  192.     solve(1)
  193. _subsets()
  194.  
  195. def subsets():
  196.     def solve(working_set, level, n):
  197.         if level == n:
  198.             s = {k for k in working_set if working_set[k] == 1}
  199.             solutions.append(s)
  200.         else:
  201.             level += 1
  202.             for i in [0,1]:
  203.                 working_set[level] = i
  204.                 solve(working_set, level, n)
  205.     n = 3
  206.     solutions = []
  207.     solve({}, 0, n)
  208.     print(solutions)
  209. subsets()
  210.  
Success #stdin #stdout 0.16s 28788KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 1 1 
1 2 
2 1 
3 

{1,2,3,}
{1,2,}{3,}
{1,3,}{2,}
{1,}{2,3,}
{1,}{2,}{3,}

1 2 
1 3 
2 1 
2 3 
3 1 
3 2 
1 2 
1 3 
2 3 
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1 
1 
1 2 
1 2 3 
1 3 
2 
2 3 
3 
[set(), {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}]
https://ideone.com/Hh4nQT
subsets.part.perm.comb.arrang
language:
Python 3 (python  3.9.5)
created:
1 year 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!