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

How to connect android app to App engine -

i'm trying connect app in android server i've opened on appengine. my server's name : dddd-daniel-2345 , website server : http://dddd-daniel-2345.appspot.com/ this how connect android app server in app engine: app.yaml: application: dddd-daniel-2345 version: 1 runtime: python27 api_version: 1 threadsafe: yes handlers: - url: .* script: main.app libraries: - name: webapp2 version: "2.5.2" main.py: #!/usr/bin/env python # # copyright 2007 google inc. google.appengine.api import users import webapp2 class userhandler(webapp2.requesthandler): def get(self): user = users.get_current_user() if user: greeting = ('%s,%s,%s' % (user.email(),user.user_id(),user.nickname())) else: greeting = ('not logged in') self.response.out.write(greeting) app = webapp2.wsgiapplication([('/', userhandler),], debug=true) my applications code : add manifast main....
Read more

gcc - MinGW's ld cannot perform PE operations on non PE output file -

i know there other similar questions out there, stackoverflow or not. i've researched lot this, , still didn't find single solution. i'm doing operative system side project. i've been doing in assembly, wanna join c code. test, made assembly code file (called test.asm): [bits 32] global _a section .text _a: jmp $ then made c file (called main.c): extern void a(void); int main(void) { a(); } to link, used file (called make.bat): "c:\mingw\bin\gcc.exe" -ffreestanding -c -o c.o main.c nasm -f coff -o asm.o test.asm "c:\mingw\bin\ld.exe" -ttext 0x100000 --oformat binary -o out.bin c.o asm.o pause i've been researching ages, , i'm still struggling find answer. hope won't flagged duplicate. acknowledge existence of similar questions, have different answers, , none work me. question: what doing wrong? old mingw versions had problem "ld" not able create non-pe files @ all. maybe current versions...
Read more

php - display validation error message next to the textbox in codeigniter -

Image
i'm newbie codeigniter.i want display error message next text box.my view file create.php contains following code. <?php echo validation_errors(); //validation echo form_open('news/create'); //create form ?> <div class="boxes"> <div class="common"> <div class="lables"> <label for="name">name</label> </div> <div class="text_boxes"> <input type="text" name="uname" /><div id="infomessage"><?php echo $message;?></br> </div> </div>` and below controller model: public function create() { $this->load->helper('form'); $this->load->library('form_validation'); $data['title'] = 'insert items'; $this->form_validation->set_rules('uname','required|min_length[6]|m...
Read more