Partisi elemen yang adil dari daftar

Diberi daftar peringkat pemain, saya diharuskan mempartisi pemain (yaitu peringkat) menjadi dua kelompok seadil mungkin. Tujuannya adalah untuk meminimalkan perbedaan antara peringkat kumulatif tim. Tidak ada batasan bagaimana saya dapat membagi pemain menjadi tim (satu tim dapat memiliki 2 pemain dan tim lain dapat memiliki 10 pemain).

Misalnya: [5, 6, 2, 10, 2, 3, 4]harus kembali([6, 5, 3, 2], [10, 4, 2])

Saya ingin mengetahui algoritme untuk menyelesaikan masalah ini. Harap dicatat saya mengambil kursus pengantar pemrograman online, jadi algoritma sederhana akan dihargai.

Saya menggunakan kode berikut, tetapi karena suatu alasan, pemeriksa kode online mengatakan itu tidak benar.

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)

Pembaruan: Saya menghubungi instruktur dan saya diberitahu bahwa saya harus mendefinisikan fungsi "pembantu" lain di dalam fungsi untuk memeriksa semua kombinasi yang berbeda maka saya perlu memeriksa perbedaan minimum.

Catatan: Diedit untuk menangani case dengan lebih baik ketika jumlah semua angka ganjil.

Mundur adalah kemungkinan untuk masalah ini.

Hal ini memungkinkan untuk memeriksa semua kemungkinan secara rekursif, tanpa perlu banyak memori.

Itu berhenti segera setelah solusi optimal ditemukan:, di sum = 0mana sumperbedaan antara jumlah elemen himpunan A dan jumlah elemen himpunan B. EDIT: berhenti segera sum < 2, untuk menangani kasus ketika jumlah semua angka ganjil, yaitu terkait dengan perbedaan minimum 1. Jika jumlah global ini genap, perbedaan min tidak dapat sama dengan 1.

Hal ini memungkinkan untuk menerapkan prosedur sederhana pengabaian prematur :
pada waktu tertentu, jika sumlebih tinggi maka jumlah semua elemen yang tersisa (yaitu tidak ditempatkan di A atau B) ditambah nilai absolut dari minimum saat ini yang diperoleh, maka kita dapat menyerah memeriksa jalan saat ini, tanpa memeriksa elemen yang tersisa. Prosedur ini dioptimalkan dengan:

• mengurutkan input data dalam urutan menurun
• Pada setiap langkah, pertama-tama periksa pilihan yang paling mungkin: ini memungkinkan untuk pergi dengan cepat ke solusi yang hampir optimal

Ini adalah pseudo-code

Inisialisasi:

• mengurutkan elemen a[]
• Hitung jumlah elemen yang tersisa: sum_back[i] = sum_back[i+1] + a[i];
• Setel "perbedaan" minimum ke nilai maksimum: min_diff = sum_back[0];
• Masukkan a[0]A -> indeks ielemen yang diperiksa diatur ke 1
• Set up_down = true;: boolean ini menunjukkan apakah kita sedang maju (benar) atau mundur (salah)

Sementara loop:

• If (up_down): maju

  • Tes pengabaian prematur, dengan bantuan sum_back
  • Pilih nilai yang paling mungkin, sesuaikan sumdengan pilihan ini
  • if (i == n-1): LEAF -> tes jika nilai optimal ditingkatkan dan kembali jika nilai baru sama dengan 0 (EDIT:) if (... < 2); mundur
  • Jika tidak di daun: terus maju

• If (! Updown): mundur

  • Jika kami tiba di i == 0: kembali
  • Jika ini adalah langkah kedua di simpul ini: pilih nilai kedua, naik
  • lain: turun
  • Dalam kedua kasus: menghitung ulang baru sumnilai

Berikut adalah kode, dalam C ++ (Maaf, tidak tahu 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";
}

Saya pikir Anda harus melakukan latihan berikutnya sendiri, kalau tidak Anda tidak belajar banyak. Adapun yang ini, berikut adalah solusi yang mencoba menerapkan saran oleh instruktur Anda:

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

Keluaran:

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

Perhatikan bahwa output ini berbeda dari yang Anda inginkan, tetapi keduanya benar.

Algoritma ini didasarkan pada fakta bahwa, untuk memilih semua himpunan bagian yang mungkin dari himpunan yang ditentukan dengan elemen N, Anda dapat menghasilkan semua bilangan bulat dengan bit N, dan memilih item ke-I tergantung pada nilai bit ke-1. Saya meninggalkan Anda untuk menambahkan beberapa baris untuk berhenti segera setelah best_distancenol (karena tentu saja tidak bisa lebih baik).

Sedikit bit (perhatikan bahwa itu 0badalah awalan untuk nomor biner dengan Python):

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

Bergeser kanan sebanyak 1: 0b0111001 >> 1 == 0b011100 == 28

Kiri bergeser 1: 0b0111001 << 1 == 0b01110010 == 114

Bergeser kanan sebanyak 4: 0b0111001 >> 4 == 0b011 == 3

Bitwise &(dan):0b00110 & 0b10101 == 0b00100

Untuk memeriksa apakah bit ke-5 (indeks 4) adalah 1: (0b0111001 >> 4) & 1 == 0b011 & 1 == 1

Yang diikuti oleh 7 nol: 1 << 7 == 0b10000000

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

Semua kombinasi 3-bit: 0b000==0, 0b001==1, 0b010==2, 0b011==3, 0b100==4, 0b101==5, 0b110==6, 0b111==7(catatan bahwa 0b111 + 1 == 0b1000 == 1 << 3)

Algoritme berikut melakukan ini:

• macam barang
• menempatkan anggota genap dalam daftar a, ganjil dalam daftar buntuk memulai
• secara acak memindahkan dan menukar item di antara adan bjika perubahannya menjadi lebih baik

Saya telah menambahkan pernyataan cetak untuk menunjukkan perkembangan pada daftar contoh Anda:

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

Keluaran:

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

Karena saya tahu saya harus membuat semua daftar yang mungkin, saya perlu membuat fungsi "pembantu" untuk membantu menghasilkan semua kemungkinan. Setelah melakukan itu, saya benar untuk memeriksa perbedaan minimum, dan kombinasi daftar dengan perbedaan minimum adalah solusi yang diinginkan.

Fungsi helper bersifat rekursif, dan memeriksa semua kemungkinan kombinasi daftar.

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)

Contoh r = [1, 2, 2, 3, 5, 4, 2, 4, 5, 5, 2]:, partisi optimal adalah: ([1, 2, 2, 3, 5, 4], [2, 4, 5, 5, 2])dengan perbedaan 1.

r = [73, 7, 44, 21, 43, 42, 92, 88, 82, 70], partisi optimal adalah: ([73, 7, 21, 92, 88], [44, 43, 42, 82, 70])dengan perbedaan 0.

Berikut adalah contoh yang cukup rumit, yang dimaksudkan untuk tujuan pendidikan daripada kinerja. Ini memperkenalkan beberapa konsep Python yang menarik seperti daftar pemahaman dan generator, serta contoh yang baik dari rekursi di mana kasus pinggiran perlu diperiksa dengan tepat. Ekstensi, mis. Hanya tim dengan jumlah pemain yang sama yang valid, mudah diimplementasikan dalam fungsi individu yang sesuai.

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)

Keluaran:

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

Mengingat Anda menginginkan tim yang merata, Anda tahu skor target dari peringkat masing-masing tim. Ini adalah jumlah peringkat yang dibagi 2.

Jadi kode berikut harus melakukan apa yang Anda inginkan.

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)

Keluaran

first_strong_ratings 
[6, 10]

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

Ada pemisahan lain yang memiliki yang sama fairnessini semua tersedia untuk menemukan di dalam tuple strong_ratings, saya hanya memilih untuk melihat yang pertama karena ini akan selalu ada untuk daftar peringkat yang Anda lewati (disediakan len(ratings) > 1).

Solusi serakah mungkin menghasilkan solusi sub-optimal. Berikut ini adalah solusi serakah yang cukup sederhana, idenya adalah untuk mengurutkan daftar dalam urutan menurun untuk mengurangi efek penambahan peringkat dalam ember. Peringkat akan ditambahkan ke ember yang jumlah total peringkatnya kurang

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

Keluaran:

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

Edit:

Pendekatan lain akan menghasilkan semua himpunan bagian yang mungkin dari daftar. Katakanlah Anda memiliki l1 yang merupakan salah satu himpunan bagian dari daftar, maka Anda dapat dengan mudah mendapatkan daftar l2 sehingga l2 = daftar (asli) - l1. Jumlah semua bagian yang mungkin dari daftar ukuran n adalah 2 ^ n. Kita dapat menyatakannya sebagai seq bilangan bulat dari 0 hingga 2 ^ n -1. Ambil contoh, misalkan Anda memiliki list = [1, 3, 5] maka tidak ada kombinasi yang mungkin adalah 2 ^ 3 yaitu 8. Sekarang kita dapat menulis semua kombinasi sebagai berikut:

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 dan l2, dalam hal ini, dapat dengan mudah diperoleh dengan mengambil xor dengan 2 ^ n-1.

Larutan:

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

Keluaran:

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