Particionamento justo de elementos de uma lista

Dada uma lista de classificações de jogadores, sou obrigado a dividir os jogadores (ou seja, classificações) em dois grupos o mais razoavelmente possível. O objetivo é minimizar a diferença entre a classificação acumulada das equipes. Não há restrições sobre como posso dividir os jogadores em equipes (uma equipe pode ter 2 jogadores e a outra equipe pode ter 10 jogadores).

Por exemplo: [5, 6, 2, 10, 2, 3, 4]deve retornar([6, 5, 3, 2], [10, 4, 2])

Gostaria de conhecer o algoritmo para resolver este problema. Observe que estou fazendo um curso introdutório de programação on-line, para que algoritmos simples sejam apreciados.

Estou usando o código a seguir, mas, por algum motivo, o verificador de código on-line diz que está incorreto.

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)

Atualização: entrei em contato com os instrutores e me disseram que eu deveria definir outra função "auxiliar" dentro da função para verificar todas as combinações diferentes; então, preciso verificar a diferença mínima.

Nota: Editado para lidar melhor com o caso quando a soma de todos os números é ímpar.

O retorno é uma possibilidade para esse problema.

Permite examinar todas as possibilidades recursivamente, sem a necessidade de uma grande quantidade de memória.

Para assim que uma solução ótima é encontrada:, sum = 0onde sumestá a diferença entre a soma dos elementos do conjunto A e a soma dos elementos do conjunto B. EDIT: ele pára assim quesum < 2 , para lidar com o caso quando a soma de todos os números é ímpar, ou seja, corresponde a uma diferença mínima de 1. Se essa soma global for par, a diferença mínima não poderá ser igual a 1.

Permite implementar um procedimento simples de abandono prematuro :
em um determinado momento, se sumfor maior que a soma de todos os elementos restantes (ou seja, não colocados em A ou B) mais o valor absoluto do mínimo atual obtido, podemos deixar de examinar o caminho atual, sem examinar os elementos restantes. Este procedimento é otimizado com:

• classifique os dados de entrada em ordem decrescente
• Em cada etapa, primeiro examine a escolha mais provável: isso permite ir rapidamente a uma solução quase ideal

Aqui está um pseudo-código

Inicialização:

• classificar elementos a[]
• Calcule a soma dos elementos restantes: sum_back[i] = sum_back[i+1] + a[i];
• Defina a "diferença" mínima para o seu valor máximo: min_diff = sum_back[0];
• Coloque a[0]em A -> o índicei do elemento examinado é definido como 1
• Set up_down = true;: este booleano indica se estamos atualmente avançando (true) ou backward (false)

Enquanto loop:

• Se (up_down): encaminhar

  • Teste o abandono prematuro, com a ajuda de sum_back
  • Selecione o valor mais provável, ajuste de sumacordo com esta escolha
  • if (i == n-1): LEAF -> teste se o valor ideal é aprimorado e retorne se o novo valor for igual a 0 (EDIT: if (... < 2) ; ir para trás
  • Se não estiver em uma folha: continue em frente

• If (! Updown): para trás

  • Se chegarmos a i == 0 : return
  • Se for a segunda caminhada neste nó: selecione o segundo valor, vá para cima
  • mais: desça
  • Nos dois casos: recalcule o novo sumvalor

Aqui está um código, em C ++ (Desculpe, não sei 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";
}

Eu acho que você deve fazer o próximo exercício sozinho, caso contrário você não aprenderá muito. Quanto a este, aqui está uma solução que tenta implementar o conselho do seu instrutor:

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

Resultado:

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

Observe que essa saída é diferente da desejada, mas ambas estão corretas.

Esse algoritmo é baseado no fato de que, para selecionar todos os subconjuntos possíveis de um determinado conjunto com N elementos, você pode gerar todos os números inteiros com N bits e selecionar o item I-ésimo, dependendo do valor do I-ésimo bit. Deixo para você adicionar algumas linhas para parar assim que o best_distancezero for zero (porque não pode melhorar, é claro).

Um pouco sobre bits (observe que 0bé o prefixo de um número binário em Python):

Um número binário: 0b0111001 == 0·2⁶+1·2⁵+1·2⁴+1·2³+0·2²+0·2¹+1·2⁰ == 57

Deslocado para a direita em 1: 0b0111001 >> 1 == 0b011100 == 28

Deslocado para a esquerda em 1: 0b0111001 << 1 == 0b01110010 == 114

Deslocado para a direita em 4: 0b0111001 >> 4 == 0b011 == 3

Bit a bit &(e):0b00110 & 0b10101 == 0b00100

Para verificar se o quinto bit (índice 4) é 1: (0b0111001 >> 4) & 1 == 0b011 & 1 == 1

Um seguido por 7 zeros: 1 << 7 == 0b10000000

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

Todas as combinações de três bits: 0b000==0, 0b001==1, 0b010==2, 0b011==3, 0b100==4, 0b101==5, 0b110==6, 0b111==7(note que 0b111 + 1 == 0b1000 == 1 << 3)

O seguinte algoritmo faz isso:

• classifica os itens
• coloca membros pares na lista a, ímpares na lista bpara iniciar
• move aleatoriamente e troca itens entre ae bse a alteração é para melhor

Eu adicionei instruções de impressão para mostrar o progresso em sua lista de exemplos:

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

Resultado:

  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 sei que tenho que gerar todas as listas possíveis, preciso criar uma função "auxiliar" para ajudar a gerar todas as possibilidades. Depois disso, verifiquei a diferença mínima e a combinação de listas com essa diferença mínima é a solução desejada.

A função auxiliar é recursiva e verifique todas as possibilidades de combinações 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)

Exemplos r = [1, 2, 2, 3, 5, 4, 2, 4, 5, 5, 2]:, a partição ideal seria: ([1, 2, 2, 3, 5, 4], [2, 4, 5, 5, 2])com uma diferença de 1.

r = [73, 7, 44, 21, 43, 42, 92, 88, 82, 70], a partição ideal seria: ([73, 7, 21, 92, 88], [44, 43, 42, 82, 70])com uma diferença de 0.

Aqui está um exemplo bastante elaborado, destinado a fins educacionais e não a desempenho. Ele apresenta alguns conceitos interessantes do Python, como compreensão de lista e geradores, bem como um bom exemplo de recursão em que casos adicionais precisam ser verificados adequadamente. Extensões, por exemplo, apenas equipes com um número igual de jogadores são válidas, são fáceis de implementar nas funções individuais apropriadas.

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)

Resultado:

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 você quer equipes iguais, você conhece a pontuação desejada das classificações de cada equipe. Esta é a soma das classificações divididas por 2.

Portanto, o código a seguir deve fazer o que você deseja.

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)

Resultado

first_strong_ratings 
[6, 10]

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

Existem outras divisões com as mesmas, fairnesstodas disponíveis para encontrar dentro da tupla strong_ratings, apenas optei por ver a primeira, pois ela sempre existirá para qualquer lista de classificações que você passar (desdelen(ratings) > 1 ).

Uma solução gananciosa pode gerar uma solução abaixo do ideal. Aqui está uma solução gananciosa bastante simples, a idéia é classificar a lista em ordem decrescente para diminuir o efeito da adição de classificações no intervalo. A classificação será adicionada ao intervalo cuja soma total da classificação é 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))

Resultado :

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

Editar:

Outra abordagem será gerar todos os subconjuntos possíveis da lista. Digamos que você tenha l1, que é um dos subconjuntos da lista, e é possível obter facilmente a lista l2 de forma que l2 = list (original) - l1. O número de todo o subconjunto possível da lista de tamanho n é 2 ^ n. Podemos denotá-los como seq de um número inteiro de 0 a 2 ^ n -1. Tomemos um exemplo, digamos que você tenha list = [1, 3, 5], então nenhuma das combinações possíveis é 2 ^ 3, ou seja, 8. Agora, podemos escrever todas as combinações da seguinte maneira:

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 e l2, neste caso, podem ser facilmente obtidos tomando xor com 2 ^ n-1.

Solução:

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

Resultado :

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