mixmastacopycat

ipnr.py

Sep 16th, 2020
654
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. from itertools import permutations
  2. from dataclasses import dataclass
  3. from collections import deque
  4.  
  5.  
  6. def findPartitionsUtil(arr, index, number, reducedNum, partition_set):
  7.     if reducedNum < 0:
  8.         return
  9.     if reducedNum == 0:
  10.         partition_set.append(arr[:index])
  11.         return
  12.     prev = 1 if (index == 0) else arr[index - 1]
  13.     for k in range(prev, number + 1):
  14.         arr[index] = k
  15.         findPartitionsUtil(arr, index + 1, number, reducedNum - k, partition_set)
  16.  
  17.  
  18. def partition(n):
  19.     partition_set = []
  20.     arr = [0] * n
  21.     findPartitionsUtil(arr, 0, n, n, partition_set)
  22.     return partition_set
  23.  
  24.  
  25. def permute_distinct(pset):
  26.     perm_iset = []
  27.     for i in permutations(pset):
  28.         if list(i) not in perm_iset:
  29.             perm_iset.append(list(i))
  30.     return perm_iset
  31.  
  32.  
  33. def count_elements(lst):
  34.     output = []
  35.     for i in set(lst):
  36.         output.append(lst.count(i))
  37.     return output
  38.  
  39.  
  40. @dataclass
  41. class Cell:
  42.     next: int
  43.     prev: int
  44.  
  45.  
  46. class Sawada:
  47.     def __init__(self, combination):
  48.         self.necklaces = []
  49.         if not combination:
  50.             return
  51.         self.head = 0
  52.         self.key = {}
  53.         combo_set = list(sorted(set(combination)))
  54.         for i in range(len(combo_set)):
  55.             self.key[i] = combo_set[i]
  56.         lst_count = count_elements(combination)
  57.         self.num_map = [i for i in range(len(set(combination)) + 1)]
  58.         self.K = len(set(combination))
  59.         self.N = len(combination)
  60.         self.avail = [Cell(0, 0) for i in range(self.K + 2)]
  61.         self.a = [0] * (self.N + 1)
  62.         self.run = [0] * (self.N + 1)
  63.         self.num = [lst_count[i - 1] for i in range(1, len(set(combination)) + 1)]
  64.         self.num.insert(0, 0)
  65.         self.begin()
  66.         self.necklaces = [[self.key[x] for x in y] for y in self.necklaces]
  67.         self.necklaces.reverse()
  68.  
  69.     def remove(self, i):
  70.         if i == self.head:
  71.             self.head = self.avail[i].next
  72.         p = self.avail[i].prev
  73.         n = self.avail[i].next
  74.         self.avail[p].next = n
  75.         self.avail[n].prev = p
  76.         return self
  77.  
  78.     def add(self, i):
  79.         p = self.avail[i].prev
  80.         n = self.avail[i].next
  81.         self.avail[p].next = i
  82.         self.avail[n].prev = i
  83.         if self.avail[i].prev == self.K + 1:
  84.             self.head = i
  85.         return self
  86.  
  87.     def result(self):
  88.         h = []
  89.         for j in range(1, self.N + 1):
  90.             h.append(self.num_map[self.a[j]] - 1)
  91.         self.necklaces.append(h)
  92.         return self
  93.  
  94.     def gen(self, t, p, s):
  95.         if self.num[self.K] == self.N - t + 1:
  96.             if (self.num[self.K] == self.run[t - p]) & (self.N % p == 0):
  97.                 self.result()
  98.             elif (self.num[self.K] == self.run[t - p]) & (self.N == p):
  99.                 self.result()
  100.             elif self.num[self.K] > self.run[t - p]:
  101.                 self.result()
  102.         elif self.num[1] != self.N - t + 1:
  103.             j = self.head
  104.             s2 = s
  105.             while j >= self.a[t - p]:
  106.                 self.run[s] = t - s
  107.                 self.a[t] = j
  108.  
  109.                 self.num[j] -= 1
  110.                 if self.num[j] == 0:
  111.                     self.remove(j)
  112.  
  113.                 if j != self.K:
  114.                     s2 = t + 1
  115.                 if j == self.a[t - p]:
  116.                     self.gen(t + 1, p, s2)
  117.                 else:
  118.                     self.gen(t + 1, t, s2)
  119.  
  120.                 if self.num[j] == 0:
  121.                     self.add(j)
  122.                 self.num[j] += 1
  123.  
  124.                 j = self.avail[j].next
  125.             self.a[t] = self.K
  126.         return self
  127.  
  128.     def begin(self):
  129.         for j in range(self.K + 1, -1, -1):
  130.             self.avail[j].next = j - 1
  131.             self.avail[j].prev = j + 1
  132.         self.head = self.K
  133.  
  134.         for j in range(1, self.N + 1):
  135.             self.a[j] = self.K
  136.             self.run[j] = 0
  137.  
  138.         self.a[1] = 1
  139.         self.num[1] -= 1
  140.         if self.num[1] == 0:
  141.             self.remove(1)
  142.  
  143.         self.gen(2, 1, 2)
  144.         return self
  145.  
  146.  
  147. def get_necklaces(a):
  148.     return Sawada(a).necklaces
  149.  
  150.  
  151. def get_rotations(a):
  152.     if len(set(a)) == 1 or not a:
  153.         return [a]
  154.     rots = []
  155.     a_deque = deque(a)
  156.     for i in a:
  157.         rots.append(list(a_deque))
  158.         a_deque.rotate(-1)
  159.     return rots
  160.  
  161.  
  162. key_map = {
  163.     1: 'm2',
  164.     2: 'M2',
  165.     3: 'm3',
  166.     4: 'M4',
  167.     5: 'P4',
  168.     6: 'TT',
  169.     7: 'P5',
  170.     8: 'm6',
  171.     9: 'M6',
  172.     10: 'm7',
  173.     11: 'M7',
  174.     12: 'Octave'
  175. }
  176.  
  177.  
  178. def get_partition_set(n):
  179.     # partition_set = [[key_map[x] for x in i] for i in partition(n)]
  180.     partition_set = partition(n)
  181.     pset = []
  182.     for i in partition_set:
  183.         necklaces = get_necklaces(i)
  184.         neck_set = []
  185.         for j in necklaces:
  186.             neck_set.append(get_rotations(j))
  187.         pset.append(neck_set)
  188.     return pset
  189.  
  190.  
  191. def print_partition_set(partition_set, n):
  192.     print("Partitions of " + str(n) + ":")
  193.     for i in range(len(partition_set)):
  194.         print("\tPartition " + str(i+1) + ":")
  195.         for j in range(len(partition_set[i])):
  196.             print("\t\tNecklace " + str(j+1) + ": ")
  197.             for h in partition_set[i][j]:
  198.                 print("\t\t\t" + str(h))
  199.     return
  200.  
  201.  
  202. num = 12
  203.  
  204. part_set = get_partition_set(num)
  205.  
  206. print_partition_set(part_set, num)
  207.  
RAW Paste Data