Uczciwy podział elementów listy

Biorąc pod uwagę listę ocen graczy, jestem zobowiązany do podzielenia graczy (tj. Ocen) na dwie grupy tak uczciwie, jak to możliwe. Celem jest zminimalizowanie różnicy między skumulowaną oceną drużyn. Nie ma żadnych ograniczeń co do tego, w jaki sposób mogę podzielić graczy na drużyny (jedna drużyna może mieć 2 graczy, a druga drużyna może mieć 10 graczy).

Na przykład: [5, 6, 2, 10, 2, 3, 4]powinien wrócić([6, 5, 3, 2], [10, 4, 2])

Chciałbym znać algorytm rozwiązania tego problemu. Pamiętaj, że biorę kurs wprowadzający do programowania online, więc proste algorytmy byłyby mile widziane.

Używam następującego kodu, ale z jakiegoś powodu narzędzie do sprawdzania kodów online twierdzi, że jest niepoprawne.

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)

Aktualizacja: skontaktowałem się z instruktorami i powiedziano mi, że powinienem zdefiniować inną funkcję „pomocnika” wewnątrz funkcji, aby sprawdzić wszystkie różne kombinacje, a następnie muszę sprawdzić minimalną różnicę.

Uwaga: Zredagowano, aby lepiej obsługiwać przypadek, gdy suma wszystkich liczb jest nieparzysta.

Cofanie jest możliwością tego problemu.

Pozwala na badanie wszystkich możliwości rekurencyjnie, bez potrzeby dużej ilości pamięci.

Zatrzymuje się, gdy tylko zostanie znalezione optymalne rozwiązanie: sum = 0gdzie sumjest różnica między sumą elementów zestawu A i sumą elementów zestawu B. EDYCJA: zatrzymuje się tak szybko sum < 2, aby obsłużyć przypadek, w którym suma wszystkich liczb jest nieparzysty, tzn. odpowiada minimalnej różnicy równej 1. Jeśli ta suma globalna jest parzysta, minimalna różnica nie może być równa 1.

Pozwala to wdrożyć prostą procedurę przedwczesnego porzucenia :
w danym momencie, jeśli sumjest wyższa niż suma wszystkich pozostałych elementów (tj. Nie umieszczonych w A lub B) plus wartość bezwzględna uzyskanego minimum, możemy zrezygnować z badania bieżąca ścieżka, bez badania pozostałych elementów. Ta procedura jest zoptymalizowana dzięki:

• posortuj dane wejściowe w malejącej kolejności
• Na każdym kroku najpierw sprawdź najbardziej prawdopodobny wybór: pozwala to szybko przejść do prawie optymalnego rozwiązania

Oto pseudo-kod

Inicjalizacja:

• sortuj elementy a[]
• Oblicz sumę pozostałych elementów: sum_back[i] = sum_back[i+1] + a[i];
• Ustaw minimalną „różnicę” na maksymalną wartość: min_diff = sum_back[0];
• Wstaw a[0]A -> indeks ibadanego elementu jest ustawiony na 1
• Zestaw up_down = true;: ta wartość logiczna wskazuje, czy aktualnie idziemy do przodu (prawda), czy do tyłu (fałsz)

Podczas pętli:

• Jeśli (up_down): naprzód

  • Przetestuj przedwczesne porzucenie, z pomocą sum_back
  • Wybierz najbardziej prawdopodobną wartość, dostosuj sumzgodnie z tym wyborem
  • if (i == n-1): LEAF -> sprawdź poprawność optymalnej wartości i zwróć, jeśli nowa wartość jest równa 0 (EDYCJA:) if (... < 2); idź wstecz
  • Jeśli nie w liściu: kontynuuj

• Jeśli (! Updown): wstecz

  • Jeśli dojdziemy do i == 0: powrót
  • Jeśli jest to drugi spacer w tym węźle: wybierz drugą wartość, idź w górę
  • inaczej: zejdź na dół
  • W obu przypadkach: ponownie oblicz nową sumwartość

Oto kod w C ++ (Przepraszamy, nie znam 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";
}

Myślę, że powinieneś zrobić następne ćwiczenie sam, w przeciwnym razie nie nauczysz się wiele. Jeśli chodzi o ten, oto rozwiązanie, które próbuje wdrożyć porady Twojego instruktora:

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

Wynik:

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

Zauważ, że ten wynik jest inny niż pożądany, ale oba są poprawne.

Algorytm ten opiera się na fakcie, że aby wybrać wszystkie możliwe podzbiory danego zestawu z N elementami, możesz wygenerować wszystkie liczby całkowite z N bitów i wybrać I-ty element w zależności od wartości I-tego bitu. Pozostawiam wam dodanie kilku linii, aby zatrzymać się, gdy tylko best_distancezero wyniesie (bo oczywiście nie może być już lepiej).

Trochę bitów (zwróć uwagę, że 0bjest to przedrostek liczby binarnej w Pythonie):

Liczba binarna: 0b0111001 == 0·2⁶+1·2⁵+1·2⁴+1·2³+0·2²+0·2¹+1·2⁰ == 57

Prawo przesunięty o 1: 0b0111001 >> 1 == 0b011100 == 28

Lewy przesunięty o 1: 0b0111001 << 1 == 0b01110010 == 114

Prawo przesunięty o 4: 0b0111001 >> 4 == 0b011 == 3

Bitowe &(i):0b00110 & 0b10101 == 0b00100

Aby sprawdzić, czy 5. bit (indeks 4) ma wartość 1: (0b0111001 >> 4) & 1 == 0b011 & 1 == 1

Jeden z 7 zerami: 1 << 7 == 0b10000000

7 z nich: (1 << 7) - 1 == 0b10000000 - 1 == 0b1111111

Wszystkie kombinacje 3-bitowe: 0b000==0, 0b001==1, 0b010==2, 0b011==3, 0b100==4, 0b101==5, 0b110==6, 0b111==7(uwaga 0b111 + 1 == 0b1000 == 1 << 3)

Robi to następujący algorytm:

• sortuje elementy
• umieszcza parzystych członków na liście a, nieparzystych na liście, baby rozpocząć
• losowo przesuwa i zamienia przedmioty pomiędzy ai bjeśli zmiana jest lepsza

Dodałem drukowane wyciągi, aby pokazać postęp na twojej przykładowej liście:

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

Wynik:

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

Ponieważ wiem, że muszę wygenerować wszystkie możliwe listy, muszę stworzyć funkcję „pomocnika”, aby pomóc wygenerować wszystkie możliwości. Po zrobieniu tego, naprawdę sprawdzam minimalną różnicę, a kombinacja list z tą minimalną różnicą jest pożądanym rozwiązaniem.

Funkcja pomocnicza jest rekurencyjna i sprawdza wszystkie możliwości kombinacji list.

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)

Przykłady: r = [1, 2, 2, 3, 5, 4, 2, 4, 5, 5, 2]optymalna partycja to: ([1, 2, 2, 3, 5, 4], [2, 4, 5, 5, 2])z różnicą 1.

r = [73, 7, 44, 21, 43, 42, 92, 88, 82, 70], optymalna partycja byłaby: ([73, 7, 21, 92, 88], [44, 43, 42, 82, 70])z różnicą 0.

Oto dość skomplikowany przykład, przeznaczony raczej do celów edukacyjnych niż do działania. Wprowadza kilka interesujących pojęć w języku Python, takich jak listy i generatory, a także dobry przykład rekurencji, w których przypadki graniczne należy odpowiednio sprawdzać. Rozszerzenia, np. Obowiązują tylko drużyny z taką samą liczbą graczy, można łatwo wdrożyć w odpowiednich indywidualnych funkcjach.

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)

Wynik:

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

Biorąc pod uwagę, że chcesz nawet drużyn, znasz docelowy wynik ocen każdej drużyny. Jest to suma ocen podzielona przez 2.

Poniższy kod powinien zrobić to, co chcesz.

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)

Wynik

first_strong_ratings 
[6, 10]

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

Istnieją inne podziały, które mają to samo fairness wszystkie są dostępne do znalezienia w kratce strong_ratings, po prostu wybieram pierwszy, ponieważ będzie on zawsze istniał dla każdej listy ocen, którą przekazujesz (pod warunkiem len(ratings) > 1).

Chciwe rozwiązanie może dać rozwiązanie nieoptymalne. Oto dość proste chciwe rozwiązanie, pomysł polega na posortowaniu listy w kolejności malejącej, aby zmniejszyć efekt dodawania ocen w wiadrze. Ocena zostanie dodana do tego segmentu, którego suma ocen jest mniejsza

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

Wynik :

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

Edytować:

Innym podejściem będzie wygenerowanie wszystkich możliwych podzbiorów listy. Załóżmy, że masz l1, który jest jednym z podzbiorów listy, a następnie możesz łatwo uzyskać listę l2, tak że l2 = lista (oryginalna) - l1. Liczba wszystkich możliwych podzbiorów listy o rozmiarze n wynosi 2 ^ n. Możemy je oznaczyć jako sekwencję liczb całkowitych od 0 do 2 ^ n -1. Weźmy przykład, powiedzmy, że masz listę = [1, 3, 5], a następnie żadna z możliwych kombinacji nie wynosi 2 ^ 3, tj. 8. Teraz możemy napisać wszystkie kombinacje w następujący sposób:

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 i 12, w tym przypadku, można łatwo uzyskać, przyjmując xor z 2 ^ n-1.

Rozwiązanie:

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

Wynik :

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