Algorithm problem

[cody]

I have to write an algorithm with must ensure that objects are put in
buckets (which are always 4 in size).
The objects have two properties: A and B. It is not allowed that in a bucket
are objects with the same A or B value. But there can be more than one
object with A = null or B = null in the bucket.

Sometimes there is only one valid solution, sometimes there are more valid
solutions, and sometimes there isn't a complete solution at all.

Iam pulling my hair out and cannot find a solution. I tried sorting the
object list by firstly A and secondly B and then adding them from the 0th to
the N-th bucket, from 0th to third slot but It does not alway dinf the
correct solution.

for (int i=0;i<buckets;i++)
for (int j=0;j<slots;j++)
Bucket[i,j]=val;

any ideas for that? hints? algorithms? links? anything?

 

[Nick Malik]

sounds like a homework problem.

OK, so you have objects with two properties, A, and B. Let's call these
objects Things (out of respect for Dr. Seuss).

class Thing
{
int A;
int B;
}

Now, we have Buckets. The methods on the bucket: (a) add a Thing to the
bucket, and (b) return a list of Things in the bucket.

class Bucket
{
bool AddThing(Thing candidate)
{
// logic goes here. If the criteria for adding to this bucket is
met, add it.
return true if the Thing was added. Return False otherwise.
}
public Bucket(int size)
{
// initialize an internal list that holds 'size' elements of type
Thing.
// the list starts out empty
}
public Thing GetThing(int index)
{
// return the Nth Thing or Null.
}
}

Create a main class (if it's a console app) or a form with a button (if it's
a windows app). In the main method, do this...
void main()
{
// create a list of buckets. Add each bucket to an Arraylist
collection.
// read a Thing in input
Thing myThing = GetAThingFromInput(); //<-- left as an exercise
// do while (InputStream is not empty)
// {
bool handled = false;
for each (Bucket currentB in myArrayList)
{
if (currentB.AddThing(myThing))
{
handled = true;
break; // <-- break out of the for loop
}
}
if (!handled)
{
// output the fact that the Thing cannot be added to any
bucket.
// This may be a termination condition. If so, break out
of the do loop.
}
// read a Thing in input
myThing = GetAThingFromInput();
// }
for each (Bucket currentB2 in myArrayList)
{
// loop on each bucket to discover it's contents
// display the contents
}
}


Kinda partial code, but the logic is solid. Hope it helps. You never said
if you like VB.NET or C#. This is in C# but there's nothing that can't be
done in VB.

--- Nick

 

[cody]

sounds like a homework problem.

Actually, it is a company problem.

OK, so you have objects with two properties, A, and B. Let's call these
objects Things (out of respect for Dr. Seuss).
[..]

Thank you for trying to help but your algorithm cannot solve the problem.
I'll explain you why:

Lets say you have following 8 input objects:

A B
1 1
2 2
3 3
4 4
5 2
6 3
7 9
8 9

With this, you could theoretically fill 2 buckets with no duplicates.
But lets see what your algorithm would do:

Bucket1:
1 1
2 2
3 3
4 4
Bucket2:
5 2
6 3
7 9
8 9

It would put all items from 1st to 4th in the first bucket and the 5th to
7th in the second bucket. Now when it reaches the 8th item there is a
duplicate.

But one of the multiple valid solutions would be:

Bucket1:
1 1
2 2
3 3
8 9
Bucket2:
5 2
6 3
7 9
4 4

Sorry my problem is not as simple as it seems on the first glimpse.

 

[phoenix]

sounds like a homework problem.

Actually, it is a company problem.

OK, so you have objects with two properties, A, and B. Let's call these
objects Things (out of respect for Dr. Seuss).
[..]

Thank you for trying to help but your algorithm cannot solve the problem.
I'll explain you why:

Lets say you have following 8 input objects:

A B
1 1
2 2
3 3
4 4
5 2
6 3
7 9
8 9

With this, you could theoretically fill 2 buckets with no duplicates.
But lets see what your algorithm would do:

Bucket1:
1 1
2 2
3 3
4 4
Bucket2:
5 2
6 3
7 9
8 9

It would put all items from 1st to 4th in the first bucket and the 5th to
7th in the second bucket. Now when it reaches the 8th item there is a
duplicate.

But one of the multiple valid solutions would be:

Bucket1:
1 1
2 2
3 3
8 9
Bucket2:
5 2
6 3
7 9
4 4

Sorry my problem is not as simple as it seems on the first glimpse.

--
cody

[Freeware, Games and Humor]
www.deutronium.de.vu || www.deutronium.tk

I think the only solution is to try every possible combination until you
find a fitting one. If you have none found after trying everything, then
there is none.

If you suspect that in a lot of cases there will be no fitting, it might be
worth to calculate the number of 'collisions' of every Thing (meaning T1.a
== T2.a || T1.b == T2.b) first. If one of these numbers is equal or higher
than the number of buckets available you will know there is no solution.

You might want to order the Thing's in the order of their collisions as
well. This might speed up the finding of a solution since it will most
likely block early saying that it can't continu in trying a certain solution
and move on to the next attempt at a solution.

Yves

 

[phoenix]

Sorry there was a mistake in that reply. The line "If one of these numbers
is equal or higher than the number of buckets available you will know there
is no solution." is incorrect, since i was talking about both properties (A
and B). If it only had been one (A or B) you got the number of collisions
from then you could make that conclusion. So maybe you should just calculate
both 'collision' numbers seperatly and then combine them for the ordening.

Yves

 

[Nick Malik]

Oh! You don't want a simple algorithm! You want a mini-max algorithm!

This falls into the category of logic programming. I used to really enjoy
algorithms like these (at my geeky best) in languages like LISP and Prolog.
I hear XSB is terrific for solving problems like this (and problems much
much harder), but I haven't had the chance to really dig into XSB yet.

What I didn't understand at first: You are not just trying to end up with
buckets. You are trying to find a path through the data to allow the least
number of buckets to hold the greatest number of items. Would that be a
correct statement?

(Sorry for calling it a homework problem. Your original description was a
lot simpler... I misunderstood).

Logic problems can be attacked with three methods: mathematical sorting,
heuristical analysis and brute force. Mathematical sorting (my term) would
require the use of higher-level calculus, and would probably be implemented
using something like a neural network... probably overkill for your
application (in addition to requiring a great deal of skill to develop and
maintain).

You could use brute force, with two alternatives. Brute force method 1 is
the backtracking method. This means that you try a combination, and if it
doesn't work, you back up to your most recent decision and change it. If
that doesn't work, you go back two decisions, change it, and follow to the
end of the tree. C# is not your friend here. You'll end up creating a
logic engine to determine your backtracking mechanism, and not only is that
difficult to do (and thus error prone), but you also tend into some higher
mathematics to prove that you don't drop into infinite loops (which is why
it took many years for Prolog to evolve into XSB). If you could post your
data into a data file, you could use XSB to do the work and then use C# to
read the data in and continue processing... (probably a pipe dream, but fun
to suggest). Brute force method 2 is combinational analysis... I'll get
back to that.

I'd like to see you use heuristical analysis. You need to create a "factor"
or "hash" function that, when applied to your inputs, will provide you with
clues as to where this object is "best" placed. The function may take, as
it's input, the complete set of assignments so far. While this is not as
powerful as either brute force method and will NOT find every possible
solution, it will find the vast majority of them and will do so much
quicker.

I'd need to know a lot more about the character of your data, over time, to
suggest the hash function, and how it would be used. You'd need to test it,
to make sure you get the results you expect.

If you need to find the solution, every single time, even when the problem
is "hard" (e.g. out of 65536 possible combinations of data, there is only
one that works), then you are probably going to have to go with one of the
brute force methods.

Combinational analysis (Brute force method 2) is what it says: you create a
list of every possible combination. Each time you add a possibility to the
list of possibilities, you check it. (A possibility includes a complete
assignment of all inputs to all buckets). The moment you find one that
works, you stop. It could take a while, depending on the statistical size
of your possibility set. Some simple pattern matching algorithms can help
you to start with "likely" combinations before moving on to the rest of what
I affectionately call "the slag heap."

Once again, without a good idea of what your data actually looks like, I
can't suggest the pattern match algorithms. I can help with the
combinational analysis brute-force list algorithm, if you'd like. I'll need
the following bits of data:

How many inputs do you have at one time?
How many buckets are you allowed to use (e.g. how many are allowed to be
partially filled?)
How much time should you spend (in milliseconds) to solve this problem?

It doesn't really matter what the attributes are: integers, complex numbers,
polynomial functions... I really don't need to know that to create the
combinational method... I would need to know that information to create your
pattern match algorithms, to start with the "likely" combinations. It's up
to you if that is something you'd like me to help with.

--- Nick

sounds like a homework problem.

Actually, it is a company problem.

OK, so you have objects with two properties, A, and B. Let's call these
objects Things (out of respect for Dr. Seuss).
[..]

Thank you for trying to help but your algorithm cannot solve the problem.
I'll explain you why:

Lets say you have following 8 input objects:

A B
1 1
2 2
3 3
4 4
5 2
6 3
7 9
8 9

With this, you could theoretically fill 2 buckets with no duplicates.
But lets see what your algorithm would do:

Bucket1:
1 1
2 2
3 3
4 4
Bucket2:
5 2
6 3
7 9
8 9

It would put all items from 1st to 4th in the first bucket and the 5th to
7th in the second bucket. Now when it reaches the 8th item there is a
duplicate.

But one of the multiple valid solutions would be:

Bucket1:
1 1
2 2
3 3
8 9
Bucket2:
5 2
6 3
7 9
4 4

Sorry my problem is not as simple as it seems on the first glimpse.

--
cody

[Freeware, Games and Humor]
www.deutronium.de.vu || www.deutronium.tk

 

[cody]

What I didn't understand at first: You are not just trying to end up with

buckets. You are trying to find a path through the data to allow the least
number of buckets to hold the greatest number of items. Would that be a
correct statement?

No. the number of buckets (tables) is given, as well as the number of items
(players).

I'd like to see you use heuristical analysis. You need to create a "factor"
or "hash" function that, when applied to your inputs, will provide you with
clues as to where this object is "best" placed. The function may take, as
it's input, the complete set of assignments so far. While this is not as
powerful as either brute force method and will NOT find every possible
solution, it will find the vast majority of them and will do so much
quicker.

I only want one solution: the best one.

Combinational analysis (Brute force method 2) is what it says: you create a
list of every possible combination. Each time you add a possibility to the
list of possibilities, you check it. (A possibility includes a complete
assignment of all inputs to all buckets). The moment you find one that
works, you stop. It could take a while, depending on the statistical size
of your possibility set.

Indeed it would take too much time.

How many inputs do you have at one time?
How many buckets are you allowed to use (e.g. how many are allowed to be
partially filled?)
How much time should you spend (in milliseconds) to solve this problem?

Ok, it is a game (skat, a cardgame). you have up to 1000 players. At each
table there must sit 4 players.
neither of them is allowed to have the same sport club number or team number
as another player at this table. If the club or team number is 0 then it
doesn't matter because it means the player is not in a team or club.

Your idea with backtracking is good, I didn't though of that. Also I notices
that if I sort the items by their properties first and then place them like
I described in the first post the algorithm often succeeds and sometimes
doesn't, depending on the sorting of the items. I could use bruteforce to
try multiple combinations.

 

[cody]

Sorry there was a mistake in that reply. The line "If one of these numbers

is equal or higher than the number of buckets available you will know there
is no solution." is incorrect, since i was talking about both properties (A
and B). If it only had been one (A or B) you got the number of collisions
from then you could make that conclusion. So maybe you should just calculate
both 'collision' numbers seperatly and then combine them for the ordening.

Good idea. I can combine this with bruteforce so I know before when to stop
trying.

 

[cody]

Hi Malik,

Iam still having trouble. Is there a way to calculate the number of
collisions in the optimum result?
My algorithm is now optimized that it returns in *most* cases the best
result.
I know want to let the algorithm repeat until the perfect result is reached
but I don't have a clue how to determine what the minimum number of
inevitable collisions is.

--
cody

Freeware Tools, Games and Humour
http://www.deutronium.de.vu || http://www.deutronium.tk

Oh! You don't want a simple algorithm! You want a mini-max algorithm!

This falls into the category of logic programming. I used to really enjoy
algorithms like these (at my geeky best) in languages like LISP and Prolog.
I hear XSB is terrific for solving problems like this (and problems much
much harder), but I haven't had the chance to really dig into XSB yet.

What I didn't understand at first: You are not just trying to end up with
buckets. You are trying to find a path through the data to allow the least
number of buckets to hold the greatest number of items. Would that be a
correct statement?

(Sorry for calling it a homework problem. Your original description was a
lot simpler... I misunderstood).

Logic problems can be attacked with three methods: mathematical sorting,
heuristical analysis and brute force. Mathematical sorting (my term) would
require the use of higher-level calculus, and would probably be implemented
using something like a neural network... probably overkill for your
application (in addition to requiring a great deal of skill to develop and
maintain).

You could use brute force, with two alternatives. Brute force method 1 is
the backtracking method. This means that you try a combination, and if it
doesn't work, you back up to your most recent decision and change it. If
that doesn't work, you go back two decisions, change it, and follow to the
end of the tree. C# is not your friend here. You'll end up creating a
logic engine to determine your backtracking mechanism, and not only is that
difficult to do (and thus error prone), but you also tend into some higher
mathematics to prove that you don't drop into infinite loops (which is why
it took many years for Prolog to evolve into XSB). If you could post your
data into a data file, you could use XSB to do the work and then use C# to
read the data in and continue processing... (probably a pipe dream, but fun
to suggest). Brute force method 2 is combinational analysis... I'll get
back to that.

I'd like to see you use heuristical analysis. You need to create a "factor"
or "hash" function that, when applied to your inputs, will provide you with
clues as to where this object is "best" placed. The function may take, as
it's input, the complete set of assignments so far. While this is not as
powerful as either brute force method and will NOT find every possible
solution, it will find the vast majority of them and will do so much
quicker.

I'd need to know a lot more about the character of your data, over time, to
suggest the hash function, and how it would be used. You'd need to test it,
to make sure you get the results you expect.

If you need to find the solution, every single time, even when the problem
is "hard" (e.g. out of 65536 possible combinations of data, there is only
one that works), then you are probably going to have to go with one of the
brute force methods.

Combinational analysis (Brute force method 2) is what it says: you create a
list of every possible combination. Each time you add a possibility to the
list of possibilities, you check it. (A possibility includes a complete
assignment of all inputs to all buckets). The moment you find one that
works, you stop. It could take a while, depending on the statistical size
of your possibility set. Some simple pattern matching algorithms can help
you to start with "likely" combinations before moving on to the rest of what
I affectionately call "the slag heap."

Once again, without a good idea of what your data actually looks like, I
can't suggest the pattern match algorithms. I can help with the
combinational analysis brute-force list algorithm, if you'd like. I'll need
the following bits of data:

How many inputs do you have at one time?
How many buckets are you allowed to use (e.g. how many are allowed to be
partially filled?)
How much time should you spend (in milliseconds) to solve this problem?

It doesn't really matter what the attributes are: integers, complex numbers,
polynomial functions... I really don't need to know that to create the
combinational method... I would need to know that information to create your
pattern match algorithms, to start with the "likely" combinations. It's up
to you if that is something you'd like me to help with.

--- Nick

sounds like a homework problem.

Actually, it is a company problem.

OK, so you have objects with two properties, A, and B. Let's call these
objects Things (out of respect for Dr. Seuss).
[..]

Thank you for trying to help but your algorithm cannot solve the problem.
I'll explain you why:

Lets say you have following 8 input objects:

A B
1 1
2 2
3 3
4 4
5 2
6 3
7 9
8 9

With this, you could theoretically fill 2 buckets with no duplicates.
But lets see what your algorithm would do:

Bucket1:
1 1
2 2
3 3
4 4
Bucket2:
5 2
6 3
7 9
8 9

It would put all items from 1st to 4th in the first bucket and the 5th to
7th in the second bucket. Now when it reaches the 8th item there is a
duplicate.

But one of the multiple valid solutions would be:

Bucket1:
1 1
2 2
3 3
8 9
Bucket2:
5 2
6 3
7 9
4 4

Sorry my problem is not as simple as it seems on the first glimpse.

--
cody

[Freeware, Games and Humor]
www.deutronium.de.vu || www.deutronium.tk

 

[Nick Malik]

I'm not sure how that statistic will help you. It certainly isn't a number
I cared much for when I was doing this kind of programming.
To be honest, I'm not completely certain which of the methods I outlined,
you are doing!
I suspect that it is heuristical analysis, especially from this question.

The minimum number of inevitable collisions is a function of the number of
teams, the average number of players on each team and the number of buckets.
I'm afraid, thick as I am first thing in the morning, that I don't have a
good understanding of the data, so I can't provide this function.

If you are trying to limit the retry loop, then set a good upper limit, and
evaluate the answer. If your app comes up dry, which it sounds like it does
on occasion, simply increase the upper limit by 20% and keep going. Limit
the number of increases (five sounds right), to prevent infinite loops.

Can you tell me, are you using heuristics or brute force combinational
analysis?

--- Nick

Hi Malik,

Iam still having trouble. Is there a way to calculate the number of
collisions in the optimum result?
My algorithm is now optimized that it returns in *most* cases the best
result.
I know want to let the algorithm repeat until the perfect result is reached
but I don't have a clue how to determine what the minimum number of
inevitable collisions is.

--
cody

Freeware Tools, Games and Humour
http://www.deutronium.de.vu || http://www.deutronium.tk

Oh! You don't want a simple algorithm! You want a mini-max algorithm!

This falls into the category of logic programming. I used to really enjoy
algorithms like these (at my geeky best) in languages like LISP and Prolog.
I hear XSB is terrific for solving problems like this (and problems much
much harder), but I haven't had the chance to really dig into XSB yet.

What I didn't understand at first: You are not just trying to end up with
buckets. You are trying to find a path through the data to allow the least
number of buckets to hold the greatest number of items. Would that be a
correct statement?

(Sorry for calling it a homework problem. Your original description was a
lot simpler... I misunderstood).

Logic problems can be attacked with three methods: mathematical sorting,
heuristical analysis and brute force. Mathematical sorting (my term) would
require the use of higher-level calculus, and would probably be implemented
using something like a neural network... probably overkill for your
application (in addition to requiring a great deal of skill to develop and
maintain).

You could use brute force, with two alternatives. Brute force method 1 is
the backtracking method. This means that you try a combination, and if it
doesn't work, you back up to your most recent decision and change it. If
that doesn't work, you go back two decisions, change it, and follow to the
end of the tree. C# is not your friend here. You'll end up creating a
logic engine to determine your backtracking mechanism, and not only is that
difficult to do (and thus error prone), but you also tend into some higher
mathematics to prove that you don't drop into infinite loops (which is why
it took many years for Prolog to evolve into XSB). If you could post your
data into a data file, you could use XSB to do the work and then use C# to
read the data in and continue processing... (probably a pipe dream, but fun
to suggest). Brute force method 2 is combinational analysis... I'll get
back to that.

I'd like to see you use heuristical analysis. You need to create a "factor"
or "hash" function that, when applied to your inputs, will provide you with
clues as to where this object is "best" placed. The function may take, as
it's input, the complete set of assignments so far. While this is not as
powerful as either brute force method and will NOT find every possible
solution, it will find the vast majority of them and will do so much
quicker.

I'd need to know a lot more about the character of your data, over time, to
suggest the hash function, and how it would be used. You'd need to test it,
to make sure you get the results you expect.

If you need to find the solution, every single time, even when the problem
is "hard" (e.g. out of 65536 possible combinations of data, there is only
one that works), then you are probably going to have to go with one of the
brute force methods.

Combinational analysis (Brute force method 2) is what it says: you

create

a
list of every possible combination. Each time you add a possibility to the
list of possibilities, you check it. (A possibility includes a complete
assignment of all inputs to all buckets). The moment you find one that
works, you stop. It could take a while, depending on the statistical size
of your possibility set. Some simple pattern matching algorithms can help
you to start with "likely" combinations before moving on to the rest of what
I affectionately call "the slag heap."

Once again, without a good idea of what your data actually looks like, I
can't suggest the pattern match algorithms. I can help with the
combinational analysis brute-force list algorithm, if you'd like. I'll need
the following bits of data:

How many inputs do you have at one time?
How many buckets are you allowed to use (e.g. how many are allowed to be
partially filled?)
How much time should you spend (in milliseconds) to solve this problem?

It doesn't really matter what the attributes are: integers, complex numbers,
polynomial functions... I really don't need to know that to create the
combinational method... I would need to know that information to create your
pattern match algorithms, to start with the "likely" combinations. It's up
to you if that is something you'd like me to help with.

--- Nick

sounds like a homework problem.

Actually, it is a company problem.

OK, so you have objects with two properties, A, and B. Let's call these
objects Things (out of respect for Dr. Seuss).
[..]

Thank you for trying to help but your algorithm cannot solve the problem.
I'll explain you why:

Lets say you have following 8 input objects:

A B
1 1
2 2
3 3
4 4
5 2
6 3
7 9
8 9

With this, you could theoretically fill 2 buckets with no duplicates.
But lets see what your algorithm would do:

Bucket1:
1 1
2 2
3 3
4 4
Bucket2:
5 2
6 3
7 9
8 9

It would put all items from 1st to 4th in the first bucket and the 5th to
7th in the second bucket. Now when it reaches the 8th item there is a
duplicate.

But one of the multiple valid solutions would be:

Bucket1:
1 1
2 2
3 3
8 9
Bucket2:
5 2
6 3
7 9
4 4

Sorry my problem is not as simple as it seems on the first glimpse.

--
cody

[Freeware, Games and Humor]
www.deutronium.de.vu || www.deutronium.tk

 

[cody]

I'm not sure how that statistic will help you. It certainly isn't a
number

I cared much for when I was doing this kind of programming.
To be honest, I'm not completely certain which of the methods I outlined,
you are doing!
I suspect that it is heuristical analysis, especially from this question.

The minimum number of inevitable collisions is a function of the number of
teams, the average number of players on each team and the number of buckets.
I'm afraid, thick as I am first thing in the morning, that I don't have a
good understanding of the data, so I can't provide this function.

If you are trying to limit the retry loop, then set a good upper limit, and
evaluate the answer. If your app comes up dry, which it sounds like it does
on occasion, simply increase the upper limit by 20% and keep going. Limit
the number of increases (five sounds right), to prevent infinite loops.

Can you tell me, are you using heuristics or brute force combinational
analysis?

I sort the players by their teams and secondly by their sport clubs. now Iam
putting the players in each bucket. Starting from bucket 1 to bucket N, I
put the players in slot 1. then I do the same for slots 2..4. If I find a
collision I iterate through all buckets a try wheather it is possible to
exchange this player with another without causing a new conflict.
This method works in 70% of all cases. Because of this, I reiterate the
whole loop ten times and at the end I pick the result with the least
conflicts, of course if I find something with conflicts==0, I prematurely
exit.
Iam not sure which word would best describe my approach but I think
"combined bruteforce and luck approach" seems to be a good description

 

[Nick Malik]

problem with this method is that you will try a number of different
combinations, but, at the end of the run, you won't know which combinations
you Haven't tried yet.

You need to think about it this way:
Logically, you create a complete list of all possible combinations. Sort
your list of combinations so that the most likely come first. Create the
combinations in order of liklihood and evaluate each one stopping when you
are done.

Practically, it is as difficult to create a list of all possible
combinations and sort it as it is to solve the problem.

The workaround for this is to find an abstraction that represents a
combination, one which is easily generated, and has an aspect that can be
sorted, but requires far less work to generate than the complete
combination.

(in this discussion, a combination is a complete assignment set of all
players to all buckets).

The easiest for me has always been a string generator where a single
character represents a player (not their id, just their attributes). Then,
the list of all possible combinations is simply a generator for every
possible combination of characters.

When you hit on a combination that works (e.g. a string that passes your
test), then you use that string to find the players to fill your buckets.

Does this make sense?

-- Nick

 

[cody]

problem with this method is that you will try a number of different

combinations, but, at the end of the run, you won't know which combinations
you Haven't tried yet.

As I said, I try maximum 10 combinations. That is, I let my algorithm work
10 times, each with different random sorting of the input data. And it works
very well at the moment.

The problem with your suggestion is that there are 1million combinations
(for 1000 players). And if I would create abstractions for one combination
say 1 byte per player I would have 1000bytes*1million possibilities.
impossible.
And how can I sort them by their likelyhood?

 

[Nick Malik]

Yes, the bit about 1000 players... you'd mentioned that and I had not kept
that in mind.
In 1000 players, how many sport clubs will there be. In each sport club,
how many teams? In each team, how many players?

You really should do this with heuristical analysis, because of the
combinational explosion. Even backtracking would probably take a while, and
this doesn't sound so difficult to do heuristically. You are doing quite a
bit already. I'm going to think "aloud" for a minute. See if my logic
makes sense to the problem.

The goal is to prevent two players from a sport club at the same table, and
to prevent two players from the same team at the same table, right? A table
holds four people.

If a team is a subset of a sport club, then logically, you only have the
number of sport clubs in your population.
If you have 1000 players, represented by 35 sport clubs, then your
population is 35.

The rest of this discussion is based upon this very simple statement. If
this is an oversimplification, then I am going off into the weeds.

I'd like to validate my assumption:
First off: can a team be comprised of individuals from two different sport
clubs? (With a variation: if a team contains three members of a sport club,
and a fourth person who is, before this tournament, unaffiliated, should
this fourth person be considered, for the duration of the tournament, as
though they were a member of both the sport club and the team? This
matters. I assume that you can make this "assignment" and that, in fact, it
is a requirement that is hidden in the numbers. If, on the other hand, the
unaffiliated individual can be considered to be a member of the team, but
not the club, then you have MORE possible solutions. I'm assuming the most
restrictive...)

Another assumption: A person who is not affiliated with a sport club should
be considered to be affiliated with their own sport club. Also that a team
that is not part of a club, should be considered to be in their own club for
the duration of the tournament.

Back to my sample idea, which uses my assumptions. I want to validate that
heuristics will work. Let's do some grouping...

If you have 1000 players, represented by 35 sport clubs for example, then
your population is 35.
If you have 1000 players, you have 80 that are not affiliated with a club or
team, and you have 35 registered clubs, your population is 115.
If you have 1000 players, with 35 clubs, 6 teams that are not in a club (4
players each) and 8 solo individuals, you have a population of 49.

Are we on the same page?

If you have a population of 35, the number of VALID combinations is high,
since there's over 1M combinations that can be placed in four places at the
table. However, if you have only 8, the number of VALID combinations is
fairly low (1680). Regardless, this combinational value is still very good
for heuristical analysis.

Your trick is to find a set of patterns, representing the allocation of
club-players to tables, where the sum of the players (by club) in the
solution set equals the actual break down of players by club in the
tournament enrollment.

There are some easy hueristics that can be used to find out things that
don't work...

For example, if you have 20 players in 4 clubs (A brings 2, B brings 6, C
brings 7, and D brings 5), you know already that there is no exact
solution... because the only combinations that can work would require you to
have 7 tables (one each with a player from C), and yet 7 tables would hold
28 players, which you don't have.

So, starting with the most restrictive situation (the club with the largest
number of players), you should be able to create groups that you know will
work.

For example, with 100 players, you have 25 tables.

Therefore if one club brings 20 players, you could start by grouping that
club with another club that brings five players. (20 + 5 = number of
tables). Call these A and J clubs. So, start with 25 empty buckets, and
assign A to each bucket (for a total of 20), and then J (for a total of 5).
You have filled up the first slot in each table in a manner that you know
will not cause a conflict with any other possible combination.

Now, club B brings 18 players. You do not have any clubs with 7 players,
but you do have an unaffiliated team with 4 players (call them K). So, you
can make a group containing club B, "club" K, and three unaffiliated
players. Place one player from this new group into slot two at each table.

Now you have only a smattering of teams (of four players) and some
individuals. Remember that each team makes a club, and each individual is
in their own "club". Create two remaining groups of 25 each. The rules of
the grouping: if one player in a club are in a group, then all players from
the club are in the group.

Scatter one player from group 3 in each slot 3. Scatter one player from
group 4 in each slot 4.

You should have a working set.

The key to this idea is that you don't really have individuals... and you
don't really have two attributes. You have one attribute: membership in a
group that will conflict with another player at the same table. This is
what I'm calling "club." So, you always have to assign up the heirarchy.
If a club doesn't exist, create one for the sake of the algorithm. This is
the abstraction that my algorithm depends on.

It is possible that this method doesn't work, but it should, given the fact
that the combinational patterns are so large. If you had 1000 players, and
only one right answer, and the number of attributes were very high (to the
point where you couldn't reasonably abstract them down to one, as I've done
here), then brute force makes more sense.

See if this works for you.

 

[cody]

The goal is to prevent two players from a sport club at the same table,
and

to prevent two players from the same team at the same table, right? A table
holds four people.
xactly!

If a team is a subset of a sport club, then logically, you only have the
number of sport clubs in your population.
If you have 1000 players, represented by 35 sport clubs, then your
population is 35.

No. A team and a sportsclub is totally different here and has nothing to do
with each other. People of different or the same sportsclub can join
together in a team.
There are also players with no sportsclub and/or no team.
Somebody with no team can play on the same table with players of any team or
players which do not have a team.
Somebody with no sportsclub can play together with players of any sportsclub
and with players without club.

in short:

bool conflict = otherplayersClub!=null && otherplayersClub==thisPlayersClub
|| otherplayersTeam!=null &&
otherplayersTeam==thisPlayersTeam;

Sorry to say, but this makes all you following assumptions invalid

 

[Nick Malik]

Hi Cody,

Yes, you are right. I assumed myself right into a box.

Time to start over. Here's the rules:
a) a player may be unaffiliated with a team or sport club. That player may
play with anyone else in the tournament.
b) a player may be affiliated with a team but not a club. That player may
play with anyone not on their team.
c) a player may be affiliated with a club but not a team. That player may
play with anyone not in their club.
d) a player may be affiliated with both a club and a team. That player may
play with others who are not members of either group.

Four players per table.

(by the way, what happens if the total numbr of players is not evenly
divisible by four?).

Calculation: take the number of players. divide by four and round down to
the nearest integer. That's the number of tables.
Goal: place players at tables according to the rules above.

I sat here for a few minutes with a whiteboard writing up Venn diagrams. I
find that, when doing this by hand, I still start with the most restrictive
group. Players group out in the following ways (most restrictive to least
restrictive):
1) any club player who is part of a team where one or more members of the
team are affiliated with a different club.
2) any club player who is part of a team that contains unaffiliated players,
3) any club player in a team where all teammates are in the same club, or
any unaffiliate player on a team of unaffiliated players
4) any club players not on a team.
5) players in neither a club nor a team.

So, I suggest that you do these steps:
1) calculate the number of tables. Initialize an ordered list of table
objects.
2) if you have any club with more members than there are tables in the game,
stop. No solution is possible.
3) take your set of players and sort them into the five buckets above.
(literally, create an object for each player and place them into one of five
ordered lists).
4) Start a loop, initializing a "table pointer" so that you continue to
cycle through the tables in order.
[As infinite loops are possible with this algorigthm, limit the
loop in a sensable manner.]

4a) Pick off the top player in the most restrictive group available.
4b) Attempt to place the player at the next table.
4c) If the attempt fails, call a routine to perform a "failure run"
which means to loop through the list of tables exactly once, starting from
the failing table, looking for a table that can take this player. If found,
continue to step 4d. If not:
4c.i -- scan the tables looking for another player that is seated
that has the same restriction level.
4c.ii -- If found, check if they are compatible and the player is
not marked as 'sticky'.
4c.iii -- If so, check if a swap would be legal.
4c.iv -- If so, swap the players.
4c.iv.1 : Mark the swapped player as 'sticky' so it
won't be swapped again.
4c.iv.2 : take the swapped player and place it back
on top of its restriction group, LIFO, so that it will be the next one to
pop off.
4.c.v -- if no swap occurs, stop. You have an unsolvable
problem.
4d) increment the table pointer
5) If you have ended the loop but still have players in the buckets that
are not placed, assume that they cannot be placed, and stop.

In english, this algorithm can be explained as follows. (I'm being
repetitive for the sake of clarity).

Starting with empty tables, attempt to fill an empty slot of each table with
players from the most restrictive bucket available and check for conflicts.
If a conflict is found, move the conflicting player to the next table,
leaving a slot open at the offending table. Cycle through the complete set
of tables five times. That should allow all players to be placed (since the
players at the end will all be less restrictive, and therefore trivial to
place).

I will add one collision rule: if you have a player that cannot be placed at
any remaining open slots, then scan the tables looking for another player in
the same restriction group that is completely non-conflicting (e.g. they
could play together), where a swap would be legal. Swap them. Then go and
find a home for the newly swapped player. If you really want to get
elaborate, add this wrinkle: If you cannot find a legal swap with a player
of the same restriction group that is non conflicting, try to find a legal
swap with any players in the same group that are partially conflicting (team
but not club or vice versa). If that fails, stop... you have an unsolvable
problem.

I ran through this a few times on my whiteboard and it worked reliably.

It became much easier with the greater number of players because the odds go
up that you won't overload with players in the most restrictive groups.

I hope this helps (finally).

--- Nick

 

[cody]

(by the way, what happens if the total numbr of players is not evenly

divisible by four?).

In that case, on the last few tables there are only 3 players placed. Every
number can be composed from combinations of 3 or 4's.
This works only if the number of players is 3,4 or >=6.

I sat here for a few minutes with a whiteboard writing up Venn diagrams. I
find that, when doing this by hand, I still start with the most restrictive
group. Players group out in the following ways (most restrictive to least
restrictive):
1) any club player who is part of a team where one or more members of the
team are affiliated with a different club.
2) any club player who is part of a team that contains unaffiliated players,
3) any club player in a team where all teammates are in the same club, or
any unaffiliate player on a team of unaffiliated players
4) any club players not on a team.
5) players in neither a club nor a team.

Good idea. I didn't thought of it this way. The rest of your solution is
similar to that what I have so far yet, that means Iam on the right way

Thank you very much for your great help!