sorting - How can I sort this "matrix" of data? -


i run sporting website, , it's useful rank people against each other based on previous meetings.

see example set of data:

on left raw "unsorted" view. on right correctly sorted (in opinion) list.

each square shows number of times they've competed against each other, , percentage of victories. they're shaded based on percentage.

i have in webpage, "up" , "down" controls alongside each row, , can manually nudge them around until want.

i'm not quite sure of best way automate this.

the numbers @ end of each row quick idea roughed out, , equal sum across row of (percentage-50 * column number). can see, job, first 2 rows being "wrong". don't give weight number of meetings though, win percentage.

the final-column numbers change depending on row order well, can seen comparing left , right tables in image, sorting on initial values wouldn't work well. looping sort + re-calc couple of times might job.

i expect can cobble make work... feel have much better ideas, , i'm ears.

a tournament graph in there 1 directed edge between every pair of vertices; create such graph input, make graph vertex each player, , "point" each edge between 2 players in direction of player won majority of games (you need break ties somehow).

if this, , if there no cycles > b > ... > of type mentioned in comment in graph, graph transitive, , can order players using topological sort of graph. takes linear time in number of edges, i.e. o(n^2) n players.

if there are such cycles, there's no "perfect" ordering of players: ordering place @ least 1 player after player have beaten. in case, reasonable alternative orderings minimise number of these "edge violations". turns out well-studied np-hard problem in computer science called (minimum) feedback arc set in tournaments (fast). feedback arc set set of directed edges ("arcs") which, if deleted graph, leave graph no directed cycles -- can turned order using topological sort before.

this paper describes recent attack on problem. haven't read paper, active area of research , algorithm quite complicated -- might give ideas how create simpler algorithm runs slower (but acceptably fast on such small instances), or how create heuristic.


Comments

Post a Comment

Popular posts from this blog

powershell Start-Process exit code -1073741502 when used with Credential from a windows service environment -

i'm running strange behavior powershell start-process call. here call: $process = start-process ` "c:\somepath\mybinary.exe" ` -passthru ` -credential $defaultcredential ` -wait ` -workingdirectory "c:\somepath" ` -loaduserprofile if ($process.exitcode -ne 0) { #do } this call return exit code - 1073741502 . after quick search, exit code seems related generic error when program not load required dll (aka. status_dll_init_failed ). when run without -credential $credential program runs correctly. in order isolate problem, manually launched some.exe in prompt target credential , runs smoothly. so problem seems come way start-process cmdlet launch process. i found potential solutions problem tried apply no luck : link , link . would have idea of what's going on here ? edit 1: run proc mon monitoring program activities when launched directly or via powershell script. problem seems occur when loading kernelbase
Read more

twig - Using Twigbridge in a Laravel 5.1 Package -

i'm trying create laravel 5.1 package uses twigbridge instead of .php views. can normal .php views display fine, when try make use of .twig templates i'm met error. possible use twigbridge templates when creating views laravel package or pretty stuck blade , php ? edit 1: loading twig template without extending works. it's when start using {% extends 'file' %} error comes out. i error error loading /virtual/laravel/packages/username/mypackage/src/views/sample.twig: template "templates.master" not defined () in "/virtual/laravel/packages/username/mypackage/src/views/sample.twig" @ line 1. my folders username |_ mypackage |_ src |_ controllers - samplecontroller.php |_ views |_ templates - master.twig - sample.twig twig template sample.twig {% extends 'templates.master' %} {% block content %} {{ parent()
Read more

c# - LINQ join Entities from HashSet's, Join vs Dictionary vs HashSet performance -

i have hashset's each stores t, have written test application compares different relation algorithms can think of, i'm not pleased results getting. does there exist more efficient ways of achieving object relations, once testing? using system; using system.collections.generic; using system.linq; using system.text; using system.threading.tasks; using system.diagnostics; namespace linqtests { class program { static void main(string[] args) { hashset<user> usertable = new hashset<user>(); hashset<userproperty> userpropertytable = new hashset<userproperty>(); #region lets create dummy data. console.writeline("please wait while creating dummy data, can take while..."); console.writeline(""); int rows = 1000000; for(int x = 0; x < rows; x++) { random rnd = new random(); // ad
Read more