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";
}