metalaureate
asked on
Determining the final winners and all of its losers in a list of win/lose pairs
I'm having trouble figuring out the logic for the following problem - the application is a de-duping process that has to merge the contents of the duplicates:
I have a list of pairs of winners and losers
e.g.
9962261 wins over 9962260
9962263 wins over 9962261
9962263 wins over 9962260
In this example, 9962263 is the winner, and wins out over 9962260 and 9962261.
imagine thousands of such contests expressed as records like this
how do i algorithmically end up with an array of the form
winner1, [list of losers]
winner2, [list of losers]
winner3, [list of losers]
such that there is no winner that is also a loser.
My logic fails me.
I have a list of pairs of winners and losers
e.g.
9962261 wins over 9962260
9962263 wins over 9962261
9962263 wins over 9962260
In this example, 9962263 is the winner, and wins out over 9962260 and 9962261.
imagine thousands of such contests expressed as records like this
how do i algorithmically end up with an array of the form
winner1, [list of losers]
winner2, [list of losers]
winner3, [list of losers]
such that there is no winner that is also a loser.
My logic fails me.
I don't know if I'm able enough to help you, but sure I (and all other experts, I think) need to know how is formatted your original list: is it an ssociative array where the key is the winner and the value the looser? Or is it something else?
And the result you wish is, following your example, an array of array as the following one?
9962263 => array(9962260, 9962261)
9962261 => array(9962260)
9962260 => array()
Cheers
And the result you wish is, following your example, an array of array as the following one?
9962263 => array(9962260, 9962261)
9962261 => array(9962260)
9962260 => array()
Cheers
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
How is the database laid out. Is it two columns: '9962261', '9962260' (where the right is the loser). Or is it one column: '9962261 wins over 9962260'?
Either way, I would implement a WHERE clause that only pulled values on the LEFT that do not appear on the RIGHT. For one field, you can use LEFT() with an INSTR, CHARINDEX, or similar type method depending on your database platform -- what is that by the way? -- then to compare to the other side, you can use similar functions to pull the right portion or use REGEXP if MySQL.
From there, you can use a GROUP BY and database specific tricks like GROUP_CONCAT or FOR XML to generate a common-delimited list for the losers.
Either way, I would implement a WHERE clause that only pulled values on the LEFT that do not appear on the RIGHT. For one field, you can use LEFT() with an INSTR, CHARINDEX, or similar type method depending on your database platform -- what is that by the way? -- then to compare to the other side, you can use similar functions to pull the right portion or use REGEXP if MySQL.
From there, you can use a GROUP BY and database specific tricks like GROUP_CONCAT or FOR XML to generate a common-delimited list for the losers.
ASKER
Ingenious. Thanks to all who helped.
Please show us the data structure and how you programmed the solution, thanks. ~Ray
9962261 wins over 9962260
9962263 wins over 9962261
9962263 wins over 9962260
It would seem that you can take all the numbers in the right column and remove any instance of them from the left column. That will tell you the winners who are not also losers.
Not sure I understand the other part. How would you know whether 9962263 eliminated 9962260 before 9962261 eliminated 9962260. That detail would seem to have an effect on whatever you wanted to put into the list of losers.