Package dsc_suite :: Package tools :: Module combinatorics
[hide private]
[frames] | no frames]

Source Code for Module dsc_suite.tools.combinatorics

  1  """module combinatorics 
  2   
  3  Helper module implementing several combinatoric basic methods. 
  4  """ 
  5  from dsc_suite.tools.math import fak 
6 7 ##### ENUMERATIVE COMBINATORICS ################################################ 8 -class EnumerativeCombinatorics(object):
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 #TODO: implement permutation method which allows to calculate 20 # the n-th permutation of an element list directly 21 # this would be a more memory saving solution for the data structures 22 23 @staticmethod
24 - def permute_old(element_list):
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
55 - def permute(element_list):
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
81 - def get_permutation(element_list, number):
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
109 - def get_num_permutations(element_list):
110 """Calculate number of possible permutations.""" 111 return fak(len(element_list)) # n!
112 113 @staticmethod
114 - def get_num_variations(element_list, variation_length):
115 """Calculate number of possible variations.""" 116 return len(element_list)**variation_length # n^k
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
146 - def get_variation(element_list, variation_length, number):
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 #NEXT STEP: combination, variation, permutation with/without repetition 167