partitioning_problem.py

import random

# A group of N integer numbers need to be divided fairly into K subgroups.
# A fair division is that the max of the sums of K subgroups is minimal?

# greedy algorithm
def partitioning(n, k):
    a = sum(n) / k
    nums = sorted(n, reverse=True)
    groups = []
    gsums = []

    for _ in range(k):
        group = [nums.pop(0)]
        groups.append(group)
        gsum = group[0]

        while True:
            gnext_num = 0
            gnext_i = -1
            for i, num in enumerate(nums):
                if gsum + num <= a and num > gnext_num:
                    gnext_num = num
                    gnext_i = i

            if gnext_i > -1:
                gsum += gnext_num
                group.append(gnext_num)
                nums.pop(gnext_i)
            else:
                break

        gsums.append(gsum)

    for num in nums:
        i = gsums.index(min(gsums))
        groups[i].append(num)
        gsums[i] += num

    return groups

def partitioning_random(n, k, count):
    group_min = sum(n)
    groups_min = None
    for i in range(count):
        numbers = n[:] + [-1] * (k - 1)
        random.shuffle(numbers)

        groups = []
        group = []
        gsum_max = 0
        gsum = 0

        for num in numbers + [-1]:
            if num == -1:
                groups.append(group)
                group = []
                if gsum > gsum_max:
                    gsum_max = gsum
                gsum = 0
            else:
                gsum += num
                group.append(num)

        if gsum_max < group_min:
            group_min = gsum_max
            groups_min = groups

    return groups_min


class partitioning_ga():

    def __init__(self, numbers, group_num, count):
        self.count = count
        self.groups_min = sum(numbers)
        self.population = self.gen_population(numbers, group_num, count)

    def evolve(self, retain_rate=0.2, random_select_rate=0.5, mutation_rate=0.01):
        parents = self.selection(retain_rate, random_select_rate)
        self.crossover(parents)
        self.mutation(mutation_rate)

        fitness, chromosome = self._result()
        if fitness < self.groups_min:
            self.groups_min = fitness
            self.chromosome = chromosome[:]
            print('max group:', fitness)

    def gen_chromosome(self, numbers, group_num):
        chromosome = numbers[:] + [-1] * (group_num - 1)
        random.shuffle(chromosome)
        return chromosome

    def gen_population(self, numbers, group_num, count):
        return [self.gen_chromosome(numbers, group_num) for i in range(count)]

    def fitness(self, chromosome):
        group_max = 0

        for group in self.decode(chromosome):
            group_sum = sum(group)

            if group_sum > group_max:
                group_max = group_sum

        return group_max

    def selection(self, retain_rate, random_select_rate):
        graded = [(self.fitness(chromosome), chromosome) for chromosome in self.population]
        graded = [x[1] for x in sorted(graded)]
        retain_length = int(len(graded) * retain_rate)
        parents = graded[:retain_length]

        for chromosome in graded[retain_length:]:
            if random.random() < random_select_rate:
                parents.append(chromosome)

        return parents

    def crossover(self, parents):
        # self crossover
        children = []
        target_count = len(self.population) - len(parents)

        while len(children) < target_count:
            child = parents[random.randint(0, len(parents) - 1)][:]

            pos1 = random.randint(0, len(child) - 1)
            pos2 = random.randint(0, len(child) - 1)
            if pos1 == -1 or pos2 == -1:
                continue

            pos1, pos2 = sorted([pos1, pos2])
            for pos in range(pos1 + 1, pos2):
                if child[pos] == -1:
                    # in different group, swap two numbers
                    child[pos2], child[pos1] = child[pos1], child[pos2]
                    children.append(child)
                    break

        self.population = parents + children

    def mutation(self, rate):
        for i in range(len(self.population)):
            if random.random() < rate:
                chromosome = self.population[i]

                pos1 = random.randint(0, len(chromosome) - 1)
                pos2 = random.randint(0, len(chromosome) - 1)

                if pos1 != pos2:
                    chromosome[pos2], chromosome[pos1] = chromosome[pos1], chromosome[pos2]

    def decode(self, chromosome):
        groups = []
        group = []

        for num in chromosome + [-1]:
            if num == -1:
                groups.append(group)
                group = []
            else:
                group.append(num)

        return groups

    def _result(self):
        graded = [(self.fitness(chromosome), chromosome) for chromosome in self.population]
        graded = sorted(graded)
        return graded[0]

    def result(self):
        return self.decode(self.chromosome)

if __name__ == "__main__":
    ga = partitioning_ga([6, 6, 5, 2, 1, 1], 3, 10)
    for x in range(50):
         ga.evolve()

    print(ga.result())
    print(partitioning([6, 6, 5, 2, 1, 1], 3))

    ga = partitioning_ga([13, 41, 9, 21, 12, 36, 33, 35, 46, 29, 18, 11, 36, 6, 29, 32, 43, 5, 49, 33], 6, 100)
    for x in range(500):
        print('cycle: ', x)
        ga.evolve()

    result = ga.result()
    print(result, "Max:", max([sum(g) for g in result]))

    result = partitioning([13, 41, 9, 21, 12, 36, 33, 35, 46, 29, 18, 11, 36, 6, 29, 32, 43, 5, 49, 33], 6)
    print(result, "Max:", max([sum(g) for g in result]))

    #result = partitioning_random([13, 41, 9, 21, 12, 36, 33, 35, 46, 29, 18, 11, 36, 6, 29, 32, 43, 5, 49, 33], 6, 1000000)
    #print(result, "Max:", max([sum(g) for g in result]))

    result = [[36, 5, 49], [29, 29, 32], [46, 43], [36, 35, 18], [12, 33, 11, 33], [13, 41, 9, 21, 6]]
    print(result, "Max:", max([sum(g) for g in result]))
    exit(0)


    print(partitioning([13, 41, 9, 21, 12, 36, 33, 35, 46, 29, 18, 11, 36, 6, 29, 32, 43, 5, 49, 33], 6))
    # 最优是： [[36, 5, 49], [29, 29, 32], [46, 43], [36, 35, 18], [12, 33, 11, 33], [13, 41, 9, 21, 6]]
    # 参考： https://gist.github.com/ruoyu0088/d100e678718572f8d1378be8704e70fd
    #        https://developers.google.com/optimization/cp/cp_solver

    print(partitioning([12, 11, 10, 9, 8, 7, 3, 2], 4))
    print(partitioning([6, 6, 5, 2, 1, 1], 2))
    print(partitioning([6, 6, 5, 2, 1, 1], 3))
    print(partitioning([6, 6, 5, 2, 1, 1], 4))
    print(partitioning([9, 2, 1], 2))
    print(partitioning([6, 5, 3, 2, 2], 2))
    print(partitioning([8, 5, 5, 2, 2, 6], 5))

    for i in range(100):
        n = random.sample(range(1,100), 7)
        print('N =', n)
        for k in range(2, 5):
            result = partitioning(n, k)
            print('    K =', k, ": ", result, 'Avg:', sum(n) / k, 'Max: ', max([sum(g) for g in result]))