Particionamiento equitativo de elementos de una lista

Dada una lista de clasificaciones de jugadores, debo dividir a los jugadores (es decir, clasificaciones) en dos grupos de la manera más justa posible. El objetivo es minimizar la diferencia entre la calificación acumulativa de los equipos. No hay restricciones en cuanto a cómo puedo dividir a los jugadores en los equipos (un equipo puede tener 2 jugadores y el otro equipo puede tener 10 jugadores).

Por ejemplo: [5, 6, 2, 10, 2, 3, 4]debería volver([6, 5, 3, 2], [10, 4, 2])

Me gustaría conocer el algoritmo para resolver este problema. Tenga en cuenta que estoy tomando un curso introductorio de programación en línea, por lo que se agradecerán los algoritmos simples.

Estoy usando el siguiente código, pero por alguna razón, el verificador de código en línea dice que es incorrecto.

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)

Actualización: Me puse en contacto con los instructores y me dijeron que debería definir otra función "auxiliar" dentro de la función para verificar todas las combinaciones diferentes, luego necesito verificar la diferencia mínima.

Nota: Editado para manejar mejor el caso cuando la suma de todos los números es impar.

Retroceder es una posibilidad para este problema.

Permite examinar todas las posibilidades de forma recursiva, sin la necesidad de una gran cantidad de memoria.

Se detiene tan pronto como se encuentra una solución óptima: sum = 0dónde sumestá la diferencia entre la suma de los elementos del conjunto A y la suma de los elementos del conjunto B. EDITAR: se detiene tan pronto sum < 2para manejar el caso cuando la suma de todos los números es impar, es decir, corresponde a una diferencia mínima de 1. Si esta suma global es par, la diferencia mínima no puede ser igual a 1.

Permite implementar un procedimiento simple de abandono prematuro :
en un momento dado, si sumes mayor que la suma de todos los elementos restantes (es decir, no colocados en A o B) más el valor absoluto del mínimo actual obtenido, entonces podemos dejar de examinar la ruta actual, sin examinar los elementos restantes. Este procedimiento está optimizado con:

• ordenar los datos de entrada en orden decreciente
• En cada paso, primero examine la opción más probable: esto permite ir rápidamente a una solución casi óptima

Aquí hay un pseudocódigo

Inicializacion:

• ordenar elementos a[]
• Calcule la suma de los elementos restantes: sum_back[i] = sum_back[i+1] + a[i];
• Establezca la "diferencia" mínima en su valor máximo: min_diff = sum_back[0];
• Poner a[0]en A -> el índice idel elemento examinado se establece en 1
• Conjunto up_down = true;: este valor booleano indica si actualmente estamos avanzando (verdadero) o retrocediendo (falso)

Mientras bucle:

• If (arriba_ abajo): adelante

  • Pruebe el abandono prematuro, con la ayuda de sum_back
  • Seleccione el valor más probable, ajústelo sumsegún esta opción
  • if (i == n-1): LEAF -> prueba si se mejora el valor óptimo y devuelve si el nuevo valor es igual a 0 (EDITAR if (... < 2)); volver atras
  • Si no está en una hoja: continúe avanzando

• If (! Updown): hacia atrás

  • Si llegamos a i == 0: regreso
  • Si es la segunda caminata en este nodo: seleccione el segundo valor, suba
  • más: baja
  • En ambos casos: recalcular el nuevo sumvalor

Aquí hay un código, en C ++ (lo siento, no sé 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";
}

Creo que deberías hacer el próximo ejercicio por tu cuenta, de lo contrario no aprenderás mucho. En cuanto a este, aquí hay una solución que intenta implementar el consejo de su 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))

Salida:

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

Tenga en cuenta que esta salida es diferente de la deseada, pero ambas son correctas.

Este algoritmo se basa en el hecho de que, para elegir todos los subconjuntos posibles de un conjunto dado con N elementos, puede generar todos los enteros con N bits y seleccionar el elemento I-ésimo dependiendo del valor del bit I-ésimo. Dejo que agreguen un par de líneas para detenerse tan pronto como best_distancesea ​​cero (porque, por supuesto, no puede mejorar).

Un bit en bits (tenga en cuenta que 0bes el prefijo para un número binario en Python):

Un número binario: 0b0111001 == 0·2⁶+1·2⁵+1·2⁴+1·2³+0·2²+0·2¹+1·2⁰ == 57

Derecha desplazada por 1: 0b0111001 >> 1 == 0b011100 == 28

Izquierda desplazada por 1: 0b0111001 << 1 == 0b01110010 == 114

Derecha desplazada por 4: 0b0111001 >> 4 == 0b011 == 3

A nivel de bit &(y):0b00110 & 0b10101 == 0b00100

Para verificar si el quinto bit (índice 4) es 1: (0b0111001 >> 4) & 1 == 0b011 & 1 == 1

Uno seguido de 7 ceros: 1 << 7 == 0b10000000

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

Todas las combinaciones de 3 bits: 0b000==0, 0b001==1, 0b010==2, 0b011==3, 0b100==4, 0b101==5, 0b110==6, 0b111==7(nota que 0b111 + 1 == 0b1000 == 1 << 3)

El siguiente algoritmo hace esto:

• ordena los artículos
• pone a los miembros pares en la lista a, impares en la lista bpara comenzar
• mueve aleatoriamente e intercambia elementos entre ay bsi el cambio es para mejor

He agregado declaraciones impresas para mostrar el progreso en su lista de ejemplos:

# -*- 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')  

Salida:

  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]) 

Como sé que tengo que generar todas las listas posibles, necesito hacer una función de "ayuda" para ayudar a generar todas las posibilidades. Después de hacer eso, debo verificar la diferencia mínima, y ​​la combinación de listas con esa diferencia mínima es la solución deseada.

La función auxiliar es recursiva y verifica todas las posibilidades de combinaciones de listas.

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)

Ejemplos: r = [1, 2, 2, 3, 5, 4, 2, 4, 5, 5, 2]la partición óptima sería: ([1, 2, 2, 3, 5, 4], [2, 4, 5, 5, 2])con una diferencia de 1.

r = [73, 7, 44, 21, 43, 42, 92, 88, 82, 70], la partición óptima sería: ([73, 7, 21, 92, 88], [44, 43, 42, 82, 70])con una diferencia de 0.

Aquí hay un ejemplo bastante elaborado, destinado a fines educativos en lugar de desempeño. Introduce algunos conceptos interesantes de Python, como las listas de comprensiones y generadores, así como un buen ejemplo de recursión en el que los casos marginales deben verificarse adecuadamente. Las extensiones, por ejemplo, solo los equipos con el mismo número de jugadores son válidos, son fáciles de implementar en las funciones individuales apropiadas.

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)

Salida:

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]
****************************************

Dado que quiere incluso equipos, conoce el puntaje objetivo de las calificaciones de cada equipo. Esta es la suma de las calificaciones dividida por 2.

Entonces, el siguiente código debe hacer lo que quieras.

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)

Salida

first_strong_ratings 
[6, 10]

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

Hay otras divisiones que tienen lo mismo fairness, todas están disponibles para encontrar dentro de la tupla strong_ratings, solo elijo mirar la primera, ya que esto siempre existirá para cualquier lista de calificaciones que ingrese (provista len(ratings) > 1).

Una solución codiciosa podría producir una solución subóptima. Aquí hay una solución codiciosa bastante simple, la idea es ordenar la lista en orden descendente para disminuir el efecto de la adición de calificaciones en el cubo. La calificación se agregará a ese grupo cuya suma total de calificación es menor

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))

Salida:

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

Editar:

Otro enfoque será generar todos los subconjuntos posibles de la lista. Digamos que tiene l1, que es uno de los subconjuntos de la lista, entonces puede obtener fácilmente la lista l2 de modo que l2 = lista (original) - l1. El número de todos los subconjuntos posibles de la lista de tamaño n es 2 ^ n. Podemos denotarlos como seq de un entero de 0 a 2 ^ n -1. Tome un ejemplo, digamos que tiene una lista = [1, 3, 5], entonces ninguna combinación posible es 2 ^ 3, es decir, 8. Ahora podemos escribir todas las combinaciones de la siguiente manera:

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 y l2, en este caso, pueden obtenerse fácilmente tomando xor con 2 ^ n-1.

Solución:

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))

Salida:

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