Fair partitioning of elements of a list

Question

Given a list of ratings of players, I am required to partition the players (ie ratings) into two groups as fairly as possible. The goal is to minimize the difference between the teams' cumulative rating. There are no constraints as to how I can split the players into the teams (one team can have 2 players and the other team can have 10 players).

For example: [5, 6, 2, 10, 2, 3, 4] should return ([6, 5, 3, 2], [10, 4, 2])

I would like to know the algorithm to solve this problem. Please note I am taking an online programming introductory course, so simple algorithms would be appreciated.

I am using the following code, but for some reason, the online code checker says it is incorrect.

def partition(ratings):
    set1 = []
    set2 =[]
    sum_1 = 0
    sum_2 = 0
    for n in sorted(ratings, reverse=True):
        if sum_1 < sum_2:
            set1.append(n)
            sum_1 = sum_1 + n
        else:
            set2.append(n)
            sum_2 = sum_2 + n
    return(set1, set2)

Update: I contacted the instructors and I was told I should defined another "helper" function inside the function to check all different combinations then I need to check for the minimum difference.

Answer 1

Note: Edited to better handle the case when the sum of all numbers is odd.

Backtracking is a possibility for this problem.

It allows examining all the possibilities recursively, without the need of a large amount of memory.

It stops as soon as an optimal solution is found: sum = 0, where sum is the difference between the sum of elements of set A and the sum of elements of set B. EDIT: it stops as soon sum < 2, to handle the case when the sum of all numbers is odd, i.e. corresponding to a minimum difference of 1. If this global sum is even, the min difference cannot be equal to 1.

It allows to implement a simple procedure of premature abandon:
at a given time, if sum is higher then the sum of all remaining elements (i.e. not placed in A or B) plus the absolute value of current minimum obtained, then we can give up examining the current path, without examining the remaining elements. This procedure is optimized with:

• sort the input data in decreasing order
• A each step, first examine the most probable choice: this allow to go rapidly to a near-optimum solution

Here is a pseudo-code

Initialization:

• sort elements a[]
• Calculate the sum of remaining elements: sum_back[i] = sum_back[i+1] + a[i];
• Set the min "difference" to its maximum value: min_diff = sum_back[0];
• Put a[0] in A -> the index i of examined element is set to 1
• Set up_down = true; : this boolean indicates if we are currently going forward (true) or backward (false)

While loop:

• If (up_down): forward

  • Test premature abandon, with help of sum_back
  • Select most probable value, adjust sum according to this choice
  • if (i == n-1): LEAF -> test if the optimum value is improved and return if the new value is equal to 0 (EDIT: if (... < 2)); go backward
  • If not in a leaf: continue going forward

• If (!updown): backward

  • If we arrive at i == 0 : return
  • If it is the second walk in this node: select the second value, go up
  • else: go down
  • In both cases: recalculate the new sum value

Here is a code, in C++ (Sorry, don't know Python)

#include    <iostream>
#include    <vector>
#include    <algorithm>
#include    <tuple>

std::tuple<int, std::vector<int>> partition(std::vector<int> &a) {
    int n = a.size();
    std::vector<int> parti (n, -1);     // current partition studies
    std::vector<int> parti_opt (n, 0);  // optimal partition
    std::vector<int> sum_back (n, 0);   // sum of remaining elements
    std::vector<int> n_poss (n, 0);     // number of possibilities already examined at position i

    sum_back[n-1] = a[n-1];
    for (int i = n-2; i >= 0; --i) {
        sum_back[i] = sum_back[i+1] + a[i];
    }

    std::sort(a.begin(), a.end(), std::greater<int>());
    parti[0] = 0;       // a[0] in A always !
    int sum = a[0];     // current sum

    int i = 1;          // index of the element being examined (we force a[0] to be in A !)
    int min_diff = sum_back[0];
    bool up_down = true;

    while (true) {          // UP
        if (up_down) {
            if (std::abs(sum) > sum_back[i] + min_diff) {  //premature abandon
                i--;
                up_down = false;
                continue;
            }
            n_poss[i] = 1;
            if (sum > 0) {
                sum -= a[i];
                parti[i] = 1;
            } else {
                sum += a[i];
                parti[i] = 0;
            }

            if (i == (n-1)) {           // leaf
                if (std::abs(sum) < min_diff) {
                    min_diff = std::abs(sum);
                    parti_opt = parti;
                    if (min_diff < 2) return std::make_tuple (min_diff, parti_opt);   // EDIT: if (... < 2) instead of (... == 0)
                }
                up_down = false;
                i--;
            } else {
                i++;        
            }

        } else {            // DOWN
            if (i == 0) break;
            if (n_poss[i] == 2) {
                if (parti[i]) sum += a[i];
                else sum -= a[i];
                //parti[i] = 0;
                i--;
            } else {
                n_poss[i] = 2;
                parti[i] = 1 - parti[i];
                if (parti[i]) sum -= 2*a[i];
                else sum += 2*a[i];
                i++;
                up_down = true;
            }
        }
    }
    return std::make_tuple (min_diff, parti_opt);
}

int main () {
    std::vector<int> a = {5, 6, 2, 10, 2, 3, 4, 13, 17, 38, 42};
    int diff;
    std::vector<int> parti;
    std::tie (diff, parti) = partition (a);

    std::cout << "Difference = " << diff << "\n";

    std::cout << "set A: ";
    for (int i = 0; i < a.size(); ++i) {
        if (parti[i] == 0) std::cout << a[i] << " ";
    }
    std::cout << "\n";

    std::cout << "set B: ";
    for (int i = 0; i < a.size(); ++i) {
        if (parti[i] == 1) std::cout << a[i] << " ";
    }
    std::cout << "\n";
}

Answer 2

I think that you should do the next exercise by yourself, otherwise you don't learn much. As for this one, here is a solution that tries to implement the advice by your instructor:

def partition(ratings):

    def split(lst, bits):
        ret = ([], [])
        for i, item in enumerate(lst):
            ret[(bits >> i) & 1].append(item)
        return ret

    target = sum(ratings) // 2
    best_distance = target
    best_split = ([], [])
    for bits in range(0, 1 << len(ratings)):
        parts = split(ratings, bits)
        distance = abs(sum(parts[0]) - target)
        if best_distance > distance:
            best_distance = distance
            best_split = parts
    return best_split

ratings = [5, 6, 2, 10, 2, 3, 4]
print(ratings)
print(partition(ratings))

Output:

[5, 6, 2, 10, 2, 3, 4]
([5, 2, 2, 3, 4], [6, 10])

Note that this output is different from your desired one, but both are correct.

This algorithm is based on the fact that, to pick all possible subsets of a given set with N elements, you can generate all integers with N bits, and select the I-th item depending on the value of the I-th bit. I leave to you to add a couple of lines in order to stop as soon as the best_distance is zero (because it can't get any better, of course).

A bit on bits (note that 0b is the prefix for a binary number in Python):

A binary number: 0b0111001 == 0·2⁶+1·2⁵+1·2⁴+1·2³+0·2²+0·2¹+1·2⁰ == 57

Right shifted by 1: 0b0111001 >> 1 == 0b011100 == 28

Left shifted by 1: 0b0111001 << 1 == 0b01110010 == 114

Right shifted by 4: 0b0111001 >> 4 == 0b011 == 3

Bitwise & (and): 0b00110 & 0b10101 == 0b00100

To check whether the 5th bit (index 4) is 1: (0b0111001 >> 4) & 1 == 0b011 & 1 == 1

A one followed by 7 zeros: 1 << 7 == 0b10000000

7 ones: (1 << 7) - 1 == 0b10000000 - 1 == 0b1111111

All 3-bit combinations: 0b000==0, 0b001==1, 0b010==2, 0b011==3, 0b100==4, 0b101==5, 0b110==6, 0b111==7 (note that 0b111 + 1 == 0b1000 == 1 << 3)

Answer 3

The following algorithm does this:

• sorts the items
• puts even members in list a, odd in list b to start
• randomly moves and swaps items between a and b if the change is for the better

I have added print statements to show the progress on your example list:

# -*- coding: utf-8 -*-
"""
Created on Fri Dec  6 18:10:07 2019

@author: Paddy3118
"""

from random import shuffle, random, randint

#%%
items = [5, 6, 2, 10, 2, 3, 4]

def eq(a, b):
    "Equal enough"
    return int(abs(a - b)) == 0

def fair_partition(items, jiggles=100):
    target = sum(items) / 2
    print(f"  Target sum: {target}")
    srt = sorted(items)
    a = srt[::2]    # every even
    b = srt[1::2]   # every odd
    asum = sum(a)
    bsum = sum(b)
    n = 0
    while n < jiggles and not eq(asum, target):
        n += 1
        if random() <0.5:
            # move from a to b?
            if random() <0.5:
                a, b, asum, bsum = b, a, bsum, asum     # Switch
            shuffle(a)
            trial = a[0]
            if abs(target - (bsum + trial)) < abs(target - bsum):  # closer
                b.append(a.pop(0))
                asum -= trial
                bsum += trial
                print(f"  Jiggle {n:2}: Delta after Move: {abs(target - asum)}")
        else:
            # swap between a and b?
            apos = randint(0, len(a) - 1)
            bpos = randint(0, len(b) - 1)
            trya, tryb = a[apos], b[bpos]
            if abs(target - (bsum + trya - tryb)) < abs(target - bsum):  # closer
                b.append(trya)  # adds to end
                b.pop(bpos)     # remove what is swapped
                a.append(tryb)
                a.pop(apos)
                asum += tryb - trya
                bsum += trya - tryb
                print(f"  Jiggle {n:2}: Delta after Swap: {abs(target - asum)}")
    return sorted(a), sorted(b)

if __name__ == '__main__':
    for _ in range(5):           
        print('\nFinal:', fair_partition(items), '\n')  

Output:

  Target sum: 16.0
  Jiggle  1: Delta after Swap: 2.0
  Jiggle  7: Delta after Swap: 0.0

Final: ([2, 3, 5, 6], [2, 4, 10]) 

  Target sum: 16.0
  Jiggle  4: Delta after Swap: 0.0

Final: ([2, 4, 10], [2, 3, 5, 6]) 

  Target sum: 16.0
  Jiggle  9: Delta after Swap: 3.0
  Jiggle 13: Delta after Move: 2.0
  Jiggle 14: Delta after Swap: 1.0
  Jiggle 21: Delta after Swap: 0.0

Final: ([2, 3, 5, 6], [2, 4, 10]) 

  Target sum: 16.0
  Jiggle  7: Delta after Swap: 3.0
  Jiggle  8: Delta after Move: 1.0
  Jiggle 13: Delta after Swap: 0.0

Final: ([2, 3, 5, 6], [2, 4, 10]) 

  Target sum: 16.0
  Jiggle  5: Delta after Swap: 0.0

Final: ([2, 4, 10], [2, 3, 5, 6]) 

Answer 4

Since I know I have to generate all possible lists, I need to make a "helper" function to help generate all possibilities. After doing that, I true to check for the minimum difference, and the combination of lists with that minimum difference is the desired solution.

The helper function is recursive, and check for all possibilities of combinations of lists.

def partition(ratings):

    def helper(ratings, left, right, aux_list, current_index):
        if current_index >= len(ratings):
            aux_list.append((left, right))
            return

        first = ratings[current_index]
        helper(ratings, left + [first], right, aux_list, current_index + 1)
        helper(ratings, left, right + [first], aux_list, current_index + 1)

    #l contains all possible sublists
    l = []
    helper(ratings, [], [], l, 0)
    set1 = []
    set2 = []
    #set mindiff to a large number
    mindiff = 1000
    for sets in l:
        diff = abs(sum(sets[0]) - sum(sets[1]))
        if diff < mindiff:
            mindiff = diff
            set1 = sets[0]
            set2 = sets[1]
    return (set1, set2)

Examples: r = [1, 2, 2, 3, 5, 4, 2, 4, 5, 5, 2], the optimal partition would be: ([1, 2, 2, 3, 5, 4], [2, 4, 5, 5, 2]) with a difference of 1.

r = [73, 7, 44, 21, 43, 42, 92, 88, 82, 70], the optimal partition would be: ([73, 7, 21, 92, 88], [44, 43, 42, 82, 70]) with a difference of 0.

Answer 5

Here is a fairly elaborate example, intended for educational purposes rather than performance. It introduces some interesting Python concepts such as list comprehensions and generators, as well as a good example of recursion in which fringe cases need to be checked appropriately. Extensions, e.g. only teams with an equal number of players are valid, are easy to implement in the appropriate individual functions.

def listFairestWeakTeams(ratings):
    current_best_weak_team_rating = -1
    fairest_weak_teams = []
    for weak_team in recursiveWeakTeamGenerator(ratings):
        weak_team_rating = teamRating(weak_team, ratings)
        if weak_team_rating > current_best_weak_team_rating:
            fairest_weak_teams = []
            current_best_weak_team_rating = weak_team_rating
        if weak_team_rating == current_best_weak_team_rating:
            fairest_weak_teams.append(weak_team)
    return fairest_weak_teams


def recursiveWeakTeamGenerator(
    ratings,
    weak_team=[],
    current_applicant_index=0
):
    if not isValidWeakTeam(weak_team, ratings):
        return
    if current_applicant_index == len(ratings):
        yield weak_team
        return
    for new_team in recursiveWeakTeamGenerator(
        ratings,
        weak_team + [current_applicant_index],
        current_applicant_index + 1
    ):
        yield new_team
    for new_team in recursiveWeakTeamGenerator(
        ratings,
        weak_team,
        current_applicant_index + 1
    ):
        yield new_team


def isValidWeakTeam(weak_team, ratings):
    total_rating = sum(ratings)
    weak_team_rating = teamRating(weak_team, ratings)
    optimal_weak_team_rating = total_rating // 2
    if weak_team_rating > optimal_weak_team_rating:
        return False
    elif weak_team_rating * 2 == total_rating:
        # In case of equal strengths, player 0 is assumed
        # to be in the "weak" team
        return 0 in weak_team
    else:
        return True


def teamRating(team_members, ratings):
    return sum(memberRatings(team_members, ratings))    


def memberRatings(team_members, ratings):
    return [ratings[i] for i in team_members]


def getOpposingTeam(team, ratings):
    return [i for i in range(len(ratings)) if i not in team]


ratings = [5, 6, 2, 10, 2, 3, 4]
print("Player ratings:     ", ratings)
print("*" * 40)
for option, weak_team in enumerate(listFairestWeakTeams(ratings)):
    strong_team = getOpposingTeam(weak_team, ratings)
    print("Possible partition", option + 1)
    print("Weak team members:  ", weak_team)
    print("Weak team ratings:  ", memberRatings(weak_team, ratings))
    print("Strong team members:", strong_team)
    print("Strong team ratings:", memberRatings(strong_team, ratings))
    print("*" * 40)

Output:

Player ratings:      [5, 6, 2, 10, 2, 3, 4]
****************************************
Possible partition 1
Weak team members:   [0, 1, 2, 5]
Weak team ratings:   [5, 6, 2, 3]
Strong team members: [3, 4, 6]
Strong team ratings: [10, 2, 4]
****************************************
Possible partition 2
Weak team members:   [0, 1, 4, 5]
Weak team ratings:   [5, 6, 2, 3]
Strong team members: [2, 3, 6]
Strong team ratings: [2, 10, 4]
****************************************
Possible partition 3
Weak team members:   [0, 2, 4, 5, 6]
Weak team ratings:   [5, 2, 2, 3, 4]
Strong team members: [1, 3]
Strong team ratings: [6, 10]
****************************************

Answer 6

Given that you want even teams you know the target score of the ratings of each team. This is the sum of the ratings divided by 2.

So the following code should do what you want.

from itertools import combinations

ratings = [5, 6, 2, 10, 2, 3, 4]

target = sum(ratings)/2 

difference_dictionary = {}
for i in range(1, len(ratings)): 
    for combination in combinations(ratings, i): 
        diff = sum(combination) - target
        if diff >= 0: 
            difference_dictionary[diff] = difference_dictionary.get(diff, []) + [combination]

# get min difference to target score 
min_difference_to_target = min(difference_dictionary.keys())
strong_ratings = difference_dictionary[min_difference_to_target]
first_strong_ratings = [x for x in strong_ratings[0]]

weak_ratings = ratings.copy()
for strong_rating in first_strong_ratings: 
    weak_ratings.remove(strong_rating)

Output

first_strong_ratings 
[6, 10]

weak_rating 
[5, 2, 2, 3, 4]

There is other splits that have the same fairness these are all available to find inside the strong_ratings tuple, I just choose to look at the first one as this will always exist for any ratings list that you pass in (provided len(ratings) > 1).

Answer 7

A greedy solution might yield a sub-optimal solution. Here is a fairly simple greedy solution, the idea is to sort the list in descending order in order to decrease the effect of the addition of ratings in the bucket. Rating will be added to that bucket whose total rating sum is less

lis = [5, 6, 2, 10, 2, 3, 4]
lis.sort()
lis.reverse()

bucket_1 = []
bucket_2 = []

for item in lis:
    if sum(bucket_1) <= sum(bucket_2):
        bucket_1.append(item)
    else:
        bucket_2.append(item)

print("Bucket 1 : {}".format(bucket_1))
print("Bucket 2 : {}".format(bucket_2))

Output :

Bucket 1 : [10, 4, 2]
Bucket 2 : [6, 5, 3, 2]

Edit:

Another approach will be to generate all possible subsets of the list. Let's say you have l1 which is one of the subsets of the list, then you can easily get list l2 such that l2 = list(original) - l1. Number of all possible subset of the list of size n is 2^n. We can denote them as seq of an integer from 0 to 2^n -1. Take an example, say you have list = [1, 3, 5] then no of possible combination is 2^3 i.e 8. Now we can write all combination as follow:

1. 000 - [] - 0
2. 001 - [1] - 1
3. 010 - [3] - 2
4. 011 - [1,3] - 3
5. 100 - [5] - 4
6. 101 - [1,5] - 5
7. 110 - [3,5]- 6
8. 111 - [1,3,5] - 7 and l2, in this case, can easily be obtained by taking xor with 2^n-1.

Solution:

def sum_list(lis, n, X):
    """
    This function will return sum of all elemenst whose bit is set to 1 in X
    """
    sum_ = 0
    # print(X)
    for i in range(n):
        if (X & 1<<i ) !=0:
            # print( lis[i], end=" ")
            sum_ += lis[i]
    # print()
    return sum_

def return_list(lis, n, X):
    """
    This function will return list of all element whose bit is set to 1 in X
    """
    new_lis = []
    for i in range(n):
        if (X & 1<<i) != 0:
            new_lis.append(lis[i])
    return new_lis

lis = [5, 6, 2, 10, 2, 3, 4]
n = len(lis)
total = 2**n -1 

result_1 = 0
result_2 = total
result_1_sum = 0
result_2_sum = sum_list(lis,n, result_2)
ans = total
for i in range(total):
    x = (total ^ i)
    sum_x = sum_list(lis, n, x)
    sum_y = sum_list(lis, n, i)

    if abs(sum_x-sum_y) < ans:
        result_1 =  x
        result_2 = i
        result_1_sum = sum_x
        result_2_sum = sum_y
        ans = abs(result_1_sum-result_2_sum)

"""
Produce resultant list
"""

bucket_1 = return_list(lis,n,result_1)
bucket_2 = return_list(lis, n, result_2)

print("Bucket 1 : {}".format(bucket_1))
print("Bucket 2 : {}".format(bucket_2))

Output :

Bucket 1 : [5, 2, 2, 3, 4]
Bucket 2 : [6, 10]