1 """module combinatorics
2
3 Helper module implementing several combinatoric basic methods.
4 """
5 from dsc_suite.tools.math import fak
9 """ class EnumerativeCombinatorics() - basic EC functionality
10
11 This class implements basic enumerative combinatorics functionality, such
12 as permutations, combinations and partitions, since they are necessary for
13 my optimization investigations of data structures.
14
15 Most methods are static (class) methods. Basically, this class is used to
16 encapsulated conjoined functions.
17 """
18
19
20
21
22
23 @staticmethod
25 """ permute(element_list) -> permutation_list
26
27 element_list ... list of elements which are used
28 permutation_list ... all possible permutations of elements
29
30 Generates the PERMUTATION WITHOUT REPETITION of all elements given in
31 the element_list, which are used once. The resulting permutation_list
32 is a list including the n = len(element_list)! different sequences.
33
34 ATTENTION: This permutation implementation delivers a different order
35 than permute and get_permutation!
36 """
37 def p(permutation, elements, result):
38 if len(elements) == 0:
39 result.append(permutation)
40 else:
41 for e in elements:
42 temp = list(elements)
43 temp.remove(e)
44 if elements.index(e)%2 == 1:
45 temp.reverse()
46 temp2 = list(permutation)
47 temp2.append(e)
48 p(temp2, temp, result)
49
50 permutation_list = []
51 p([], list(element_list), permutation_list)
52 return permutation_list
53
54 @staticmethod
56 """ permute(element_list) -> permutation_list
57
58 element_list -- list of elements which are used
59 permutation_list -- all possible permutations of elements
60
61 Generates the PERMUTATION WITHOUT REPETITION of all elements given in
62 the element_list, which are used once. The resulting permutation_list
63 is a list including the n = len(element_list)! different sequences.
64 Obtains the same ordering of permutations as the get_permutation
65 method.
66
67 """
68 def p(processed, unprocessed):
69 if len(unprocessed) == 1:
70 return [processed + unprocessed]
71 else:
72 temp = []
73 for i in range(len(unprocessed)):
74 temp.extend(p(processed + [unprocessed[i]], unprocessed[:i]+unprocessed[i+1:]))
75 return temp
76
77 permutation_list = p([], element_list)
78 return permutation_list
79
80 @staticmethod
82 """ get_permutation(element_list, number) -> permutation
83
84 element_list -- list of elements which are used
85 number -- number of permutation (implementation inherent order)
86 permutation -- resulting permutation of elements
87
88 Generates the PERMUTATION WITHOUT REPETITION of the elements
89 given in the element_list, which are used once. The number of
90 all possible permutations is fak(len(element_list)), thus the
91 range of number should be: 0 <= number < fak(len(element_list)).
92 Validity of number is not tested. This should be done in the
93 calling function (e.g., assert(number) < fak(len(element_list))),
94 otherwise this test would be executed in every recursion step.
95
96 Result equal to: permute(element_list)[number]
97
98 """
99 if len(element_list) == 1:
100 return element_list
101 else:
102 next_range = fak(len(element_list)-1)
103 element_pos = number // next_range
104 return [element_list[element_pos]] \
105 + EnumerativeCombinatorics.get_permutation(element_list[:element_pos]+element_list[element_pos+1:],
106 number % next_range)
107
108 @staticmethod
110 """Calculate number of possible permutations."""
111 return fak(len(element_list))
112
113 @staticmethod
115 """Calculate number of possible variations."""
116 return len(element_list)**variation_length
117
118 @staticmethod
119 - def vary(element_list, variation_length):
120 """ vary(element_list, variation_length) -> variation_list
121
122 element_list ... list of elements which are used
123 variation_length ... length of resulting variation
124 variation_list ... result of variation
125
126 Generates the VARIATION WITH REPETITION of the given length. Therefore
127 on every place every given element can be used. The order is important.
128 Finaly, the variation_list contains len(element_list)**variation_length
129 variations.
130 """
131 if variation_length < 1:
132 return []
133 else:
134 variation_list = [[x] for x in element_list]
135
136 for i in range(variation_length-1):
137 temp = []
138 for element in element_list:
139 for variation in variation_list:
140 temp.append([element] + variation)
141 variation_list = temp
142
143 return variation_list
144
145 @staticmethod
147 """ Generate variation and return the specified element.
148
149 element_list - list of elements which are used
150 variation_length - length of resulting variation
151 number - number of wanted variation
152 variation - resulting variation
153
154 Generates one VARIATION WITH REPETITION of the given length and
155 elements at position number.
156 Result equal to: vary(element_list, variation_length)[number].
157
158 """
159 base = len(element_list)
160 variation = []
161 for i in range(variation_length-1, -1, -1):
162 variation.append(element_list[number//base**i])
163 number = number % base**i
164 return variation
165
166
167