플레이어의 등급 목록이 주어지면 플레이어 (즉 등급)를 가능한 한 두 그룹으로 나눠야합니다. 목표는 팀의 누적 평가 차이를 최소화하는 것입니다. 플레이어를 팀으로 나눌 수있는 방법에 대한 제약은 없습니다 (한 팀에는 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로 설정 - 설정
up_down = true;
:이 부울은 현재 진행 중인지 (true) 또는 진행 중인지 (false)를 나타냅니다.
while 루프 :
-
(up_down) 인 경우 : 전달
- 의 도움으로 조기 포기 테스트
sum_back
- 가장 가능한 값
sum
을 선택하고이 선택에 따라 조정하십시오 if (i == n-1)
: LEAF-> 최적 값이 개선되었는지 테스트하고 새로운 값이 0이면 리턴합니다 (편집 🙂if (... < 2)
; 뒤로 가다- 잎이없는 경우 : 계속 진행
- 의 도움으로 조기 포기 테스트
-
만약 (! updown) : 뒤로
- 우리가 도착하면
i == 0
: return - 이 노드에서 두 번째 보행인 경우 : 두 번째 값을 선택하고 위로 이동하십시오.
- 다른 : 내려가
- 두 경우 모두 : 새
sum
값을 다시 계산
- 우리가 도착하면
다음은 C ++ 코드입니다 (죄송합니다, 파이썬을 몰라)
#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
0이 되 자마자 멈추기 위해 몇 줄을 추가하도록 남겨 두었습니다 (물론 더 나아질 수 없기 때문에).
비트 온 비트 ( 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
1 뒤에 7 개의 0이옵니다. 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
)
답변
다음 알고리즘이이를 수행합니다.
- 항목을 정렬
- 짝수 멤버를 list에 넣고 list
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
.
답변
다음은 성과보다는 교육 목적을위한 상당히 정교한 예입니다. 리스트 이해 및 생성기와 같은 흥미로운 파이썬 개념과 프린지 사례를 적절히 점검해야하는 재귀의 좋은 예를 소개합니다. 예를 들어 같은 수의 팀을 가진 팀만 유효한 확장은 적절한 개별 기능으로 쉽게 구현할 수 있습니다.
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 = list (original)-l1과 같이 목록 l2를 쉽게 얻을 수 있습니다. 크기 n의 목록에서 가능한 모든 하위 집합의 수는 2 ^ n입니다. 0에서 2 ^ n -1 사이의 정수의 seq로 나타낼 수 있습니다. 예를 들어 list = [1, 3, 5]라고 가정하면 가능한 조합은 2 ^ 3 즉 8입니다. 이제 모든 조합을 다음과 같이 쓸 수 있습니다.
- 000-[]-0
- 001-[1]-1
- 010-[3]-2
- 011-[1,3]-3
- 100-[5]-4
- 101-[1,5]-5
- 110-[3,5] -6
- 이 경우 111-[1,3,5]-7 및 l2는 2 ^ n-1로 xor를 취함으로써 쉽게 얻을 수 있습니다.
해결책:
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]