- Edited
Some theory to start with
Let's assume that we have an even number of players, say 50. The number of ways we can take from these 50 players into the first team is given by:
combinations_players(50) = 50! / 25! / 25! = 126,410,606,437,752
Compare to: combinations_players(20) = 20! / 10! / 10! = 184,756
Since there's apparently no greedy solution to the problem (not proved, not to discourage), the problem disintegrates into a problem of generating all combinations, checking each of them for their sum property, and taking out the minimum.
@George: I think I am starting to build a hunch for this elusive problem. It's not easy to benchmark it since some cases return almost immediately (when there's an exact match for a half) or almost never return when using large inputs.
So for, my first trial with reorienting the first piece of code to work with missed constraints has failed. Teams of fifty are crashing the app without any return. I have one solution that uses almost no memory, but I am more inclined to generic graph solutions.
I was hoping I could find a greedy algorithm to fit, but apparently I can't connect all the dots correctly. I am stuck with a failing solution for the time being. None the less, it handles odd counts of people, and returns partitions that are one item in length apart.
Here's what I got so far (for an input of 20 scores, it has to close 388593 of some kind of steps. Not cool.
C++0x, VS2010
Let's assume that we have an even number of players, say 50. The number of ways we can take from these 50 players into the first team is given by:
combinations_players(50) = 50! / 25! / 25! = 126,410,606,437,752
Compare to: combinations_players(20) = 20! / 10! / 10! = 184,756
Since there's apparently no greedy solution to the problem (not proved, not to discourage), the problem disintegrates into a problem of generating all combinations, checking each of them for their sum property, and taking out the minimum.
@George: I think I am starting to build a hunch for this elusive problem. It's not easy to benchmark it since some cases return almost immediately (when there's an exact match for a half) or almost never return when using large inputs.
So for, my first trial with reorienting the first piece of code to work with missed constraints has failed. Teams of fifty are crashing the app without any return. I have one solution that uses almost no memory, but I am more inclined to generic graph solutions.
I was hoping I could find a greedy algorithm to fit, but apparently I can't connect all the dots correctly. I am stuck with a failing solution for the time being. None the less, it handles odd counts of people, and returns partitions that are one item in length apart.
Here's what I got so far (for an input of 20 scores, it has to close 388593 of some kind of steps. Not cool.
closed nodes 388593
[ 27 34 36 42 45 58 62 64 67 69 ] [ 0 5 24 27 41 61 78 81 91 95 ]
difference = 1C++0x, VS2010
#include <iostream>
#include <set>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct node {
vector<int> left;
vector<int> right;
int sum_left;
int sum_right;
bool operator<(node const & n) const{
return lexicographical_compare(left.begin(), left.end(), n.left.begin(), n.left.end());
}
int diff() const {
return sum_left - sum_right;
}
list<node> neighbours(){
list<node> result;
for(unsigned i = 0; i < left.size(); i++){
if((left.size() >= right.size()) && (sum_left - left[i] > sum_right + left[i])){
node cpy(*this);
cpy.left.erase(cpy.left.begin() + i);
cpy.right.insert(lower_bound(cpy.right.begin(), cpy.right.end(), left[i]), left[i]);
cpy.sum_left -= left[i];
cpy.sum_right += left[i];
result.push_back(cpy);
}
}
return result;
}
};
struct node_less_optimal {
bool operator()(node const & a, node const & b){
return a.diff() > b.diff();
}
};
int main(){
//int arr[] = {2, 3, 6, 2, 4, 5, 10, 8, 7};
vector<int> v; //(arr, arr+sizeof(arr)/sizeof(arr[0]));
for(int i = 0; i < 20; i++){
v.push_back(rand()%100);
}
sort(v.begin(), v.end());
node start;
start.left = v;
int sum = 0; for_each(start.left.begin(), start.left.end(), [&sum](int x){ sum += x;});
start.sum_left = sum;
start.sum_right = 0;
set<node> close;
priority_queue<node, vector<node>, node_less_optimal> open;
open.push(start);
node c;
node optimum = start;
node_less_optimal comp;
while(open.size() > 0){
c = open.top();
if((c.left.size() <= c.right.size() + 1) && c.diff() == 0){
optimum = c;
break;
}
close.insert(c);
if((c.left.size() <= c.right.size() + 1) && comp(optimum, c))
optimum = c;
open.pop();
auto ns = c.neighbours();
for_each(ns.begin(), ns.end(), [&close, &open](node n){
if(close.find(n)==close.end())
open.push(n);
});
}
cout << "closed nodes " << close.size() << endl;
cout << "[ ";
for_each(optimum.left.begin(), optimum.left.end(), [](int x){cout << x << " ";});
cout << "] [ ";
for_each(optimum.right.begin(), optimum.right.end(), [](int x){cout << x << " ";});
cout << "]" << endl;
cout << "difference = " << optimum.diff() << endl;
return 0;
}