# 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.
47.     def __init__(self, combination):
48.         self.necklaces = []
49.         if not combination:
50.             return
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):
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.
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:
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:
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:
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
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):
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