Справедливое разбиение элементов списка

Учитывая список рейтингов игроков, я должен разделить игроков (то есть рейтинги) на две группы как можно более справедливо. Цель состоит в том, чтобы минимизировать разницу между совокупным рейтингом команд. Нет никаких ограничений относительно того, как я могу разделить игроков на команды (одна команда может иметь 2 игрока, а другая команда может иметь 10 игроков).

Например: [5, 6, 2, 10, 2, 3, 4]должен вернуться([6, 5, 3, 2], [10, 4, 2])

Я хотел бы знать алгоритм для решения этой проблемы. Пожалуйста, обратите внимание, что я прохожу вводный курс по программированию в Интернете, поэтому были бы полезны простые алгоритмы.

Я использую следующий код, но по какой-то причине он-лайн проверка кода говорит, что он неправильный.

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)

Обновление: я связался с инструкторами, и мне сказали, что я должен определить другую «вспомогательную» функцию внутри функции, чтобы проверить все различные комбинации, а затем мне нужно проверить минимальную разницу.

Примечание: отредактировано для лучшей обработки случая, когда сумма всех чисел нечетна.

Возврат является возможным для этой проблемы.

Это позволяет рекурсивно исследовать все возможности без необходимости большого объема памяти.

Он останавливается, как только найдено оптимальное решение: sum = 0где sumразница между суммой элементов множества A и суммой элементов множества B. РЕДАКТИРОВАТЬ: останавливается сразу же sum < 2, чтобы обработать случай, когда сумма всех чисел является нечетным, то есть соответствует минимальной разнице 1. Если эта глобальная сумма четна, минимальная разница не может быть равна 1.

Это позволяет реализовать простую процедуру преждевременного отказа :
в данное время, если sumоно больше, чем сумма всех оставшихся элементов (т.е. не помещенных в A или B) плюс абсолютное значение полученного текущего минимума, тогда мы можем отказаться от проверки текущий путь, без изучения оставшихся элементов. Эта процедура оптимизирована с помощью:

• сортировать входные данные в порядке убывания
• На каждом этапе сначала изучите наиболее вероятный выбор: это позволяет быстро перейти к почти оптимальному решению.

Вот псевдокод

Инициализация:

• сортировать элементы a[]
• Рассчитать сумму оставшихся элементов: sum_back[i] = sum_back[i+1] + a[i];
• Установите минимальную «разницу» в ее максимальное значение: min_diff = sum_back[0];
• Положите a[0]в A -> индекс iисследуемого элемента установлен в 1
• Set up_down = true;: это логическое значение указывает, движемся ли мы в данный момент вперед (true) или назад (false)

Пока цикл:

• Если (up_down): вперед

  • Тест преждевременного отказа, с помощью sum_back
  • Выберите наиболее вероятное значение, отрегулируйте в sumсоответствии с этим выбором
  • if (i == n-1): LEAF -> проверить, улучшено ли оптимальное значение, и вернуть, если новое значение равно 0 (РЕДАКТИРОВАТЬ: if (... < 2) ; идти назад
  • Если не в листе: продолжать идти вперед

• Если (! Updown): назад

  • Если мы приедем в i == 0 : возврат
  • Если это вторая прогулка в этом узле: выберите второе значение, поднимитесь
  • еще: идти вниз
  • В обоих случаях: пересчитать новое sumзначение

Вот код на C ++ (извините, не знаю 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";
}

Я думаю, что вы должны выполнить следующее упражнение самостоятельно, иначе вы многому не научитесь. Что касается этого, вот решение, которое пытается реализовать рекомендации вашего инструктора:

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

Вывод:

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

Обратите внимание, что этот вывод отличается от желаемого, но оба они верны.

Этот алгоритм основан на том факте, что для выбора всех возможных подмножеств данного набора с N элементами вы можете сгенерировать все целые числа с N битами и выбрать I-й элемент в зависимости от значения I-го бита. Я оставляю вам, чтобы добавить пару строк, чтобы остановить, как только best_distanceноль (потому что, конечно, не может быть лучше).

Бит по битам (обратите внимание, что 0bэто префикс для двоичного числа в Python):

Двоичное число: 0b0111001 == 0·2⁶+1·2⁵+1·2⁴+1·2³+0·2²+0·2¹+1·2⁰ == 57

Сдвиг вправо на 1: 0b0111001 >> 1 == 0b011100 == 28

Сдвиг влево на 1: 0b0111001 << 1 == 0b01110010 == 114

Сдвиг вправо на 4: 0b0111001 >> 4 == 0b011 == 3

Побитовый &(и):0b00110 & 0b10101 == 0b00100

Чтобы проверить, равен ли 5-й бит (индекс 4) 1: (0b0111001 >> 4) & 1 == 0b011 & 1 == 1

Один, за которым следуют 7 нулей: 1 << 7 == 0b10000000

7 из них: (1 << 7) - 1 == 0b10000000 - 1 == 0b1111111

Все 3-битовые комбинации: 0b000==0, 0b001==1, 0b010==2, 0b011==3, 0b100==4, 0b101==5, 0b110==6, 0b111==7(заметим , что 0b111 + 1 == 0b1000 == 1 << 3)

Следующий алгоритм делает это:

• сортирует предметы
• помещает четные элементы в список a, нечетные в списке, bчтобы начать
• случайным образом перемещает и меняет позиции между, aи bесли изменение к лучшему

Я добавил операторы печати, чтобы показать прогресс в вашем списке примеров:

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

Вывод:

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

Поскольку я знаю, что должен сгенерировать все возможные списки, мне нужно создать вспомогательную функцию, чтобы помочь сгенерировать все возможности. После этого я проверяю минимальную разницу, и комбинация списков с этой минимальной разницей является желаемым решением.

Вспомогательная функция является рекурсивной и проверяет все возможности комбинаций списков.

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)

Примеры:, r = [1, 2, 2, 3, 5, 4, 2, 4, 5, 5, 2]оптимальный раздел будет: ([1, 2, 2, 3, 5, 4], [2, 4, 5, 5, 2])с разницей 1.

r = [73, 7, 44, 21, 43, 42, 92, 88, 82, 70]оптимальным разделом будет: ([73, 7, 21, 92, 88], [44, 43, 42, 82, 70])с разницей 0.

Вот довольно сложный пример, предназначенный для образовательных целей, а не для производительности. В нем представлены некоторые интересные концепции Python, такие как списки и генераторы, а также хороший пример рекурсии, в которой необходимо надлежащим образом проверять дополнительные случаи. Расширения, например, действительны только команды с равным количеством игроков, легко реализуются в соответствующих индивидуальных функциях.

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)

Вывод:

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

Учитывая, что вам нужны даже команды, вы знаете целевой рейтинг рейтингов каждой команды. Это сумма рейтингов, деленная на 2.

Поэтому следующий код должен делать то, что вы хотите.

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)

Вывод

first_strong_ratings 
[6, 10]

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

Есть другие сплиты, которые имеют то же самое fairness, что все они доступны для поиска в кортеже strong_ratings, я просто выберу первый, так как он всегда будет существовать для любого списка рейтингов, который вы передаете (при условии len(ratings) > 1).

Жадное решение может привести к неоптимальному решению. Вот довольно простое жадное решение, идея состоит в том, чтобы отсортировать список по убыванию, чтобы уменьшить эффект добавления рейтингов в корзину. Рейтинг будет добавлен в тот сегмент, чья общая сумма рейтинга меньше

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

Вывод :

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

Редактировать:

Другой подход заключается в создании всех возможных подмножеств списка. Допустим, у вас есть l1, который является одним из подмножеств списка, тогда вы можете легко получить список l2 такой, что l2 = list (original) - l1. Количество всех возможных подмножеств списка размера n равно 2 ^ n. Мы можем обозначить их как последовательность целого числа от 0 до 2 ^ n -1. Возьмем пример, скажем, у вас есть список = [1, 3, 5], тогда ни одна из возможных комбинаций не равна 2 ^ 3, то есть 8. Теперь мы можем записать все комбинации следующим образом:

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 и l2 в этом случае можно легко получить, взяв xor с 2 ^ n-1.

Решение:

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

Вывод :

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