fork download
copy 
  1. #
  2. # Lecture Notes: Backtracking.
  3. #
  4. # Elements of combinatorics.
  5. #
  6. # Permutation.
  7. # Combinations.
  8. # Arrangements.
  9. # Partitions Set.
  10. # Partitions Integer.
  11. # Subsets.
  12. #
  13. # Product Cartesian MxM.
  14. # Product Cartesian AxBx..xZ.
  15. def perm1(n):
  16.     def ok(level):
  17.         for i in range(1, level):
  18.             if stack[level] == stack[i]:
  19.                 return False
  20.         return True
  21.     def back(level):
  22.         if level == n+1:
  23.             print(stack)
  24.         else:
  25.             for i in range(1, n+1):
  26.                 stack[level] = i
  27.                 if ok(level):
  28.                     back(level+1)
  29.     n = n
  30.     stack = [0] * (n+1)
  31.     back(1)
  32. perm1(4)
  33.  
  34. print("Permutations2:")
  35. def perm():
  36.     def accepted(level):
  37.         for i in range(1, level):
  38.             if stack[i] == stack[level]:
  39.                 return False
  40.         return True
  41.     def solve(level):
  42.         for i in range(1, n+1):
  43.             stack[level] = i
  44.             if accepted(level) is True:
  45.                if level == n:
  46.                   for i in range(1,n+1):
  47.                       print(stack[i], end=" ")
  48.                   print()
  49.                else:
  50.                   solve(level+1)
  51.     n = 3
  52.     stack = [0] * (n+1)
  53.     solve(1)
  54. perm()
  55.  
  56. print("Combinations:")
  57. print()
  58.  
  59. def comb(n,k):
  60.     def accepted(level):
  61.         for i in range(1, level):
  62.             if stack[i] == stack[level]:
  63.                 return False
  64.         return True
  65.     def solve(level):
  66.         for i in range(stack[level-1]+1, n+1):
  67.             stack[level] = i
  68.             if accepted(level) is True:
  69.                if level == k:
  70.                   for i in range(1,k+1):
  71.                       print(stack[i], end=" ")
  72.                   print()
  73.                else:
  74.                   solve(level+1)
  75.     n = n
  76.     k = k
  77.     stack = [0] * (n+1)
  78.     solve(1)
  79. comb(4,2)
  80.  
  81. print()
  82.  
  83. print("Arrangements:")
  84. def arrange(n,k):
  85.     def accepted(level):
  86.         for i in range(1, level):
  87.             if stack[i] == stack[level]:
  88.                 return False
  89.         return True
  90.     def solve(level):
  91.         for i in range(1, n+1):
  92.             stack[level] = i
  93.             if accepted(level) is True:
  94.                if level == k:
  95.                   for i in range(1,k+1):
  96.                       print(stack[i], end=" ")
  97.                   print()
  98.                else:
  99.                   solve(level+1)
  100.     n = n
  101.     k = k
  102.     stack = [0] * (n+1)
  103.     solve(1)
  104. arrange(4,2)
  105.  
  106. print()
  107.  
  108. print("Partitions of a set")
  109. def partSet():
  110.     def getMax(level):
  111.         max = 0
  112.         for i in range(1, level):
  113.             if stack[i]>max:
  114.                 max = stack[i]
  115.         return max
  116.     def display_solution():
  117.         max = getMax(n+1)
  118.         for i in range(1, max+1):
  119.             for j in range(1,n+1):
  120.                 if stack[j]==i:
  121.                     print(j, end="")
  122.             print("*", end="")
  123.         print()
  124.     def solve(level):
  125.         for i in range(1, getMax(level)+1+1):
  126.             stack[level] = i
  127.             if level == n:
  128.                 display_solution()
  129.             else:
  130.                 solve(level+1)
  131.  
  132.     n = 3
  133.     stack = [0] * (n+1)
  134.     solve(1)
  135. partSet()
  136.  
  137. print()
  138. print("Partitions of an integer")
  139. def partInt():
  140.     def solve(level):
  141.         global sum
  142.         if sum == n:
  143.             for i in range(1, level):
  144.                 print(stack[i], end=" ")
  145.             print()
  146.         else:
  147.             stack[level] = 0
  148.             while stack[level]+sum<n:
  149.                 stack[level]+=1
  150.                 sum += stack[level]
  151.                 solve(level+1)
  152.                 sum -= stack[level]
  153.  
  154.     n = 3
  155.     global sum
  156.     sum = 0
  157.     stack = [0] * (n+1)
  158.     solve(1)
  159. partInt()
  160.  
  161. print()
  162. print("Subsets")
  163. def subsets(k):
  164.     def solution(level):
  165.         for i in range(1,level+1):
  166.             print(stack[i], end=" ")
  167.         print()
  168.     def solve(level):
  169.         if level<=n:
  170.             for i in range(stack[level-1]+1, n+1):
  171.                 stack[level] = i
  172.                 solution(level)
  173.                 solve(level+1)
  174.     n = k
  175.     stack = [0] * (n+1)
  176.     solve(1)
  177. subsets(3)
  178.  
  179. print("Product Cartesian")
  180.  
  181. def Cartesian(k):
  182.     def solve(level):
  183.         if level == 3:
  184.             print("(",end="")
  185.             for i in range(1, 3):
  186.                 print(stack[i], end=",")
  187.             print("\b)",end="")
  188.  
  189.         else:
  190.             for i in range(1, m+1):
  191.                 stack[level] = i
  192.                 solve(level+1)
  193.     m = k
  194.     stack = [0] * (m+1)
  195.     print("{",end="")
  196.     solve(1)
  197.     print("}")
  198.  
  199. Cartesian(5)
  200.  
  201. print("Product Cartesian AxB")
  202.  
  203. def CartesianAB(a,b):
  204.     def solve(level):
  205.         if level == n+1:
  206.             print("(",end="")
  207.             for i in range(1, n+1):
  208.                 print(stack[i], end=",")
  209.             print("\b)",end="")
  210.  
  211.         else:
  212.             stack[level] = 0
  213.             while stack[level]<M[level]:
  214.                 stack[level]+=1
  215.                 solve(level+1)
  216.     M = [0,a,b]
  217.     n = len(M)-1
  218.     stack = [0] * (n+1)
  219.     print("{",end="")
  220.     solve(1)
  221.     print("}")
  222.  
  223. CartesianAB( 2, 3 )
  224.  
  225. def fn():
  226.     def subsets(working_set, level, n):
  227.         if level == n:
  228.             s = {i for i in working_set if working_set[i] == 1}
  229.             solutions.append(s)
  230.         else:
  231.             level+=1
  232.             for i in [0,1]:
  233.                 working_set[level] = i
  234.                 subsets(working_set,level,n)
  235.     n = 3
  236.     solutions = []
  237.     subsets({},0,n)
  238.     print(solutions)
  239. fn()
Success #stdin #stdout 0.03s 9548KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[0, 1, 2, 3, 4]
[0, 1, 2, 4, 3]
[0, 1, 3, 2, 4]
[0, 1, 3, 4, 2]
[0, 1, 4, 2, 3]
[0, 1, 4, 3, 2]
[0, 2, 1, 3, 4]
[0, 2, 1, 4, 3]
[0, 2, 3, 1, 4]
[0, 2, 3, 4, 1]
[0, 2, 4, 1, 3]
[0, 2, 4, 3, 1]
[0, 3, 1, 2, 4]
[0, 3, 1, 4, 2]
[0, 3, 2, 1, 4]
[0, 3, 2, 4, 1]
[0, 3, 4, 1, 2]
[0, 3, 4, 2, 1]
[0, 4, 1, 2, 3]
[0, 4, 1, 3, 2]
[0, 4, 2, 1, 3]
[0, 4, 2, 3, 1]
[0, 4, 3, 1, 2]
[0, 4, 3, 2, 1]
Permutations2:
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1 
Combinations:

1 2 
1 3 
1 4 
2 3 
2 4 
3 4 

Arrangements:
1 2 
1 3 
1 4 
2 1 
2 3 
2 4 
3 1 
3 2 
3 4 
4 1 
4 2 
4 3 

Partitions of a set
123*
12*3*
13*2*
1*23*
1*2*3*

Partitions of an integer
1 1 1 
1 2 
2 1 
3 

Subsets
1 
1 2 
1 2 3 
1 3 
2 
2 3 
3 
Product Cartesian
{(1,1,)(1,2,)(1,3,)(1,4,)(1,5,)(2,1,)(2,2,)(2,3,)(2,4,)(2,5,)(3,1,)(3,2,)(3,3,)(3,4,)(3,5,)(4,1,)(4,2,)(4,3,)(4,4,)(4,5,)(5,1,)(5,2,)(5,3,)(5,4,)(5,5,)}
Product Cartesian AxB
{(1,1,)(1,2,)(1,3,)(2,1,)(2,2,)(2,3,)}
[set(), {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}]
https://ideone.com/oqRntz
Partitions.Comb.Arrange.Perm.ProductCartesian.Subsets
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!