Partitionnement équitable des éléments d'une liste

Étant donné une liste de notes des joueurs, je dois diviser les joueurs (c.-à-d. Les notes) en deux groupes aussi équitablement que possible. L'objectif est de minimiser la différence entre la note cumulée des équipes. Il n'y a aucune contrainte quant à la façon dont je peux diviser les joueurs en équipes (une équipe peut avoir 2 joueurs et l'autre équipe peut avoir 10 joueurs).

Par exemple: [5, 6, 2, 10, 2, 3, 4]devrait revenir([6, 5, 3, 2], [10, 4, 2])

Je voudrais connaître l'algorithme pour résoudre ce problème. Veuillez noter que je prends un cours d'introduction à la programmation en ligne, donc des algorithmes simples seraient appréciés.

J'utilise le code suivant, mais pour une raison quelconque, le vérificateur de code en ligne dit qu'il est 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)

Mise à jour: J'ai contacté les instructeurs et on m'a dit que je devrais définir une autre fonction "d'aide" à l'intérieur de la fonction pour vérifier toutes les différentes combinaisons, puis je dois vérifier la différence minimale.

Remarque: modifié pour mieux gérer le cas lorsque la somme de tous les nombres est impaire.

Le retour en arrière est une possibilité pour ce problème.

Il permet d'examiner toutes les possibilités de manière récursive, sans avoir besoin d'une grande quantité de mémoire.

Il s'arrête dès qu'une solution optimale est trouvée:, sum = 0où sumest la différence entre la somme des éléments de l'ensemble A et la somme des éléments de l'ensemble B. EDIT: il s'arrête dès que sum < 2, pour traiter le cas où la somme de tous les nombres est impair, c'est-à-dire correspondant à une différence minimale de 1. Si cette somme globale est paire, la différence min ne peut pas être égale à 1.

Il permet de mettre en œuvre une procédure simple d' abandon prématuré :
à un instant donné, s'il sumest supérieur alors la somme de tous les éléments restants (c'est-à-dire non placés en A ou B) plus la valeur absolue du minimum actuel obtenu, alors on peut renoncer le chemin actuel, sans examiner les éléments restants. Cette procédure est optimisée avec:

• trier les données d'entrée par ordre décroissant
• A chaque étape, examinez d'abord le choix le plus probable: cela permet de passer rapidement à une solution quasi optimale

Voici un pseudo-code

Initialisation:

• trier les éléments a[]
• Calculez la somme des éléments restants: sum_back[i] = sum_back[i+1] + a[i];
• Réglez la "différence" min à sa valeur maximale: min_diff = sum_back[0];
• Mettez a[0]dans A -> l'indice ide l'élément examiné est mis à 1
• Set up_down = true;: ce booléen indique si nous allons actuellement en avant (vrai) ou en arrière (faux)

Boucle while:

• Si (up_down): avant

  • Tester l'abandon prématuré, avec l'aide de sum_back
  • Sélectionnez la valeur la plus probable, ajustez sumselon ce choix
  • if (i == n-1): LEAF -> teste si la valeur optimale est améliorée et retourne si la nouvelle valeur est égale à 0 (EDIT:) if (... < 2); aller à l'arrière
  • Si ce n'est pas dans une feuille: continuez à avancer

• Si (! Updown): en arrière

  • Si nous arrivons à i == 0 : retour
  • Si c'est la deuxième marche de ce noeud: sélectionnez la deuxième valeur, montez
  • sinon: redescendre
  • Dans les deux cas: recalculez la nouvelle sumvaleur

Voici un code, en C ++ (Désolé, je ne connais pas 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";
}

Je pense que vous devriez faire le prochain exercice par vous-même, sinon vous n'apprenez pas beaucoup. Quant à celui-ci, voici une solution qui tente de mettre en œuvre les conseils de votre moniteur:

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

Production:

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

Notez que cette sortie est différente de celle désirée, mais les deux sont correctes.

Cet algorithme est basé sur le fait que, pour sélectionner tous les sous-ensembles possibles d'un ensemble donné avec N éléments, vous pouvez générer tous les entiers avec N bits et sélectionner le I-ème élément en fonction de la valeur du I-ème bit. Je vous laisse ajouter quelques lignes afin de vous arrêter dès que le best_distancezéro est nul (car ça ne peut pas aller mieux, bien sûr).

Un peu sur les bits (notez que 0bc'est le préfixe d'un nombre binaire en Python):

Un nombre binaire: 0b0111001 == 0·2⁶+1·2⁵+1·2⁴+1·2³+0·2²+0·2¹+1·2⁰ == 57

Décalé à droite de 1: 0b0111001 >> 1 == 0b011100 == 28

Décalé à gauche de 1: 0b0111001 << 1 == 0b01110010 == 114

Décalé à droite de 4: 0b0111001 >> 4 == 0b011 == 3

Au niveau du bit &(et):0b00110 & 0b10101 == 0b00100

Pour vérifier si le 5e bit (index 4) est 1: (0b0111001 >> 4) & 1 == 0b011 & 1 == 1

Un suivi de 7 zéros: 1 << 7 == 0b10000000

7 unités: (1 << 7) - 1 == 0b10000000 - 1 == 0b1111111

Toutes les combinaisons 3 bits: 0b000==0, 0b001==1, 0b010==2, 0b011==3, 0b100==4, 0b101==5, 0b110==6, 0b111==7(note que 0b111 + 1 == 0b1000 == 1 << 3)

L'algorithme suivant fait cela:

• trie les articles
• met les membres pairs dans la liste a, impair dans la liste bpour commencer
• déplace et échange au hasard des éléments entre aet bsi le changement est pour le mieux

J'ai ajouté des instructions d'impression pour montrer les progrès de votre liste d'exemples:

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

Production:

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

Comme je sais que je dois générer toutes les listes possibles, je dois créer une fonction "d'aide" pour aider à générer toutes les possibilités. Après cela, je vérifie la différence minimale et la combinaison de listes avec cette différence minimale est la solution souhaitée.

La fonction d'assistance est récursive et vérifie toutes les possibilités de combinaisons de listes.

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)

Exemples r = [1, 2, 2, 3, 5, 4, 2, 4, 5, 5, 2]:, la partition optimale serait: ([1, 2, 2, 3, 5, 4], [2, 4, 5, 5, 2])avec une différence de 1.

r = [73, 7, 44, 21, 43, 42, 92, 88, 82, 70], la partition optimale serait: ([73, 7, 21, 92, 88], [44, 43, 42, 82, 70])avec une différence de 0.

Voici un exemple assez élaboré, destiné à des fins éducatives plutôt qu'à des performances. Il présente quelques concepts Python intéressants tels que les compréhensions de listes et les générateurs, ainsi qu'un bon exemple de récursivité dans lequel les cas marginaux doivent être vérifiés de manière appropriée. Les extensions, par exemple seules les équipes avec un nombre égal de joueurs sont valides, sont faciles à mettre en œuvre dans les fonctions individuelles appropriées.

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)

Production:

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

Étant donné que vous voulez même des équipes, vous connaissez le score cible des notes de chaque équipe. Il s'agit de la somme des notes divisée par 2.

Le code suivant devrait donc faire ce que vous voulez.

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)

Production

first_strong_ratings 
[6, 10]

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

Il y a d'autres divisions qui ont le même, fairnesselles sont toutes disponibles pour trouver à l'intérieur du tuple strong_ratings, je choisis simplement de regarder la première car cela existera toujours pour toute liste de notes que vous transmettez (fournie len(ratings) > 1).

Une solution gourmande pourrait donner une solution sous-optimale. Voici une solution assez simple et gourmande, l'idée est de trier la liste par ordre décroissant afin de diminuer l'effet de l'ajout de notes dans le bucket. La note sera ajoutée à ce compartiment dont la somme totale des notes est inférieure

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

Production :

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

Éditer:

Une autre approche consistera à générer tous les sous-ensembles possibles de la liste. Disons que vous avez l1 qui est l'un des sous-ensembles de la liste, alors vous pouvez facilement obtenir la liste l2 telle que l2 = list (original) - l1. Le nombre de tous les sous-ensembles possibles de la liste de taille n est 2 ^ n. On peut les désigner comme seq d'un entier de 0 à 2 ^ n -1. Prenons un exemple, disons que vous avez list = [1, 3, 5] alors aucune combinaison possible n'est 2 ^ 3 soit 8. Maintenant, nous pouvons écrire toutes les combinaisons comme suit:

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 et l2, dans ce cas, peuvent être facilement obtenus en prenant xor avec 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))

Production :

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