codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
''' A minimum solution space finder for the "subset sum problem". This gets messy when you try to work with 5 bits and up, maybe pypy can make it work. written for python 3 with inspiration from http://www.reddit.com/r/programming/comments/d1oay/solve_p_vs_np/ ''' from itertools import combinations from pprint import pprint BITS = 3 def build_numbers_of_signed_int(num_of_bits): maximum = 2 ** (num_of_bits - 1) - 1 minimum = -1 - maximum numbers = set(range(minimum, maximum + 1)) numbers.remove(0) # remove the trivial solutions return numbers def get_solution_sets(numbers_space): zero_sets = [] for set_size in range(2, len(numbers_space) + 1): for combo in combinations(numbers_space, set_size): if sum(combo) == 0: zero_sets.append(set(combo)) return zero_sets def minimize_solution_sets(solution_sets): unique_solutions = solution_sets[::] for solution in solution_sets: is_unique = True for other_solution in unique_solutions: if solution.issubset(other_solution) and solution != other_solution: unique_solutions.remove(other_solution) break return unique_solutions def main(): solution_dimensions = [] for bits in range(2,5): signed_ints = build_numbers_of_signed_int(bits) sol_sets = get_solution_sets(signed_ints) min_sets = minimize_solution_sets(sol_sets) solution_dimensions.append((bits, len(sol_sets), len(min_sets))) pprint(sol_sets) pprint(min_sets) pprint(solution_dimensions) if __name__ == "__main__": main()
Private
[
?
]
Run code
Submit