Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from __future__ import nested_scopes, print_function
- import bisect
- import numpy
- from collections import namedtuple
- from itertools import combinations
- Num = namedtuple("Num", ["value", "i"])
- # This implements the Karmarkar-Karp heuristic for partitioning a set
- # in two, i.e. into two disjoint subsets s.t. their sums are
- # approximately equal. It produces only one result, in O(N log N)
- # time. A remarkable property is that it loves large sets: in
- # general, the more numbers you feed it, the better it does.
- def partition(nums):
- nums = sorted(Num(num, i) for i, num in enumerate(nums))
- N = len(nums)
- connections = [[] for _ in range(N)]
- while len(nums) > 1:
- bigger = nums.pop()
- smaller = nums.pop()
- # Force these into different sets, by "drawing a
- # line" connecting them.
- i, j = bigger.i, smaller.i
- connections[i].append(j)
- connections[j].append(i)
- diff = bigger.value - smaller.value
- assert diff >= 0
- bisect.insort(nums, Num(diff, i))
- # Now sorted contains only 1 element x, and x.value is
- # the difference between the subsets' sums.
- # Theorem: The connections matrix represents a spanning tree
- # on the set of index nodes, and any tree can be 2-colored.
- # 2-color this one (with "colors" 0 and 1).
- index2color = [None] * N
- def color(i, c):
- if index2color[i] is not None:
- assert index2color[i] == c
- return
- index2color[i] = c
- for j in connections[i]:
- color(j, not c)
- color(0, 0)
- # Partition the indices by their colors.
- subsets = [[], []]
- for i, color in enumerate(index2color):
- subsets[color].append(i)
- return subsets
- def two_sort_optimal(bricks):
- indexes_1, indexes_2 = partition(bricks)
- tower_1 = [bricks[x] for x in indexes_1]
- tower_2 = [bricks[x] for x in indexes_2]
- return tower_1, tower_2
- def tower_greed(bricks, n_tower):
- bricks.sort(reverse=True)
- towers = [[] for _ in range(n_tower)]
- heights = [0] * n_tower
- for brick in bricks:
- lowest = heights.index(min(heights))
- towers[lowest].append(brick)
- heights[lowest] += brick
- return towers
- def tower_build(bricks, n_tower):
- if n_tower == 2:
- return two_sort_optimal(bricks)
- towers = tower_greed(bricks, n_tower)
- heights = [sum(i) for i in towers]
- print("First pass stdev:", numpy.std(heights))
- def reshuffle(tower_1, tower_2):
- old_diff = abs(sum(tower_1) - sum(tower_2))
- new_tower_1, new_tower_2 = two_sort_optimal(tower_1 + tower_2)
- new_diff = abs(sum(new_tower_1) - sum(new_tower_2))
- if old_diff <= new_diff:
- return False
- tower_1[:] = new_tower_1
- tower_2[:] = new_tower_2
- return True
- while True:
- towers.sort(key=sum)
- shuffles = [reshuffle(t1, t2) for t1, t2 in combinations(towers, 2)]
- if not any(shuffles):
- break
- return towers
- if __name__ == "__main__":
- with open('buildingSite3.txt') as f:
- numberTowers = 23
- bricks = [int(line.strip()) for line in f]
- towers = tower_build(bricks,numberTowers)
- heights = [sum(i) for i in towers]
- print("Final stdev:", numpy.std(heights))
- print(towers)
- print(*map(sum, towers))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement