Someone (FilippeSoaresRoza) asked a question 21 June 2013 on OTN about finding the best fantasy football team in SQL, Processing Cost – How to catch a soccer team with the highest combined score?. I saw that this was another knapsack problem, of the single container type. I had solved that problem on the forum before, and here, A Simple SQL Solution for the Knapsack Problem (SKP-1), so I decided to adapt the solution for this case. This is in fact a more general form of the problem, wherein the items now have categories, with constraints on the numbers in each category, and on the overall number of items. The first solution I posted provided an exact solution, as in the above article, and performed well enough on the simple sample data, returning in a few seconds. However, the poster reported that the query was still running on his full data set after a couple of hours. I therefore decided to look for a mechanism to reduce the work done by the query on what is a hard combinatorial problem, and to return ‘good’ solutions in a practical amount of time, but without guaranteeing optimality (I recently provided solutions like this for a related problem, SQL for the Balanced Number Partitioning Problem).
This article provides the SQL that does this, and also a PL/SQL package containing a pipelined function that applies a slightly different algorithm; the latter is also practical, although it proved less efficient on my test problems.
Note that this article is a re-write of the article I published 22 June, which had the exact solution approach, and also an earlier data model, closer to the poster’s own.
Update, 12 November 2017: In response to a comment, I have added all the scripts necessary to run the SQL against the two example datasets to a new GitHub repo: Brendan’s repo for interesting SQL
Test Problems
I used two test problems.
Test Problem 1: Brazilian League
The first problem was supplied by the OTN poster and appears to be based on a Brazilian league. It has 114 players, in seven positions (one being coach), with twelve players forming a team. The problem is to find the team with maximum total player points within a given maximum price, and matching the positional constraints:
Input positions
ID MIN_PLAYERS MAX_PLAYERS
-- ----------- -----------
AL 12 12
CB 2 3
CO 1 1
FW 1 3
GK 1 1
MF 3 5
WB 0 2
6 rows selected.
Input players
ID CLUB_NAME PLAYER_NAME PO PRICE AVG_POINTS APPEARANCES PRF_R VFP_R PRC_R
--- ------------------------------ ------------------------------ -- ---------- ---------- ----------- ---------- ---------- ----------
038 Portuguesa Ivan WB 755 1320 100 1 2 20
001 Atlético-PR Éderson FW 1712 1012 500 2 22 97
002 Vitória Maxi Biancucchi FW 1962 1005 400 3 33 103
003 Fluminense Rafael Sobis FW 2303 955 400 4 47 112
098 Fluminense Digão CB 931 927 300 5 5 34
058 Internacional Fred MF 3028 892 500 6 92 114
059 Grêmio Zé Roberto MF 2593 878 400 7 73 113
039 Vasco Elsinho WB 1468 850 400 8 25 83
004 Bahia Fernandão FW 1328 822 500 9 19 70
060 Internacional Otavinho MF 762 807 300 10 4 21
078 Flamengo Jaime De AlMFda CO 1156 803 100 11 12 52
022 Vitória Wilson GK 1239 794 500 12 17 59
021 Cruzeiro Fábio GK 2090 794 500 12 59 106
023 Coritiba Vanderlei GK 1858 776 500 14 45 101
005 São Paulo Luis Fabiano FW 2154 758 400 15 67 107
040 Cruzeiro Egídio WB 1482 752 500 16 34 84
041 Fluminense Carlinhos WB 1240 693 300 17 26 60
099 Flamengo Samir CB 267 680 100 18 1 1
061 Vasco Carlos Alberto MF 1501 675 200 19 42 85
006 Botafogo Rafael Marques FW 1974 668 500 20 74 105
062 Cruzeiro Nilton MF 2239 646 500 21 95 110
100 Cruzeiro Dedé CB 2254 640 500 22 97 111
063 Coritiba Júnior Urso MF 1438 622 500 23 43 81
064 Crisciúma João Vitor MF 1327 604 500 24 41 69
101 São Paulo Lúcio CB 2171 602 500 25 99 108
007 Cruzeiro Dagoberto FW 2211 594 500 26 102 109
102 Grêmio Bressan CB 1085 590 400 27 28 48
103 Atlético-PR Manoel CB 1699 588 500 28 70 96
065 Corinthians Guilherme MF 883 587 400 29 14 32
104 Ponte Preta Cléber CB 1461 578 500 30 55 82
008 Náutico Rogério FW 1062 570 500 31 29 44
066 Corinthians Ralf MF 1965 570 500 31 93 104
067 Vitória Escudero MF 1638 568 500 33 68 93
068 Portuguesa Correa MF 844 560 400 34 15 26
042 Náutico Auremir WB 773 548 400 35 11 22
079 Cruzeiro Marcelo Oliveira CO 1611 543 500 36 75 92
080 Fluminense Abel Braga CO 1751 536 400 37 84 98
105 Cruzeiro Bruno Rodrigo CB 1547 528 500 38 72 88
043 Cruzeiro Mayke WB 374 525 200 39 3 3
069 Portuguesa Souza MF 1262 517 400 40 49 62
070 Coritiba Alex MF 1698 508 500 41 88 95
009 Flamengo Hernane FW 1387 498 500 42 65 75
071 Grêmio Souza MF 1380 498 400 42 64 74
106 Santos Edu Dracena CB 1682 497 300 44 90 94
010 Crisciúma Lins FW 1840 490 500 45 103 100
011 Santos Neilton FW 638 488 400 46 9 11
012 Fluminense Samuel FW 1001 487 300 47 36 37
072 Ponte Preta Cicinho MF 1142 472 500 48 48 51
024 Atlético-MG Victor GK 1163 467 400 49 52 53
045 Atlético-MG Richarlyson WB 1020 467 300 49 40 38
044 Portuguesa Luis Ricardo WB 858 467 300 49 27 28
013 Ponte Preta Chiquinho FW 997 464 500 52 38 36
081 Internacional Dunga CO 1422 463 500 53 79 80
047 São Paulo Juan WB 789 457 300 54 24 23
046 Internacional Fabrício WB 876 457 400 54 31 30
014 Atlético-MG Luan FW 1318 455 400 56 71 67
048 São Paulo Paulo Miranda WB 1053 454 500 57 44 41
049 Flamengo João Paulo WB 715 453 300 58 18 19
050 São Paulo Rodrigo Caio WB 1192 452 500 59 60 56
025 Bahia Marcelo Lomba GK 1364 450 500 60 78 71
073 Botafogo Fellype Gabriel MF 860 447 400 61 32 29
082 Vitória Caio Júnior CO 1140 445 500 62 56 50
015 Ponte Preta William FW 1393 444 500 63 81 76
107 Náutico William Alves CB 556 443 300 64 8 8
083 Grêmio Vanderlei Luxemburgo CO 1577 442 400 65 98 89
084 São Paulo Ney Franco CO 1515 439 500 66 94 86
074 Atlético-PR João Paulo MF 1056 438 500 67 46 42
026 Botafogo Renan GK 677 437 400 68 16 13
075 Vasco Sandro Silva MF 1076 428 500 69 53 46
108 Fluminense Gum CB 1218 422 400 70 69 58
085 Náutico Levi Gomes CO 708 420 200 71 21 18
109 Flamengo Wallace CB 429 420 200 71 6 4
051 Coritiba Victor Ferraz WB 1304 420 500 71 80 65
076 Santos Cícero MF 1415 418 500 74 91 78
027 Flamengo Felipe GK 1526 414 500 75 101 87
077 Fluminense Wagner MF 855 413 300 76 37 27
052 Bahia Jussandro WB 694 410 500 77 23 16
110 Náutico João Filipe CB 547 410 400 77 10 7
016 Botafogo Vitinho FW 1020 404 500 79 54 38
053 Santos Rafael Galhardo WB 1288 404 500 79 83 64
111 Grêmio Werley CB 1590 403 400 81 105 90
055 Náutico Maranhão WB 653 402 500 82 20 12
054 Goiás William Matheus WB 587 402 500 82 13 9
112 Corinthians Gil CB 1323 398 500 84 85 68
113 Vitória Gabriel Paulista CB 1177 394 500 85 76 54
086 Atlético-PR Ricardo Drubscky CO 796 392 500 86 35 24
087 Coritiba Marquinhos Santos CO 1059 389 500 87 62 43
017 Coritiba Deivid FW 1590 376 500 88 107 90
028 Grêmio Dida GK 1132 375 400 89 77 49
114 Goiás Ernando CB 1024 374 500 90 63 40
029 Corinthians Cássio GK 1251 374 500 90 89 61
018 Grêmio Barcos FW 1896 367 400 92 110 102
088 Vasco Paulo Autuori CO 1313 361 500 93 100 66
030 Vasco Michel Alves GK 899 348 500 94 57 33
019 Atlético-MG Jô FW 1393 340 200 95 106 76
056 Internacional Gabriel WB 1181 338 500 96 96 55
057 Goiás Vítor WB 877 336 500 97 58 31
089 Portuguesa Edson Pimenta CO 367 326 400 98 7 2
090 Botafogo Oswaldo De Oliveira CO 1077 323 500 99 87 47
031 Crisciúma Bruno GK 1066 320 500 100 86 45
092 Santos Claudinei Oliveira CO 1192 317 300 101 104 56
091 Corinthians Tite CO 1368 317 500 101 108 73
020 São Paulo Osvaldo FW 1364 312 500 103 109 71
032 Internacional Muriel GK 981 310 400 104 82 35
033 Santos Rafael GK 1782 300 500 105 112 99
093 Bahia Cristóvão Borges CO 827 292 500 106 66 25
094 Crisciúma Vadão CO 704 286 500 107 50 17
095 Goiás Enderson Moreira CO 680 253 500 108 61 14
034 Atlético-PR Weverton GK 616 248 500 109 51 10
035 Fluminense Ricardo Berna GK 460 242 400 110 30 6
096 Atlético-MG Cuca CO 1262 232 400 111 111 62
036 Portuguesa Gledson GK 452 210 400 112 39 5
037 São Paulo Rogério Ceni GK 1420 117 400 113 114 79
097 Ponte Preta Zé Sérgio CO 685 75 100 114 113 15
114 rows selected.
Note that I dropped the poster’s formations based data model in favour of the above, more general one. I used AL as a code for team size, and chose the maximum price arbitrarily (but having an influence on results). I also multiplied the points and prices by a factor of 100 to allow me to work in integers.
Test Problem 2: English Premier League
The second problem is be based on English Premier League and I got the data from a ‘scraping’ web-site, https://scraperwiki.com/scrapers/fantasy_premier_league_player_stats/. There are some data quality issues with the data, but it is good enough for technical testing. I summed the players’ points over the last season and took their values at the last week as prices.
After excluding zero-point players, there remained 576 players, of five positions, with eleven players forming a team, and the problem is the same, with the positional constraints:
Input positions
ID MIN_PLAYERS MAX_PLAYERS
-- ----------- -----------
AL 11 11
DF 3 5
FW 1 3
GK 1 1
MF 2 5
Input players
ID CLUB_NAME PLAYER_NAME PO PRICE AVG_POINTS APPEARANCES PRF_R VFP_R PRC_R
---------- --------------- -------------------- -- ---------- ---------- ----------- ---------- ---------- ----------
661 Tottenham Gareth Bale MF 111 240 38 1 36 573
286 Liverpool Luis Suarez FW 105 213 38 2 62 572
30 Arsenal Santi Santi Cazorla MF 97 198 36 3 57 569
149 Chelsea Juan Mata MF 102 190 36 4 90 571
265 Liverpool Steven Gerrard MF 92 187 38 5 60 562
533 Southampton Rickie Lambert FW 69 178 37 6 5 513
165 Everton Leighton Baines DF 78 173 38 7 25 537
318 Man City Carlos Tevez FW 92 172 38 8 87 562
139 Chelsea Eden Hazard MF 96 171 35 9 99 568
641 Swansea Miguel Michu MF 79 169 36 10 41 542
177 Everton Marouane Fellaini MF 73 168 38 11 14 527
47 Aston Villa Christian Benteke FW 74 166 35 12 20 530
204 Fulham Dimitar Berbatov FW 71 161 37 13 18 523
720 West Brom Romelu Lukaku FW 66 157 37 14 8 498
314 Man City David Silva MF 92 154 38 15 117 562
298 Man City Joe Hart GK 69 154 38 15 22 513
549 Stoke City Asmir Begovic GK 56 154 40 15 1 421
428 Norwich Robert Snodgrass MF 62 152 38 18 7 474
332 Man Utd Patrice Evra DF 73 152 38 18 51 527
126 Chelsea Demba Ba FW 78 149 37 20 77 537
616 Sunderland Stephane Sessegnon MF 67 148 38 21 26 504
575 Stoke City Jonathan Walters MF 63 147 40 22 13 482
770 West Ham Kevin Nolan MF 61 145 36 23 9 465
354 Man Utd Wayne Rooney FW 116 141 37 24 201 575
322 Man City Yaya Yaya Toure MF 82 141 37 24 108 548
268 Liverpool Glen Johnson DF 65 141 37 24 35 491
760 West Ham Jussi Jaaskelainen GK 52 139 36 27 2 361
198 Everton Steven Pienaar MF 66 139 38 27 46 498
609 Sunderland Simon Mignolet GK 53 139 38 27 3 379
598 Sunderland Adam Johnson MF 68 138 37 30 61 508
726 West Brom James Morrison MF 57 135 39 31 11 429
569 Stoke City Ryan Shawcross DF 56 133 40 32 10 421
248 Liverpool Daniel Agger DF 64 133 38 32 52 488
270 Liverpool Sanchez Jose Enrique DF 61 133 37 32 33 465
239 Fulham Mark Schwarzer GK 51 133 38 32 4 344
800 Wigan Arouna Kone FW 69 131 37 36 78 513
684 Tottenham Aaron Lennon MF 71 131 38 36 91 523
161 Chelsea Fernando Torres FW 93 131 36 36 165 566
552 Stoke City Peter Crouch FW 60 131 40 36 31 458
594 Sunderland Steven Fletcher FW 67 131 36 36 71 504
295 Man City Edin Dzeko FW 68 130 38 41 76 508
700 Tottenham Jan Vertonghen DF 68 129 37 42 80 508
132 Chelsea Petr Cech GK 64 129 38 42 64 488
144 Chelsea Frank Lampard MF 85 128 36 44 150 553
289 Man City Sergio Aguero FW 111 127 39 45 217 573
278 Liverpool Jose Reina GK 58 126 38 46 34 438
628 Swansea Jonathan De Guzman MF 57 122 36 47 39 429
667 Tottenham Jermain Defoe FW 79 122 37 47 137 542
723 West Brom Gareth McAuley DF 52 122 38 47 12 361
802 Wigan Shaun Maloney MF 54 121 37 50 21 395
405 Norwich Sebastien Bassong DF 53 121 37 50 16 379
186 Everton Phil Jagielka DF 59 120 38 52 59 449
558 Stoke City Robert Huth DF 55 120 40 52 32 409
353 Man Utd Rafael Rafael DF 61 119 38 54 72 465
771 West Ham Joey O'Brien DF 48 119 36 54 6 269
196 Everton Leon Osman MF 62 119 37 54 75 474
650 Swansea Wayne Routledge MF 53 118 36 57 24 379
323 Man City Pablo Zabaleta DF 64 117 38 58 92 488
669 Tottenham Clint Dempsey MF 89 116 37 59 186 557
612 Sunderland John O'Shea DF 51 115 38 60 19 344
374 Newcastle Papiss Cisse FW 87 115 39 60 182 556
142 Chelsea Branislav Ivanovic DF 69 114 36 62 120 513
211 Fulham Damien Duff MF 58 114 38 62 69 438
364 Man Utd David de Gea GK 58 114 38 62 69 438
185 Everton Tim Howard GK 53 113 38 65 43 379
154 Chelsea Emboaba Oscar MF 79 113 35 65 163 542
602 Sunderland Sebastian Larsson MF 59 112 38 67 79 449
719 West Brom Shane Long FW 58 110 38 68 81 438
413 Norwich Grant Holt FW 59 110 38 68 89 449
713 West Brom Ben Foster GK 51 109 39 70 42 344
536 Southampton Jason Puncheon MF 47 107 37 71 17 238
232 Fulham Sascha Riether DF 48 107 37 71 23 269
145 Chelsea David Luiz DF 67 107 36 71 132 504
784 Wigan Jean Beausejour MF 53 106 38 74 65 379
60 Aston Villa Bradley Guzan GK 48 106 38 74 27 269
293 Man City Gael Clichy DF 58 106 38 74 93 438
476 QPR Adel Taarabt MF 53 105 38 77 66 379
804 Wigan James McCarthy MF 48 105 38 77 30 269
595 Sunderland Craig Gardner MF 49 104 38 79 44 293
131 Chelsea Gary Cahill DF 60 104 38 79 106 458
423 Norwich Anthony Pilkington MF 55 104 38 79 82 409
541 Southampton Morgan Schneiderlin MF 48 103 37 82 38 269
412 Norwich Javier Garrido DF 47 103 38 82 29 238
414 Norwich Wes Hoolahan MF 55 103 38 82 86 409
134 Chelsea Ashley Cole A DF 63 103 36 82 123 482
701 Tottenham Kyle Walker DF 61 103 37 82 115 465
540 Southampton Jay Rodriguez FW 52 103 37 82 67 361
173 Everton Sylvain Distin DF 54 102 38 88 83 395
236 Fulham Bryan Ruiz FW 50 102 38 88 58 313
501 Reading Jobi McAnuff MF 47 101 36 90 37 238
776 West Ham Winston Reid DF 48 101 36 90 47 269
576 Stoke City Glenn Whelan MF 49 101 40 90 54 293
233 Fulham John Arne Riise DF 52 100 38 93 74 361
358 Man Utd Antonio Valencia MF 82 100 38 93 200 548
331 Man Utd Jonny Evans J DF 53 99 37 95 88 379
285 Liverpool Daniel Sturridge FW 74 99 35 95 178 530
187 Everton Nikica Jelavic FW 77 98 37 97 190 534
498 Reading Adam Le Fondre FW 44 97 36 98 28 156
261 Liverpool Stewart Downing MF 57 97 37 98 109 429
417 Norwich Bradley Johnson MF 47 97 38 98 53 238
420 Norwich Russell Martin R DF 42 96 38 101 15 82
648 Swansea Angel Rangel DF 47 96 36 101 56 238
769 West Ham Mark Noble MF 46 96 36 101 50 216
267 Liverpool Jordan Henderson MF 48 95 38 104 68 269
156 Chelsea Nascimento Ramires MF 62 95 35 104 140 474
635 Swansea Pablo Hernandez MF 59 95 33 104 130 449
606 Sunderland James McClean MF 56 95 39 104 111 421
372 Newcastle Yohan Cabaye MF 65 94 38 108 158 491
327 Man Utd Michael Carrick MF 59 94 38 108 133 449
631 Swansea Nathan Dyer MF 50 94 36 108 84 313
305 Man City James Milner MF 61 93 38 111 143 465
532 Southampton Adam Lallana MF 56 93 37 111 118 421
550 Stoke City Geoff Cameron DF 43 92 38 113 40 114
627 Swansea Ben Davies DF 44 92 35 113 49 156
334 Man Utd Rio Ferdinand DF 58 92 38 113 135 438
705 West Brom Chris Brunt MF 53 92 37 113 105 379
731 West Brom Jonas Olsson DF 49 92 39 113 85 293
786 Wigan Emmerson Boyce DF 47 91 38 118 73 238
338 Man Utd Javier Hernandez FW 65 90 37 119 170 491
789 Wigan Franco Di Santo FW 52 90 38 119 107 361
191 Everton Kevin Mirallas FW 66 90 36 119 173 498
658 Swansea Ashley Williams DF 49 89 36 122 94 293
657 Swansea Michel Vorm GK 51 89 37 122 104 344
686 Tottenham Hugo Lloris GK 58 89 34 122 139 438
282 Liverpool Martin Skrtel DF 56 89 38 122 134 421
761 West Ham Matthew Jarvis MF 55 89 35 122 129 409
164 Everton Victor Anichebe FW 43 88 38 127 55 114
735 West Brom Liam Ridgewell DF 48 87 38 128 97 269
754 West Ham Guy Demel DF 41 87 36 128 45 60
433 Norwich Michael Turner DF 41 86 38 130 48 60
747 West Ham Andy Carroll FW 82 86 36 130 237 548
547 Stoke City Charlie Adam MF 65 85 38 132 184 491
291 Man City Gareth Barry MF 52 85 38 132 124 361
537 Southampton Gaston Ramirez MF 52 85 34 132 124 361
302 Man City Vincent Kompany DF 70 85 38 132 202 521
383 Newcastle Jonas Gutierrez MF 55 84 39 136 142 409
341 Man Utd Shinji Kagawa MF 79 84 37 136 235 542
306 Man City Samir Nasri MF 81 83 37 138 243 546
125 Chelsea Cesar Azpilicueta DF 56 83 34 138 154 421
519 Southampton Nathaniel Clyne DF 41 83 37 138 63 60
78 Aston Villa Ashley Westwood MF 49 83 35 138 112 293
445 QPR Soares Cesar GK 47 83 35 138 100 238
241 Fulham Steve Sidwell MF 49 83 38 138 112 293
755 West Ham Mohamed Diame MF 47 83 36 138 100 238
564 Stoke City Steven Nzonzi MF 50 81 35 145 128 313
284 Liverpool Raheem Sterling MF 46 81 37 145 102 216
359 Man Utd Robin Van Persie FW 137 80 12 147 330 576
727 West Brom Youssouf Mulumbu MF 53 80 39 147 149 379
77 Aston Villa Andreas Weimann FW 51 80 31 147 136 344
782 Wigan Ali Al-Habsi GK 49 80 38 147 126 293
597 Sunderland Danny Graham FW 54 79 38 151 156 395
803 Wigan James McArthur MF 54 78 38 152 159 395
224 Fulham Alex Kacaniklic MF 43 78 38 152 95 114
591 Sunderland Carlos Cuellar DF 43 78 37 152 95 114
303 Man City Joleon Lescott DF 58 77 38 155 179 438
668 Tottenham Mousa Dembele MF 58 77 37 155 179 438
696 Tottenham Gylfi Sigurdsson MF 78 76 37 157 260 537
511 Reading Hal Robson-Kanu MF 42 76 36 157 98 82
307 Man City Matija Nastasic DF 53 76 34 157 161 379
386 Newcastle Tim Krul GK 51 75 38 160 155 344
522 Southampton Steven Davis MF 45 74 37 161 122 183
730 West Brom Peter Odemwingie FW 69 74 39 161 233 513
503 Reading Garath McCleary MF 44 73 36 163 119 156
221 Fulham Brede Hangeland DF 48 73 38 163 146 269
589 Sunderland Jack Colback MF 45 73 38 163 127 183
370 Newcastle Hatem Ben Arfa MF 73 72 38 166 252 527
392 Newcastle Davide Santon DF 47 72 39 166 141 238
415 Norwich Jonathan Howson MF 45 72 39 166 131 183
496 Reading Jimmy Kebe MF 41 72 36 166 103 60
659 Tottenham Emmanuel Adebayor FW 91 71 37 170 297 560
235 Fulham Hugo Rodallega FW 54 71 37 170 183 395
172 Everton Seamus Coleman MF 46 71 38 170 138 216
792 Wigan Maynor Figueroa DF 43 71 38 170 121 114
509 Reading Pavel Pogrebnyak FW 42 71 36 170 114 82
560 Stoke City Kenwyne Jones FW 50 70 40 175 166 313
194 Everton Steven Naismith FW 59 70 37 175 207 449
328 Man Utd Tom Cleverley MF 56 70 37 175 194 421
469 QPR Ryan Nelsen DF 41 69 38 178 116 60
259 Liverpool Phillippe Coutinho MF 71 69 13 178 261 523
481 QPR Bobby Zamora FW 61 68 39 180 226 465
546 Southampton Maya Yoshida DF 45 68 34 180 148 183
524 Southampton Jose Fonte DF 40 68 37 180 110 34
425 Norwich John Ruddy GK 44 67 38 183 145 156
360 Man Utd Nemanja Vidic DF 66 67 38 183 245 498
781 West Ham Ricardo Vaz Te FW 51 66 36 185 188 344
663 Tottenham Steven Caulker DF 44 66 37 185 151 156
337 Man Utd Ryan Giggs MF 60 65 38 187 232 458
13 Arsenal Olivier Giroud FW 77 65 18 187 281 534
255 Liverpool Jamie Carragher DF 50 65 38 187 187 313
467 QPR Stephane Mbia DF 49 65 35 187 181 293
499 Reading Mikele Leigertwood MF 45 65 36 187 159 183
462 QPR Clint Hill DF 43 64 38 192 153 114
520 Southampton Jack Cork MF 44 64 37 192 157 156
666 Tottenham Michael Dawson DF 45 64 38 192 164 183
624 Swansea Leon Britton MF 42 64 36 192 144 82
715 West Brom Zoltan Gera MF 47 64 39 192 175 238
561 Stoke City Michael Kightly MF 51 64 38 192 193 344
625 Swansea Chico DF 46 64 36 192 169 216
718 West Brom Billy Jones DF 44 63 38 199 162 156
387 Newcastle Sylvain Marveaux MF 41 62 38 200 147 60
463 QPR David Hoilett MF 56 62 38 200 229 421
556 Stoke City Matthew Etherington MF 59 61 40 202 241 449
230 Fulham Mladen Petric FW 54 61 37 202 221 395
478 QPR Armand Traore DF 48 61 38 202 191 269
636 Swansea Sung-Yeung Ki MF 60 60 34 205 246 458
544 Southampton Luke Shaw DF 40 60 37 205 151 34
779 West Ham Matthew Taylor MF 46 60 36 205 185 216
614 Sunderland Danny Rose MF 44 60 38 205 173 156
407 Norwich Mark Bunn GK 43 60 34 205 167 114
160 Chelsea John Terry DF 65 59 36 210 269 491
796 Wigan Jordi Gomez MF 52 59 38 210 220 361
488 Reading Adam Federici GK 43 59 36 210 172 114
363 Man Utd Ashley Young MF 82 58 37 213 307 548
431 Norwich Alexander Tettey MF 43 58 36 213 176 114
710 West Brom Graham Dorrans MF 50 58 39 213 213 313
695 Tottenham Raniere Sandro MF 47 58 38 213 198 238
75 Aston Villa Ron Vlaar DF 45 58 38 213 189 183
361 Man Utd Danny Welbeck FW 78 56 37 218 304 537
466 QPR Jamie Mackie FW 50 56 38 218 223 313
744 West Brom Claudio Yacob MF 49 56 37 218 218 293
516 Southampton Artur Boruc GK 45 56 30 218 196 183
297 Man City Francisco Garcia MF 50 56 34 218 223 313
559 Stoke City Cameron Jerome FW 50 55 38 223 231 313
787 Wigan Gary Caldwell DF 47 55 38 223 211 238
301 Man City Aleksandar Kolarov DF 55 55 38 223 246 409
500 Reading Adrian Mariappa DF 39 54 36 226 170 19
41 Aston Villa Gabriel Agbonlahor FW 68 54 21 226 295 508
38 Arsenal Theo Walcott MF 90 53 12 228 329 559
474 QPR Loic Remy FW 54 53 16 228 253 395
394 Newcastle Moussa Sissoko MF 54 53 15 228 253 395
274 Liverpool Leiva Lucas MF 46 53 38 228 216 216
506 Reading Sean Morrison DF 38 53 29 228 168 4
495 Reading Jem Karacan MF 42 53 36 228 192 82
153 Chelsea Victor Moses MF 62 53 35 228 277 474
249 Liverpool Joe Allen MF 45 52 37 235 214 183
406 Norwich Elliott Bennett MF 47 52 40 235 230 238
375 Newcastle Fabricio Coloccini DF 49 51 38 237 240 293
656 Swansea Gerhard Tremmel GK 41 51 38 237 197 60
470 QPR Nedum Onuoha DF 38 51 39 237 177 4
12 Arsenal Kieran Gibbs DF 53 51 15 237 262 379
26 Arsenal Lukas Podolski FW 81 50 12 241 322 546
674 Tottenham William Gallas DF 50 50 38 241 246 313
23 Arsenal Nacho Monreal DF 52 50 13 241 263 361
750 West Ham Carlton Cole FW 44 50 36 241 219 156
222 Fulham Aaron Hughes DF 40 50 38 241 194 34
772 West Ham Gary O'Neil MF 43 50 36 241 212 114
382 Newcastle Yoan Gouffran FW 62 50 15 241 290 474
477 QPR Andros Townsend MF 44 49 38 248 227 156
369 Newcastle Vurnon Anita MF 44 49 38 248 227 156
446 QPR Djibril Cisse FW 58 49 39 248 280 438
182 Everton Johnny Heitinga DF 50 49 38 248 255 313
225 Fulham Giorgos Karagounis MF 47 49 34 248 239 238
356 Man Utd Chris Smalling DF 45 48 38 253 234 183
570 Stoke City Ryan Shotton MF 46 48 38 253 238 216
319 Man City Kolo Toure DF 51 48 39 253 267 344
492 Reading Danny Guthrie MF 41 48 36 253 210 60
578 Stoke City Andy Wilkinson DF 40 48 40 253 204 34
502 Reading Alex McCarthy GK 40 48 36 253 204 34
690 Tottenham Kyle Naughton DF 39 48 37 253 199 19
810 Wigan Ivan Ramis DF 42 47 37 260 225 82
457 QPR Esteban Granero MF 52 47 36 260 270 361
180 Everton Darron Gibson MF 47 47 38 260 246 238
393 Newcastle Danny Simpson DF 46 46 38 263 246 216
440 QPR Jose Bosingwa DF 48 46 38 263 264 269
780 West Ham James Tomkins DF 41 46 36 263 222 60
579 Stoke City Marc Wilson DF 39 46 38 263 209 19
491 Reading Chris Gunter DF 38 46 36 263 203 4
240 Fulham Philippe Senderos DF 47 45 38 268 265 238
202 Fulham Chris Baird DF 39 45 38 268 215 19
288 Liverpool Andre Wisdom DF 38 45 32 268 208 4
207 Fulham Ashkan Dejagah MF 55 45 34 268 288 409
152 Chelsea Mikel MF 43 44 36 272 244 114
398 Newcastle Steven Taylor S DF 46 44 38 272 266 216
493 Reading Ian Harte DF 37 44 36 272 206 1
471 QPR Ji-Sung Park MF 52 44 38 272 279 361
479 QPR Shaun Wright-Phillip MF 48 44 39 272 268 269
s
691 Tottenham Scott Parker MF 52 43 37 277 285 361
11 Arsenal Yao Gervinho MF 68 42 12 278 321 508
577 Stoke City Dean Whitehead MF 42 42 40 278 246 82
453 QPR Fabio Fabio DF 40 42 38 278 236 34
2 Arsenal Mikel Arteta MF 75 41 13 281 339 533
325 Man Utd Oliveira Anderson MF 51 41 38 281 292 344
712 West Brom Marc-Antoine Fortune FW 48 41 38 281 278 269
752 West Ham James Collins DF 46 41 14 281 274 216
195 Everton Phil Neville MF 41 40 38 285 256 60
660 Tottenham Benoit Assou-Ekotto DF 60 40 38 285 313 458
21 Arsenal Per Mertesacker DF 53 39 13 287 303 379
513 Reading Nicky Shorey DF 38 39 36 287 242 4
16 Arsenal Carl Jenkinson DF 40 39 13 287 257 34
531 Southampton Jos Hooiveld DF 40 39 37 287 257 34
436 Norwich Steven Whittaker DF 40 39 38 287 257 34
643 Swansea Luke Moore FW 43 38 36 292 275 114
399 Newcastle Cheick Tiote MF 48 38 38 292 296 269
326 Man Utd Alexander Buttner DF 50 37 36 294 302 313
458 QPR Rob Green GK 41 37 38 294 271 60
494 Reading Noel Hunt FW 46 37 36 294 291 216
678 Tottenham Tom Huddlestone MF 45 37 37 294 287 183
389 Newcastle James Perch DF 44 37 38 294 283 156
655 Swansea Dwight Tiendalli DF 45 36 32 299 293 183
69 Aston Villa Matthew Lowton DF 45 36 12 299 293 183
37 Arsenal Thomas Vermaelen DF 67 36 12 299 343 504
128 Chelsea Ryan Bertrand DF 39 35 36 302 272 19
751 West Ham Joe Cole MF 51 35 37 302 310 344
805 Wigan Callum McManaman FW 45 35 38 302 298 183
401 Newcastle Mike Williamson DF 40 35 38 302 276 34
508 Reading Alex Pearce DF 38 34 36 306 273 4
350 Man Utd Luis Nani MF 82 34 38 306 369 548
368 Newcastle Shola Ameobi FW 51 34 38 306 313 344
610 Sunderland Alfred N'Diaye MF 42 34 17 306 289 82
584 Sunderland Titus Bramble DF 40 33 38 310 286 34
311 Man City Micah Richards DF 57 33 38 310 332 429
618 Sunderland David Vaughan MF 49 33 38 310 312 293
766 West Ham George McCartney DF 38 32 36 313 282 4
528 Southampton Guly Guilherme MF 47 32 37 313 311 238
753 West Ham Jack Collison MF 46 32 36 313 309 216
464 QPR Jermaine Jenas MF 42 32 38 313 300 82
489 Reading Kaspars Gorkss DF 37 31 36 317 284 1
521 Southampton Kelvin Davis GK 41 31 37 317 301 60
19 Arsenal Vito Mannone GK 40 31 36 317 299 34
448 QPR Shaun Derry MF 42 30 38 320 306 82
764 West Ham Modibo Maiga FW 50 30 36 320 324 313
818 Wigan Ben Watson MF 50 30 38 320 324 313
402 Newcastle Mapou Yanga-Mbiwa DF 49 29 15 323 328 293
737 West Brom Markus Rosenberg FW 59 29 37 323 357 449
355 Man Utd Paul Scholes MF 50 29 38 323 331 313
426 Norwich Ryan Ryan Bennett DF 39 28 38 326 304 19
526 Southampton Daniel Fox DF 40 28 37 326 308 34
51 Aston Villa Ciaran Clark DF 44 28 12 326 318 156
290 Man City Mario Balotelli FW 86 28 38 326 389 554
454 QPR Alejandro Faurlin MF 47 28 38 326 326 238
304 Man City Sisenando Maicon DF 62 28 34 326 363 474
45 Aston Villa Joe Bennett DF 44 28 36 326 318 156
791 Wigan Roger Espinoza MF 41 27 16 333 315 60
44 Aston Villa Barry Bannan MF 47 27 12 333 333 238
651 Swansea Itay Shechter FW 50 27 35 333 342 313
46 Aston Villa Darren Bent FW 78 27 18 333 384 537
280 Liverpool Nuri Sahin MF 54 27 35 333 352 395
27 Arsenal Aaron Ramsey MF 54 27 12 333 352 395
231 Fulham Kieran Richardson MF 53 27 36 333 351 379
527 Southampton Paulo Gazzaniga GK 40 26 37 340 316 34
497 Reading Stephen Kelly DF 40 26 38 340 316 34
783 Wigan Antolin Alcaraz DF 42 26 38 340 320 82
340 Man Utd Phil Jones DF 57 26 38 340 362 429
421 Norwich Steve Morison FW 49 26 38 340 345 293
346 Man Utd Anders Lindegaard GK 51 26 38 340 350 344
312 Man City Jack Rodwell MF 46 26 37 340 336 216
388 Newcastle Gabriel Obertan MF 41 25 39 347 323 60
728 West Brom Boaz Myhill GK 44 25 39 347 334 156
582 Sunderland Phil Bardsley DF 44 25 37 347 334 156
56 Aston Villa Karim El Ahmadi MF 42 25 16 347 327 82
798 Wigan David Jones MF 43 24 39 351 337 114
514 Reading Jay Tabb MF 43 24 36 351 337 114
269 Liverpool Brad Jones GK 44 24 37 351 340 156
62 Aston Villa Brett Holman MF 55 24 12 351 364 409
482 Reading Hope Akpan MF 45 24 17 351 344 183
376 Newcastle Mathieu Debuchy DF 47 24 17 351 348 238
416 Norwich Simeon Jackson FW 47 24 38 351 348 238
449 QPR Samba Diakite MF 44 24 39 351 340 156
672 Tottenham Brad Friedel GK 48 23 37 359 360 269
642 Swansea Garry Monk DF 42 22 36 360 346 82
5 Arsenal Alex Chamberlain MF 69 22 13 360 391 513
621 Swansea Kemy Agustien MF 45 22 36 360 358 183
545 Southampton James Ward-Prowse MF 43 22 37 360 347 114
371 Newcastle Gael Bigirimana MF 43 21 38 364 359 114
281 Liverpool Jonjo Shelvey MF 51 21 39 364 371 344
212 Fulham Urby Emanuelson MF 46 21 13 364 361 216
377 Newcastle Rob Elliot GK 40 20 38 367 352 34
734 West Brom Steven Reid MF 47 20 39 367 367 238
812 Wigan Joel Robles GK 40 20 15 367 352 34
815 Wigan Ronnie Stam DF 38 19 38 370 352 4
17 Arsenal Laurent Koscielny DF 53 19 12 370 382 379
64 Aston Villa Stephen Ireland MF 50 19 12 370 377 313
733 West Brom Goran Popov DF 44 19 34 370 366 156
510 Reading Jason Roberts FW 45 18 36 374 372 183
263 Liverpool Fernandez Saez FW 47 18 33 374 375 238
254 Liverpool Fabio Borini FW 72 18 37 374 409 526
315 Man City Scott Sinclair MF 60 18 37 374 392 458
197 Everton Bryan Oviedo MF 48 18 34 374 379 269
455 QPR Anton Ferdinand DF 41 17 39 379 369 60
67 Aston Villa Eric Lichaj DF 43 17 12 379 373 114
588 Sunderland Lee Cattermole MF 43 17 38 379 373 114
654 Swansea Neil Taylor DF 45 17 36 379 378 183
677 Tottenham Lewis Holtby MF 63 17 14 379 401 482
586 Sunderland Fraizer Campbell FW 49 17 37 379 383 293
742 West Brom Jerome Thomas MF 51 17 39 379 386 344
7 Arsenal Vassiriki Diaby MF 61 17 12 379 398 465
127 Chelsea Yossi Benayoun MF 61 17 36 379 398 465
29 Arsenal Bacary Sagna DF 47 17 15 379 381 238
404 Norwich Leon Barnett DF 37 16 38 389 365 1
210 Fulham Mahamadou Diarra MF 47 16 37 389 385 238
74 Aston Villa Yacouba Sylla MF 42 16 14 389 376 82
599 Sunderland Matthew Kilgallon DF 38 16 37 389 368 4
685 Tottenham Jake Livermore MF 41 15 39 393 380 60
209 Fulham Clint Dempsey MF 92 15 1 393 436 562
385 Newcastle Steve Harper GK 45 15 38 393 386 183
228 Fulham Stanislav Manolev DF 42 14 13 396 386 82
378 Newcastle Shane Ferguson MF 43 14 38 396 389 114
183 Everton Tony Hibbert DF 50 14 38 396 396 313
535 Southampton Emmanuel Mayuka FW 48 14 35 396 394 269
441 QPR Jay Bothroyd FW 47 14 40 396 393 238
48 Aston Villa Jordan Bowery FW 45 13 36 401 395 183
330 Man Utd Jonathan Evans J DF 48 13 1 401 400 269
620 Sunderland Connor Wickham FW 50 13 37 401 405 313
213 Fulham Eyong Enoh MF 50 13 13 401 405 313
31 Arsenal Clarindo Santos DF 49 13 14 401 403 293
192 Everton Jan Mucha GK 43 12 38 406 397 114
217 Fulham Emmanuel Frimpong MF 45 12 15 406 402 183
103 Bolton Mark Davies M MF 48 12 2 406 409 269
148 Chelsea Marko Marin MF 66 12 35 406 429 498
184 Everton Thomas Hitzlsperger MF 50 12 30 406 412 313
335 Man Utd Darren Fletcher MF 54 12 38 406 416 395
565 Stoke City Michael Owen FW 50 12 35 406 412 313
740 West Brom Gabriel Tamas DF 42 11 39 413 404 82
391 Newcastle Sammy Sammy Ameobi FW 43 11 39 413 408 114
72 Aston Villa Charles N'Zogbia MF 66 11 13 413 434 498
114 Bolton Martin Petrov MF 52 11 2 413 419 361
88 Blackburn David Hoilett FW 55 11 3 413 423 409
475 QPR Tommy Smith FW 45 11 40 413 411 183
43 Aston Villa Nathan Baker DF 39 10 12 419 407 19
662 Tottenham Tom Carroll MF 42 10 37 419 414 82
39 Arsenal Jack Wilshere MF 63 10 12 419 441 482
35 Arsenal Wojciech Szczesny GK 53 10 12 419 427 379
85 Blackburn Morten Gamst Gamst P MF 62 10 2 419 439 474
edersen
615 Sunderland Louis Saha FW 49 10 37 419 422 293
205 Fulham Matthew Briggs DF 39 9 38 425 415 19
158 Chelsea Oriol Romeu MF 41 9 37 425 417 60
574 Stoke City Matthew Upson DF 41 9 39 425 417 60
216 Fulham Kerim Frei MF 43 9 37 425 420 114
613 Sunderland Kieran Richardson MF 58 9 1 425 444 438
585 Sunderland Wes Brown DF 46 9 38 425 424 216
201 Everton Apostolos Vellios FW 47 9 38 425 425 238
223 Fulham Andrew Johnson A FW 47 9 1 425 425 238
257 Liverpool Sebastian Coates DF 44 9 39 425 421 156
450 QPR Kieron Dyer MF 44 8 39 434 429 156
785 Wigan Mauro Boselli FW 50 8 37 434 440 313
54 Aston Villa Fabian Delph MF 46 8 12 434 432 216
486 Reading Shaun Cummings DF 38 7 36 437 428 4
273 Liverpool Dirk Kuyt MF 94 7 1 437 478 567
166 Everton Ross Barkley MF 41 7 39 437 433 60
797 Wigan Angelo Henriquez FW 42 7 16 437 434 82
743 West Brom George Thorne MF 43 7 39 437 437 114
430 Norwich Andrew Surman MF 43 7 38 437 437 114
580 Stoke City Jonathan Woodgate DF 45 7 2 437 442 183
352 Man Utd Nick Powell MF 45 7 37 437 442 183
465 QPR Andrew Johnson FW 46 7 38 437 446 216
6 Arsenal Francis Coquelin MF 47 7 13 437 448 238
82 Blackburn Scott Dann DF 47 7 1 437 448 238
272 Liverpool Martin Kelly DF 51 7 38 437 452 344
42 Aston Villa Marc Albrighton MF 52 7 12 437 453 361
109 Bolton Ivan Klasnic FW 59 7 2 437 456 449
515 Reading Stuart Taylor GK 40 7 35 437 431 34
162 Chelsea Ross Turnbull GK 39 6 36 452 445 19
409 Norwich Lee Camp GK 40 6 15 452 447 34
310 Man City Karim Rekik DF 43 6 38 452 450 114
1 Arsenal Andrey Arshavin MF 65 6 12 452 470 491
637 Swansea Roland Lamah MF 50 6 14 452 455 313
229 Fulham Danny Murphy MF 61 6 1 452 464 465
9 Arsenal Lukasz Fabianski GK 43 6 12 452 450 114
539 Southampton Frazer Richardson DF 41 5 37 459 454 60
680 Tottenham Harry Kane FW 43 5 38 459 457 114
151 Chelsea Raul Meireles MF 63 5 36 459 474 482
84 Blackburn Mauro Formica MF 49 5 2 459 462 293
244 Fulham David Stockdale GK 43 5 38 459 457 114
709 West Brom Craig Dawson DF 38 4 39 464 459 4
439 QPR Tal Ben Haim DF 39 4 17 464 460 19
801 Wigan Adrian Lopez DF 39 4 38 464 460 19
777 West Ham Jordan Spence DF 40 4 29 464 463 34
566 Stoke City Wilson Palacios MF 41 4 39 464 465 60
52 Aston Villa Simon Dawkins MF 42 4 14 464 466 82
699 Tottenham Rafael Van der Vaart MF 89 4 37 464 509 557
717 West Brom Gonzalo Jara DF 43 4 39 464 468 114
61 Aston Villa Chris Herd MF 43 4 12 464 468 114
294 Man City Nigel De Jong MF 44 4 38 464 471 156
58 Aston Villa Shay Given GK 45 4 12 464 472 183
107 Bolton Jussi Jaaskelainen GK 48 4 2 464 473 269
251 Liverpool Oussama Assaidi MF 57 4 36 464 483 429
110 Bolton Zat Knight DF 42 4 2 464 466 82
538 Southampton Ben Reeves DF 38 3 37 478 475 4
567 Stoke City Jermaine Pennant MF 50 3 38 478 491 313
122 Chelsea Nathan Ake DF 40 3 20 478 477 34
384 Newcastle Massadio Haidara DF 41 3 15 478 479 60
608 Sunderland David Meyler MF 42 3 38 478 480 82
140 Chelsea Henrique Hilario GK 42 3 38 478 480 82
518 Southampton Richard Chaplow MF 42 3 37 478 480 82
309 Man City Abdul Razak MF 43 3 39 478 484 114
806 Wigan Ryo Miyaichi MF 43 3 12 478 484 114
774 West Ham Emanuel Pogatetz DF 43 3 14 478 484 114
373 Newcastle Adam Campbell FW 45 3 20 478 487 183
756 West Ham Alou Diarra MF 45 3 36 478 487 183
381 Newcastle Dan Gosling MF 46 3 38 478 489 216
181 Everton Magaye Gueye FW 46 3 38 478 489 216
568 Stoke City Danny Pugh MF 50 3 2 478 491 313
607 Sunderland James McFadden FW 50 3 28 478 491 313
487 Reading Daniel Daniel Carric DF 38 3 17 478 475 4
o
653 Swansea Alan Tate DF 38 2 36 495 494 4
321 Man City Gnegneri Yaya Toure MF 77 2 1 495 530 534
459 QPR Michael Harriman DF 39 2 38 495 496 19
795 Wigan Roman Golobart DF 40 2 24 495 497 34
605 Sunderland Kader Mangane DF 40 2 16 495 497 34
400 Newcastle Haris Vuckic MF 42 2 40 495 499 82
119 Bolton Gretar Rafn Steinsso DF 42 2 2 495 499 82
n
155 Chelsea Lucas Piazon MF 42 2 35 495 499 82
226 Fulham Pajtim Kasami MF 42 2 38 495 499 82
523 Southampton Steve De Ridder MF 42 2 37 495 499 82
411 Norwich David Fox MF 43 2 38 495 504 114
118 Bolton Paul Robinson DF 43 2 2 495 504 114
116 Bolton Nigel Reo-Coker MF 44 2 1 495 506 156
833 Wolves Karl Henry MF 44 2 1 495 506 156
113 Bolton Fabrice Muamba MF 44 2 1 495 506 156
707 West Brom Simon Cox FW 45 2 38 495 510 183
390 Newcastle Nile Ranger MF 45 2 26 495 510 183
832 Wolves Wayne Hennessey GK 46 2 1 495 512 216
593 Sunderland Ahmed Elmohamady MF 49 2 38 495 513 293
543 Southampton Billy Sharp FW 49 2 37 495 513 293
634 Swansea Danny Graham FW 50 2 1 495 515 313
679 Tottenham Younes Kaboul DF 50 2 38 495 515 313
91 Blackburn Marcus Marcus Olsson MF 50 2 1 495 515 313
738 West Brom Paul Scharner MF 51 2 2 495 518 344
115 Bolton Darren Pratley MF 52 2 2 495 519 361
208 Fulham Moussa Dembele FW 52 2 1 495 519 361
95 Blackburn Jason Roberts FW 53 2 3 495 521 379
283 Liverpool Jay Spearing MF 54 2 38 495 522 395
175 Everton Royston Drenthe MF 54 2 1 495 522 395
102 Bolton Kevin Davies K FW 57 2 2 495 524 429
835 Wolves Matthew Jarvis MF 57 2 1 495 524 429
682 Tottenham Niko Kranjcar MF 60 2 1 495 526 458
83 Blackburn David Dunn MF 62 2 3 495 527 474
157 Chelsea Ramires MF 69 2 1 495 528 513
694 Tottenham Louis Saha FW 69 2 1 495 528 513
775 West Ham Daniel Potts DF 38 2 36 495 494 4
396 Newcastle James Tavernier DF 39 1 38 531 531 19
136 Chelsea Didier Drogba FW 101 1 1 531 576 570
73 Aston Villa Enda Stevens DF 39 1 12 531 531 19
138 Chelsea Paulo Ferreira DF 40 1 36 531 534 34
242 Fulham Alex Smith DF 40 1 34 531 534 34
227 Fulham Stephen Kelly DF 40 1 1 531 534 34
333 Man Utd Fabio Fabio DF 42 1 1 531 537 82
793 Wigan Fraser Fyvie MF 42 1 37 531 537 82
176 Everton Shane Duffy DF 42 1 38 531 537 82
57 Aston Villa Gary Gardner MF 42 1 13 531 537 82
14 Arsenal Serge Gnabry MF 43 1 29 531 541 114
443 QPR DJ Campbell FW 43 1 40 531 541 114
555 Stoke City Maurice Edu MF 43 1 36 531 541 114
848 Wolves Stephen Ward DF 43 1 1 531 541 114
820 Wolves Christophe Berra DF 43 1 1 531 541 114
846 Wolves Richard Stearman DF 43 1 1 531 541 114
758 West Ham Robert Hall FW 43 1 34 531 541 114
512 Reading Dominic Samuel FW 44 1 23 531 548 156
419 Norwich Chris Martin C FW 44 1 38 531 548 156
814 Wigan Conor Sammon FW 45 1 38 531 550 183
633 Swansea Mark Gower MF 45 1 36 531 550 183
553 Stoke City Rory Delap MF 45 1 40 531 550 183
837 Wolves Eggert Jonsson MF 45 1 1 531 550 183
206 Fulham Simon Davies MF 46 1 38 531 554 216
670 Tottenham Yago Falque MF 46 1 37 531 554 216
96 Blackburn Ruben Rochina FW 47 1 3 531 556 238
790 Wigan Mohamed Diame MF 48 1 1 531 557 269
397 Newcastle Ryan Taylor R DF 48 1 38 531 557 269
583 Sunderland Phillip Bardsley DF 48 1 1 531 557 269
741 West Brom Somen Tchoyi MF 48 1 2 531 557 269
825 Wolves David Edwards MF 49 1 1 531 561 293
53 Aston Villa Nathan Delfouneso FW 50 1 21 531 562 313
841 Wolves Nenad Milijas MF 52 1 1 531 563 361
827 Wolves Steven Fletcher FW 52 1 1 531 563 361
839 Wolves Michael Kightly MF 54 1 1 531 565 395
130 Chelsea Jose Bosingwa DF 55 1 1 531 566 409
86 Blackburn David Goodwillie FW 55 1 2 531 566 409
342 Man Utd Will Keane FW 55 1 2 531 566 409
823 Wolves Kevin Doyle FW 57 1 1 531 569 429
137 Chelsea Michael Essien MF 63 1 36 531 570 482
171 Everton Tim Cahill MF 65 1 38 531 571 491
692 Tottenham Roman Pavlyuchenko FW 70 1 1 531 572 521
146 Chelsea Romelu Lukaku FW 74 1 3 531 573 530
247 Liverpool Charlie Adam MF 86 1 1 531 574 554
256 Liverpool Andy Carroll FW 91 1 1 531 575 560
98 Bolton Marcos Alonso DF 39 1 1 531 531 19
576 rows selected.
SQL Solution with Recursive Subquery Factoring
SQL
Note that currently I have retained the fantasy league table and column names, but they could as well be the generic items and categories in place of players and teams: This is a generic solution.
VAR KEEP_NUM NUMBER
VAR MAX_PRICE NUMBER
BEGIN
:KEEP_NUM := 40;
:MAX_PRICE := 900;
END;
/
PROMPT Top ten solutions
WITH position_counts AS (
SELECT Max (CASE id WHEN 'AL' THEN min_players END) team_size
FROM positions
), pos_runs AS (
SELECT id, Sum (CASE WHEN id != 'AL' THEN min_players END) OVER (ORDER BY id DESC) num_remain, min_players, max_players
FROM positions
), players_ranked AS (
SELECT id,
position_id,
price,
avg_points,
appearances,
Row_Number() OVER (ORDER BY position_id, avg_points DESC) rnk,
Min (price) OVER () min_price
FROM players
), rsf (path_rnk, nxt_id, lev, tot_price, tot_profit, pos_id, n_pos, team_size, min_players, pos_path, path) AS (
SELECT 0, 0, 0, 0, 0, 'AL', 0, c.team_size, 0, CAST (NULL AS VARCHAR2(400)) pos_path, CAST (NULL AS VARCHAR2(400)) path
FROM position_counts c
UNION ALL
SELECT Row_Number() OVER (PARTITION BY r.pos_path || p.position_id ORDER BY r.tot_profit + p.avg_points DESC),
p.rnk,
r.lev + 1,
r.tot_price + p.price,
r.tot_profit + p.avg_points,
p.position_id,
CASE p.position_id WHEN r.pos_id THEN r.n_pos + 1 ELSE 1 END,
r.team_size,
m1.min_players,
r.pos_path || p.position_id,
r.path || LPad (p.id, 3, '0')
FROM rsf r
JOIN players_ranked p
ON p.rnk > r.nxt_id
JOIN pos_runs m1
ON m1.id = p.position_id
AND CASE p.position_id WHEN r.pos_id THEN r.n_pos + 1 ELSE 1 END <= m1.max_players
AND r.team_size - r.lev - 1 >= m1.num_remain - CASE p.position_id WHEN r.pos_id THEN r.n_pos + 1 ELSE 1 END
AND (r.lev = 0 OR p.position_id = r.pos_id OR r.n_pos >= r.min_players)
WHERE r.tot_price + p.price + (r.team_size - r.lev - 1) * p.min_price <= :MAX_PRICE
AND r.path_rnk < :KEEP_NUM
AND r.lev < r.team_size
), paths_ranked AS (
SELECT tot_price,
tot_profit,
team_size,
Row_Number () OVER (ORDER BY tot_profit DESC, tot_price) r_profit,
path
FROM rsf
WHERE lev = team_size
), top_ten_paths AS (
SELECT tot_price,
tot_profit,
r_profit,
path,
player_index
FROM paths_ranked
CROSS JOIN (SELECT LEVEL player_index FROM position_counts CONNECT BY LEVEL <= team_size)
WHERE r_profit <= 10
), top_ten_teams AS (
SELECT tot_price,
tot_profit,
r_profit,
path,
player_index,
Substr (path, (player_index - 1) * 3 + 1, 3) player_id
FROM top_ten_paths
)
SELECT t.tot_profit,
t.tot_price,
t.r_profit rnk,
p.position_id,
t.player_id p_id,
p.player_name,
p.club_name,
p.price,
p.avg_points
FROM top_ten_teams t
JOIN players p
ON p.id = t.player_id
ORDER BY t.tot_profit DESC, t.tot_price, t.path, p.position_id, t.player_index
How It Works
The solution approach is based on the method used to provide exact solutions for knapsack problems in my earlier article, but with a number of extensions to cater for the new category constraints, and to reduce searching to manageable proportions.
- position_counts subquery: Gets the team size
- pos_runs subquery: Computes the running sums of the item category minima going backwards by category id
- players_ranked subquery: Computes a unique rank for the items, ordered by category, then profit descending
- rsf subquery: A recursive subquery that returns a set of item sets in the form of strings of the concatenated item ids
- rsf anchor branch: Initialises the recursion with a single record
- rsf recursive branch: Items are joined having strictly higher rank, and such that the constraints are not violated, both at the current position and with any possible extrapolations
- Row_Number is used to rank the records by overall profit, and the where clause excludes records from the previous iteration that have rank below an input figure;
this exclusion is what makes the computation practical; the ranking is partitioned by the category path, which is important to avoid closing off solution paths too early
- Item category minima are treated differently from the maxima; once a category is in a position, the subsequent positions are required to be of the same category until the minimum number is reached
- paths_ranked subquery: Excludes records that are not of full length,, and ranks those that are by profit
- top_ten_paths subquery: Selects the top ten paths and cross-joins them with a row-generator to provide an indexed set of records with set size cardinality for each path
- top_ten_teams subquery: Builds the item records for each of the best sets by extracting the item id from the paths according to index
- Main query: Joins items table to provide additional attributes
PL/SQL Recursive Solution
This is a version in the form of a pipelined function.
SQL
SELECT t.sol_profit,
t.sol_price,
Dense_Rank() OVER (ORDER BY t.sol_profit DESC, t.sol_price) RNK,
p.position_id,
t.item_id,
p.club_name,
p.player_name,
p.price,
p.avg_points
FROM TABLE (Item_Cats.Best_N_Sets (
p_keep_size => 10,
p_max_calls => 100000,
p_n_size => 10,
p_max_price => 900,
p_cat_cur => CURSOR (
SELECT id, min_players, max_players
FROM positions
ORDER BY CASE WHEN id != 'AL' THEN 0 END, id
),
p_item_cur => CURSOR (
SELECT id, price, avg_points, position_id
FROM players
ORDER BY position_id, avg_points DESC
)
)
) t
JOIN players p
ON p.id = t.item_id
ORDER BY t.sol_profit DESC, t.sol_price, p.position_id, t.item_id
Package
CREATE OR REPLACE PACKAGE Item_Cats AS
/**************************************************************************************************
Author: Brendan Furey
Date: 7 July 2013
Description: Brendan's pipelined function solution for the knapsack problem with one container,
and items having categories with validity bands, as described at
http://aprogrammerwrites.eu/?p=878 (SQL for the Fantasy Football Knapsack Problem)
***************************************************************************************************/
TYPE sol_detail_rec_type IS RECORD (
set_id NUMBER,
item_id VARCHAR2(100),
sol_price NUMBER,
sol_profit NUMBER
);
TYPE sol_detail_list_type IS VARRAY(100) OF sol_detail_rec_type;
FUNCTION Best_N_Sets ( p_keep_size PLS_INTEGER,
p_max_calls PLS_INTEGER,
p_n_size PLS_INTEGER,
p_max_price PLS_INTEGER,
p_cat_cur SYS_REFCURSOR,
p_item_cur SYS_REFCURSOR) RETURN sol_detail_list_type PIPELINED;
END Item_Cats;
/
SHO ERR
CREATE OR REPLACE PACKAGE BODY Item_Cats AS
c_cat_all CONSTANT VARCHAR2(3) := 'AL';
c_hash_renew_point CONSTANT PLS_INTEGER := 1000;
--
-- Bulk collect array types
--
TYPE cat_rec_type IS RECORD (
id VARCHAR2(3),
min_items PLS_INTEGER,
max_items PLS_INTEGER
);
TYPE cat_list_type IS VARRAY(100) OF cat_rec_type;
TYPE item_cat_rec_type IS RECORD (
id VARCHAR2(10),
price PLS_INTEGER,
profit PLS_INTEGER,
cat_id VARCHAR2(3)
);
TYPE item_cat_list_type IS VARRAY(1000) OF item_cat_rec_type;
TYPE chr_hash_type IS TABLE OF PLS_INTEGER INDEX BY VARCHAR2(30);
--
-- Input data LOL types
--
TYPE num_range_rec_type IS RECORD (
item_beg PLS_INTEGER,
item_end PLS_INTEGER
);
TYPE num_range_list_type IS VARRAY(1000) OF num_range_rec_type;
TYPE num_list_type IS VARRAY(100) OF PLS_INTEGER;
--
-- Solution types
--
TYPE id_list_type IS VARRAY(100) OF VARCHAR2(10);
TYPE sol_rec_type IS RECORD ( -- trial solution and record in retained array
item_list id_list_type,
price PLS_INTEGER,
profit PLS_INTEGER
);
TYPE sol_list_type IS VARRAY(100) OF sol_rec_type; -- retained solutions
TYPE int_hash_type IS TABLE OF PLS_INTEGER INDEX BY PLS_INTEGER;
g_keep_size PLS_INTEGER;
g_max_calls PLS_INTEGER;
g_n_size PLS_INTEGER;
g_max_price PLS_INTEGER;
g_cat_hash chr_hash_type;
g_item_range_list num_range_list_type := num_range_list_type();
g_hash_buffer int_hash_type;
g_profit_hash int_hash_type;
g_trial_sol sol_rec_type;
g_sol_list sol_list_type := sol_list_type();
g_cat_list cat_list_type;
g_item_cat_list item_cat_list_type;
g_n_cats PLS_INTEGER;
g_n_items PLS_INTEGER;
g_set_size PLS_INTEGER;
g_nth_profit PLS_INTEGER := 0;
g_min_item_price PLS_INTEGER := 1000000;
g_max_item_profit PLS_INTEGER := 0;
g_min_price_togo num_list_type := num_list_type();
g_max_profit_togo num_list_type := num_list_type();
g_n_recursive_calls PLS_INTEGER := 0;
g_n_sols PLS_INTEGER := 0;
PROCEDURE Write_Log (p_line VARCHAR2, p_debug_level PLS_INTEGER DEFAULT 0) IS
BEGIN
IF Utils.g_debug_level >= p_debug_level THEN
Utils.Write_Log (p_line);
END IF;
END Write_Log;
FUNCTION Dedup_Hash (p_card PLS_INTEGER, p_key PLS_INTEGER, p_hash int_hash_type) RETURN PLS_INTEGER IS
l_trial_key PLS_INTEGER := p_card * p_key;
BEGIN
LOOP
IF p_hash.EXISTS (l_trial_key) THEN
l_trial_key := l_trial_key + 1;
ELSE
EXIT;
END IF;
END LOOP;
RETURN l_trial_key;
END Dedup_Hash;
PROCEDURE Pop_Arrays (p_cat_cur SYS_REFCURSOR, p_item_cur SYS_REFCURSOR) IS
n_cat PLS_INTEGER := 0;
l_price PLS_INTEGER;
l_profit PLS_INTEGER;
l_last_cat VARCHAR2(30) := '???';
l_item_price_hash int_hash_type;
l_item_profit_hash int_hash_type;
BEGIN
FETCH p_cat_cur BULK COLLECT INTO g_cat_list;
CLOSE p_cat_cur;
Write_Log ('Collected ' || g_cat_list.COUNT || ' cats');
FETCH p_item_cur BULK COLLECT INTO g_item_cat_list;
CLOSE p_item_cur;
Write_Log ('Collected ' || g_item_cat_list.COUNT || ' items');
Write_Log (g_n_cats || ' cats');
g_n_cats := g_cat_list.COUNT - 1;
g_item_range_list.EXTEND (g_n_cats);
FOR i IN 1..g_cat_list.COUNT LOOP
IF g_cat_list(i).id = c_cat_all THEN
g_set_size := g_cat_list(i).min_items;
ELSE
g_cat_hash (g_cat_list(i).id) := i;
END IF;
END LOOP;
g_cat_list.TRIM;
FOR i IN 1..g_item_cat_list.COUNT LOOP
IF g_item_cat_list(i).price < g_min_item_price THEN
g_min_item_price := g_item_cat_list(i).price;
END IF;
IF g_item_cat_list(i).profit > g_max_item_profit THEN
g_max_item_profit := g_item_cat_list(i).profit;
END IF;
l_item_price_hash (Dedup_Hash (p_card => g_item_cat_list.COUNT, p_key => g_item_cat_list(i).price, p_hash => l_item_price_hash)) := i;
l_item_profit_hash (Dedup_Hash (p_card => g_item_cat_list.COUNT, p_key => g_item_cat_list(i).profit, p_hash => l_item_profit_hash)) := i;
IF g_item_cat_list(i).cat_id != l_last_cat THEN
--
-- Cat has changed, so reset the itm number to zero, and assign the list of items
-- for previous cat
--
n_cat := n_cat + 1;
g_item_range_list (n_cat).item_beg := i;
IF i > 1 THEN
g_item_range_list (n_cat - 1).item_end := i - 1;
END IF;
l_last_cat := g_item_cat_list(i).cat_id;
END IF;
END LOOP;
g_n_items := g_item_cat_list.COUNT;
g_item_range_list (g_n_cats).item_end := g_n_items;
g_min_price_togo.EXTEND (g_set_size);
g_max_profit_togo.EXTEND (g_set_size);
l_price := l_item_price_hash.FIRST;
l_profit := l_item_profit_hash.LAST;
Write_Log ('Hash first price min / profit max ' || l_price || ' / ' || l_profit);
g_min_price_togo (g_set_size) := 0;
g_max_profit_togo (g_set_size) := 0;
FOR i IN 1..g_set_size - 1 LOOP
g_min_price_togo (g_set_size - i) := g_min_price_togo (g_set_size - i + 1) + l_price / g_item_cat_list.COUNT;
g_max_profit_togo (g_set_size - i) := g_max_profit_togo (g_set_size - i + 1) + l_profit / g_item_cat_list.COUNT;
l_price := l_item_price_hash.NEXT (l_price);
l_profit := l_item_profit_hash.PRIOR (l_profit);
Write_Log ((g_set_size - i) || ': price min / profit max ' || g_min_price_togo (g_set_size - i) || ' / ' || g_max_profit_togo (g_set_size - i));
END LOOP;
Write_Log ('Price min / profit max ' || g_min_item_price || ' / ' || g_max_item_profit);
FOR i IN 1..g_n_cats LOOP
Utils.Write_Log ('Cat ' || i || ' : ' || g_cat_list(i).id || ' - ' || g_cat_list(i).min_items || ' - ' || g_cat_list(i).max_items || ' - ' || g_item_range_list(i).item_beg || ' - ' || g_item_range_list(i).item_end);
END LOOP;
g_sol_list.EXTEND (g_n_size);
FOR i IN 1..g_n_size LOOP
g_profit_hash (i) := i;
END LOOP;
g_nth_profit := g_profit_hash.FIRST;
g_trial_sol.price := 0;
g_trial_sol.profit := 0;
END Pop_Arrays;
PROCEDURE Get_Best_Item_List (p_position PLS_INTEGER, p_item_index_beg PLS_INTEGER, p_item_index_end PLS_INTEGER, x_item_hash IN OUT NOCOPY int_hash_type) IS
PROCEDURE Check_Item (p_item_index PLS_INTEGER) IS
l_item_rec item_cat_rec_type := g_item_cat_list (p_item_index);
l_item_list num_list_type;
Item_Failed EXCEPTION;
l_item_str VARCHAR2(200) := LPad (l_item_rec.id, (p_position)*3, '.') || '-' || l_item_rec.cat_id || '-' || l_item_rec.price || '-' || l_item_rec.profit;
FUNCTION Price_LB (p_position PLS_INTEGER) RETURN PLS_INTEGER IS
BEGIN
RETURN g_min_price_togo (p_position);
END Price_LB;
FUNCTION Profit_UB (p_position PLS_INTEGER) RETURN PLS_INTEGER IS
BEGIN
RETURN g_max_profit_togo (p_position);
END Profit_UB;
BEGIN
IF l_item_rec.price + g_trial_sol.price + Price_LB (p_position) > g_max_price THEN
l_item_str := l_item_str || ' [price failed ' || (l_item_rec.price + g_trial_sol.price) || ']';
IF (g_set_size - p_position) = 0 THEN
Write_Log ('Solution fails with price of ' || (l_item_rec.price + g_trial_sol.price), 1);
END IF;
RAISE Item_Failed;
END IF;
IF l_item_rec.profit + g_trial_sol.profit + Profit_UB (p_position) <= g_nth_profit THEN
l_item_str := l_item_str || ' [profit failed ' || (l_item_rec.profit + g_trial_sol.profit) || ', nth = ' || g_nth_profit || ']';
IF (g_set_size - p_position) = 0 THEN
Write_Log ('Solution fails with profit of ' || (l_item_rec.profit + g_trial_sol.profit), 1);
g_n_sols := g_n_sols + 1;
END IF;
RAISE Item_Failed;
END IF;
x_item_hash (Dedup_Hash (p_card => g_keep_size, p_key => l_item_rec.profit + g_trial_sol.profit, p_hash => x_item_hash)) := p_item_index;
EXCEPTION
WHEN Item_Failed THEN
Write_Log (l_item_str, 2);
END Check_Item;
BEGIN
FOR i IN p_item_index_beg..p_item_index_end LOOP
Check_Item (i);
END LOOP;
END Get_Best_Item_List;
PROCEDURE Add_Solution IS
l_nth_index PLS_INTEGER;
BEGIN
g_n_sols := g_n_sols + 1;
l_nth_index := g_profit_hash (g_profit_hash.FIRST);
Write_Log ('Solution replaces in position ' || l_nth_index || ' profit is ' || g_trial_sol.profit || ' price is ' || g_trial_sol.price, 1);
g_profit_hash.DELETE (g_profit_hash.FIRST);
g_profit_hash (Dedup_Hash (p_card => g_n_size, p_key => g_trial_sol.profit, p_hash => g_profit_hash)) := l_nth_index;
g_sol_list (l_nth_index) := g_trial_sol;
g_nth_profit := g_profit_hash.FIRST / g_n_size;
IF Mod (g_n_sols, c_hash_renew_point) = 0 THEN -- Not sur eif this works, but is intended to clear memory overhang
g_hash_buffer := g_profit_hash;
g_profit_hash := g_hash_buffer;
END IF;
END Add_Solution;
PROCEDURE Add_Item_To_Trial (p_position PLS_INTEGER, p_item_index PLS_INTEGER) IS
l_item_rec item_cat_rec_type := g_item_cat_list (p_item_index);
BEGIN
g_trial_sol.price := g_trial_sol.price + l_item_rec.price;
g_trial_sol.profit := g_trial_sol.profit + l_item_rec.profit;
IF g_trial_sol.item_list IS NULL THEN
g_trial_sol.item_list := id_list_type (l_item_rec.id);
ELSE
g_trial_sol.item_list.EXTEND;
g_trial_sol.item_list (p_position) := l_item_rec.id;
END IF;
IF p_position = g_set_size THEN
Add_Solution;
END IF;
END Add_Item_To_Trial;
FUNCTION Try_Position (p_position PLS_INTEGER, p_n_curr_cat PLS_INTEGER, p_cat_index_beg PLS_INTEGER, p_item_index_beg PLS_INTEGER) RETURN BOOLEAN IS
l_item_hash int_hash_type;
l_item_index PLS_INTEGER;
l_cat_index_beg PLS_INTEGER := p_cat_index_beg;
l_item_index_beg PLS_INTEGER := p_item_index_beg;
l_n_curr_cat PLS_INTEGER := p_n_curr_cat;
l_profit PLS_INTEGER;
BEGIN
g_n_recursive_calls := g_n_recursive_calls + 1;
IF g_n_recursive_calls > g_max_calls THEN
Write_Log (LPad ('*', p_position, '*') || 'Truncating search after ' || g_max_calls || ' recursive calls***');
RETURN TRUE;
END IF;
IF p_n_curr_cat = g_cat_list (p_cat_index_beg).max_items THEN
--
-- passed in the cat we were on in last position
-- check max not passed, if so go to next cat and reset item range
--
Write_Log ('Maxed Cat ' || p_cat_index_beg || ': ' || p_n_curr_cat || '-' || g_cat_list (p_cat_index_beg).max_items, 5);
l_cat_index_beg := p_cat_index_beg + 1;
IF l_cat_index_beg > g_n_cats THEN
RETURN FALSE;
END IF;
l_item_index_beg := g_item_range_list (l_cat_index_beg).item_beg;
l_n_curr_cat := 0;
END IF;
FOR j IN l_cat_index_beg..g_n_cats LOOP
IF l_item_index_beg < g_item_range_list (j).item_beg THEN
l_item_index_beg := g_item_range_list (j).item_beg;
END IF;
Write_Log ('Start Cat ' || j || ': ' || l_n_curr_cat || '-' || g_cat_list(j).min_items, 5);
l_n_curr_cat := l_n_curr_cat + 1;
l_item_hash.DELETE;
Get_Best_Item_List (p_position => p_position, p_item_index_beg => l_item_index_beg, p_item_index_end => g_item_range_list(j).item_end, x_item_hash => l_item_hash);
IF l_item_hash IS NOT NULL THEN
l_profit := l_item_hash.LAST;
FOR i IN 1..Least (g_keep_size, l_item_hash.COUNT) LOOP
l_item_index := l_item_hash (l_profit);
Write_Log (LPad (g_item_cat_list (l_item_index).id, (p_position)*3, '.') || '-' || g_item_cat_list (l_item_index).cat_id || '-' || g_item_cat_list (l_item_index).price || '-' || g_item_cat_list (l_item_index).profit, 1);
Add_Item_To_Trial (p_position => p_position, p_item_index => l_item_index);
IF p_position < g_set_size THEN
IF Try_Position (p_position => p_position + 1, p_n_curr_cat => l_n_curr_cat, p_cat_index_beg => j, p_item_index_beg => l_item_index + 1) THEN RETURN TRUE; END IF;
END IF;
IF g_trial_sol.item_list IS NOT NULL AND g_trial_sol.item_list.COUNT = p_position THEN
g_trial_sol.item_list.TRIM;
g_trial_sol.price := g_trial_sol.price - g_item_cat_list (l_item_index).price;
g_trial_sol.profit := g_trial_sol.profit - g_item_cat_list (l_item_index).profit;
END IF;
l_profit := l_item_hash.PRIOR (l_profit);
END LOOP;
ELSE
Write_Log ('No items found');
END IF;
--
-- Don't look at any more cats if we are not past the minimum for the current one at this position
--
Write_Log ('Cat ' || j || ': ' || l_n_curr_cat || '-' || g_cat_list(j).min_items, 5);
IF l_n_curr_cat <= g_cat_list(j).min_items THEN
EXIT;
END IF;
l_n_curr_cat := 0;
END LOOP;
RETURN FALSE;
END Try_Position;
FUNCTION Best_N_Sets ( p_keep_size PLS_INTEGER,
p_max_calls PLS_INTEGER,
p_n_size PLS_INTEGER,
p_max_price PLS_INTEGER,
p_cat_cur SYS_REFCURSOR,
p_item_cur SYS_REFCURSOR) RETURN sol_detail_list_type PIPELINED IS
l_sol_detail_rec sol_detail_rec_type;
l_position PLS_INTEGER := 1;
BEGIN
g_keep_size := p_keep_size; g_max_calls := p_max_calls; g_n_size := p_n_size; g_max_price := p_max_price;
Pop_Arrays (p_cat_cur, p_item_cur);
IF Try_Position (p_position => 1, p_n_curr_cat => 0, p_cat_index_beg => 1, p_item_index_beg => 1) THEN NULL; END IF;
FOR i IN 1..g_n_size LOOP
l_sol_detail_rec.set_id := i;
l_sol_detail_rec.sol_price := g_sol_list(i).price;
l_sol_detail_rec.sol_profit := g_sol_list(i).profit;
IF g_sol_list(i).item_list IS NOT NULL THEN
FOR j IN 1..g_sol_list(i).item_list.COUNT LOOP
l_sol_detail_rec.item_id := g_sol_list(i).item_list(j);
PIPE ROW (l_sol_detail_rec);
END LOOP;
END IF;
END LOOP;
Write_Log (g_n_sols || ' solutions found in ' || g_n_recursive_calls || ' recursive calls');
RETURN;
END Best_N_Sets;
END Item_Cats;
/
SHO ERR
How It Works
The solution approach uses a modified depth-first recursion, following a similar idea to the SQL method, of adding items in strictly increasing order of category and profit ranking. Treatment of constraints uses similar ideas to the SQL solution.
- The package is completely generic, with the items and categories being specified by means of input cursors
- Depth-first is modified by a ranking of the next sets of feasible items, partitioned by category, in order to limit the number progressed
- Hashes (associative arrays in Oracle) are used for ranking
- A function, Dedup_Hash is used to allow for duplicate hash keys; it works by storing as key the actual key multiplied by the ranking set cardinality, then adding one iteratively until no duplication occurs
- The recursion is truncated if the number of recursive calls exceeds an input limit
- The input cursors are read into arrays and all subsequent processing is in memory; this is not a scalability problem because only the current best solutions are retained; also, I reset hashes after a given number of updates
Results
Test Problem 1: Brazilian League
The pipelined function solved this in 5 seconds, while the SQL solution solved it in 21 seconds. The solutions were identical, as follows:
TOT_PROFIT TOT_PRICE RNK PO P_ID PLAYER_NAME CLUB_NAME PRICE AVG_POINTS
---------- ---------- ---------- -- ---- ------------------------------ ------------------------------ ---------- ----------
10923 18176 1 CB 098 Digão Fluminense 931 927
099 Samir Flamengo 267 680
CO 078 Jaime De AlMFda Flamengo 1156 803
FW 001 Éderson Atlético-PR 1712 1012
002 Maxi Biancucchi Vitória 1962 1005
003 Rafael Sobis Fluminense 2303 955
GK 022 Wilson Vitória 1239 794
MF 058 Fred Internacional 3028 892
059 Zé Roberto Grêmio 2593 878
060 Otavinho Internacional 762 807
WB 038 Ivan Portuguesa 755 1320
039 Elsinho Vasco 1468 850
19027 2 CB 098 Digão Fluminense 931 927
099 Samir Flamengo 267 680
CO 078 Jaime De AlMFda Flamengo 1156 803
FW 001 Éderson Atlético-PR 1712 1012
002 Maxi Biancucchi Vitória 1962 1005
003 Rafael Sobis Fluminense 2303 955
GK 021 Fábio Cruzeiro 2090 794
MF 058 Fred Internacional 3028 892
059 Zé Roberto Grêmio 2593 878
060 Otavinho Internacional 762 807
WB 038 Ivan Portuguesa 755 1320
039 Elsinho Vasco 1468 850
10905 18795 3 CB 098 Digão Fluminense 931 927
099 Samir Flamengo 267 680
CO 078 Jaime De AlMFda Flamengo 1156 803
FW 001 Éderson Atlético-PR 1712 1012
002 Maxi Biancucchi Vitória 1962 1005
003 Rafael Sobis Fluminense 2303 955
GK 023 Vanderlei Coritiba 1858 776
MF 058 Fred Internacional 3028 892
059 Zé Roberto Grêmio 2593 878
060 Otavinho Internacional 762 807
WB 038 Ivan Portuguesa 755 1320
039 Elsinho Vasco 1468 850
10833 18994 4 CB 098 Digão Fluminense 931 927
102 Bressan Grêmio 1085 590
CO 078 Jaime De AlMFda Flamengo 1156 803
FW 001 Éderson Atlético-PR 1712 1012
002 Maxi Biancucchi Vitória 1962 1005
003 Rafael Sobis Fluminense 2303 955
GK 022 Wilson Vitória 1239 794
MF 058 Fred Internacional 3028 892
059 Zé Roberto Grêmio 2593 878
060 Otavinho Internacional 762 807
WB 038 Ivan Portuguesa 755 1320
039 Elsinho Vasco 1468 850
19845 5 CB 098 Digão Fluminense 931 927
102 Bressan Grêmio 1085 590
CO 078 Jaime De AlMFda Flamengo 1156 803
FW 001 Éderson Atlético-PR 1712 1012
002 Maxi Biancucchi Vitória 1962 1005
003 Rafael Sobis Fluminense 2303 955
GK 021 Fábio Cruzeiro 2090 794
MF 058 Fred Internacional 3028 892
059 Zé Roberto Grêmio 2593 878
060 Otavinho Internacional 762 807
WB 038 Ivan Portuguesa 755 1320
039 Elsinho Vasco 1468 850
10831 19608 6 CB 098 Digão Fluminense 931 927
103 Manoel Atlético-PR 1699 588
CO 078 Jaime De AlMFda Flamengo 1156 803
FW 001 Éderson Atlético-PR 1712 1012
002 Maxi Biancucchi Vitória 1962 1005
003 Rafael Sobis Fluminense 2303 955
GK 022 Wilson Vitória 1239 794
MF 058 Fred Internacional 3028 892
059 Zé Roberto Grêmio 2593 878
060 Otavinho Internacional 762 807
WB 038 Ivan Portuguesa 755 1320
039 Elsinho Vasco 1468 850
10825 18190 7 CB 098 Digão Fluminense 931 927
099 Samir Flamengo 267 680
CO 078 Jaime De AlMFda Flamengo 1156 803
FW 001 Éderson Atlético-PR 1712 1012
002 Maxi Biancucchi Vitória 1962 1005
003 Rafael Sobis Fluminense 2303 955
GK 022 Wilson Vitória 1239 794
MF 058 Fred Internacional 3028 892
059 Zé Roberto Grêmio 2593 878
060 Otavinho Internacional 762 807
WB 038 Ivan Portuguesa 755 1320
040 Egídio Cruzeiro 1482 752
19041 8 CB 098 Digão Fluminense 931 927
099 Samir Flamengo 267 680
CO 078 Jaime De AlMFda Flamengo 1156 803
FW 001 Éderson Atlético-PR 1712 1012
002 Maxi Biancucchi Vitória 1962 1005
003 Rafael Sobis Fluminense 2303 955
GK 021 Fábio Cruzeiro 2090 794
MF 058 Fred Internacional 3028 892
059 Zé Roberto Grêmio 2593 878
060 Otavinho Internacional 762 807
WB 038 Ivan Portuguesa 755 1320
040 Egídio Cruzeiro 1482 752
10821 19370 9 CB 098 Digão Fluminense 931 927
104 Cléber Ponte Preta 1461 578
CO 078 Jaime De AlMFda Flamengo 1156 803
FW 001 Éderson Atlético-PR 1712 1012
002 Maxi Biancucchi Vitória 1962 1005
003 Rafael Sobis Fluminense 2303 955
GK 022 Wilson Vitória 1239 794
MF 058 Fred Internacional 3028 892
059 Zé Roberto Grêmio 2593 878
060 Otavinho Internacional 762 807
WB 038 Ivan Portuguesa 755 1320
039 Elsinho Vasco 1468 850
10815 19613 10 CB 098 Digão Fluminense 931 927
102 Bressan Grêmio 1085 590
CO 078 Jaime De AlMFda Flamengo 1156 803
FW 001 Éderson Atlético-PR 1712 1012
002 Maxi Biancucchi Vitória 1962 1005
003 Rafael Sobis Fluminense 2303 955
GK 023 Vanderlei Coritiba 1858 776
MF 058 Fred Internacional 3028 892
059 Zé Roberto Grêmio 2593 878
060 Otavinho Internacional 762 807
WB 038 Ivan Portuguesa 755 1320
039 Elsinho Vasco 1468 850
120 rows selected.
Test Problem 2: English Premier League
I used a maximum price of 900, and a keep parameter of 40, meaning retain the best 40 records by partition during recursion for the SQL and a value of 10 for the pipelined function. The keep parameter operates differently in the two cases so does not need to be the same value.
The SQL solution took 98 seconds, while the pipelined function took 290 seconds. Both methods got the same best solution, but the tenth best was marginally better for the SQL, at 1965, compared with 1962 for pipelined function (which truncated after 100000 recursive calls).
[For followers of Manchester United, and David Moyes, it may be of interest to note that all of the best solutions included both Leighton Baines and Patrice Evra, and the best also had Marouane Fellaini. Will these players be united also in the real world next season?]
SQL Solution
TOT_PROFIT TOT_PRICE RNK PO P_ID PLAYER_NAME CLUB_NAME PRICE AVG_POINTS
---------- ---------- ---------- -- ---- ------------------------------ --------------- ---------- ----------
1973 898 1 DF 165 Leighton Baines Everton 78 173
332 Patrice Evra Man Utd 73 152
268 Glen Johnson Liverpool 65 141
FW 286 Luis Suarez Liverpool 105 213
533 Rickie Lambert Southampton 69 178
GK 549 Asmir Begovic Stoke City 56 154
MF 661 Gareth Bale Tottenham 111 240
030 Santi Santi Cazorla Arsenal 97 198
265 Steven Gerrard Liverpool 92 187
641 Miguel Michu Swansea 79 169
177 Marouane Fellaini Everton 73 168
1971 899 2 DF 165 Leighton Baines Everton 78 173
332 Patrice Evra Man Utd 73 152
268 Glen Johnson Liverpool 65 141
FW 286 Luis Suarez Liverpool 105 213
533 Rickie Lambert Southampton 69 178
047 Christian Benteke Aston Villa 74 166
GK 549 Asmir Begovic Stoke City 56 154
MF 661 Gareth Bale Tottenham 111 240
030 Santi Santi Cazorla Arsenal 97 198
265 Steven Gerrard Liverpool 92 187
641 Miguel Michu Swansea 79 169
1970 893 3 DF 165 Leighton Baines Everton 78 173
332 Patrice Evra Man Utd 73 152
268 Glen Johnson Liverpool 65 141
FW 286 Luis Suarez Liverpool 105 213
533 Rickie Lambert Southampton 69 178
047 Christian Benteke Aston Villa 74 166
GK 549 Asmir Begovic Stoke City 56 154
MF 661 Gareth Bale Tottenham 111 240
030 Santi Santi Cazorla Arsenal 97 198
265 Steven Gerrard Liverpool 92 187
177 Marouane Fellaini Everton 73 168
1968 899 4 DF 165 Leighton Baines Everton 78 173
332 Patrice Evra Man Utd 73 152
268 Glen Johnson Liverpool 65 141
FW 286 Luis Suarez Liverpool 105 213
533 Rickie Lambert Southampton 69 178
047 Christian Benteke Aston Villa 74 166
MF 661 Gareth Bale Tottenham 111 240
030 Santi Santi Cazorla Arsenal 97 198
265 Steven Gerrard Liverpool 92 187
177 Marouane Fellaini Everton 73 168
428 Robert Snodgrass Norwich 62 152
5 DF 165 Leighton Baines Everton 78 173
332 Patrice Evra Man Utd 73 152
569 Ryan Shawcross Stoke City 56 133
FW 286 Luis Suarez Liverpool 105 213
533 Rickie Lambert Southampton 69 178
GK 549 Asmir Begovic Stoke City 56 154
MF 661 Gareth Bale Tottenham 111 240
030 Santi Santi Cazorla Arsenal 97 198
149 Juan Mata Chelsea 102 190
641 Miguel Michu Swansea 79 169
177 Marouane Fellaini Everton 73 168
900 6 DF 165 Leighton Baines Everton 78 173
332 Patrice Evra Man Utd 73 152
268 Glen Johnson Liverpool 65 141
FW 286 Luis Suarez Liverpool 105 213
533 Rickie Lambert Southampton 69 178
204 Dimitar Berbatov Fulham 71 161
GK 549 Asmir Begovic Stoke City 56 154
MF 661 Gareth Bale Tottenham 111 240
030 Santi Santi Cazorla Arsenal 97 198
149 Juan Mata Chelsea 102 190
177 Marouane Fellaini Everton 73 168
1966 896 7 DF 165 Leighton Baines Everton 78 173
332 Patrice Evra Man Utd 73 152
268 Glen Johnson Liverpool 65 141
FW 286 Luis Suarez Liverpool 105 213
533 Rickie Lambert Southampton 69 178
204 Dimitar Berbatov Fulham 71 161
GK 549 Asmir Begovic Stoke City 56 154
MF 661 Gareth Bale Tottenham 111 240
030 Santi Santi Cazorla Arsenal 97 198
265 Steven Gerrard Liverpool 92 187
641 Miguel Michu Swansea 79 169
900 8 DF 165 Leighton Baines Everton 78 173
332 Patrice Evra Man Utd 73 152
569 Ryan Shawcross Stoke City 56 133
FW 286 Luis Suarez Liverpool 105 213
533 Rickie Lambert Southampton 69 178
047 Christian Benteke Aston Villa 74 166
GK 549 Asmir Begovic Stoke City 56 154
MF 661 Gareth Bale Tottenham 111 240
030 Santi Santi Cazorla Arsenal 97 198
149 Juan Mata Chelsea 102 190
641 Miguel Michu Swansea 79 169
1965 890 9 DF 165 Leighton Baines Everton 78 173
332 Patrice Evra Man Utd 73 152
268 Glen Johnson Liverpool 65 141
FW 286 Luis Suarez Liverpool 105 213
533 Rickie Lambert Southampton 69 178
204 Dimitar Berbatov Fulham 71 161
GK 549 Asmir Begovic Stoke City 56 154
MF 661 Gareth Bale Tottenham 111 240
030 Santi Santi Cazorla Arsenal 97 198
265 Steven Gerrard Liverpool 92 187
177 Marouane Fellaini Everton 73 168
894 10 DF 165 Leighton Baines Everton 78 173
332 Patrice Evra Man Utd 73 152
569 Ryan Shawcross Stoke City 56 133
FW 286 Luis Suarez Liverpool 105 213
533 Rickie Lambert Southampton 69 178
047 Christian Benteke Aston Villa 74 166
GK 549 Asmir Begovic Stoke City 56 154
MF 661 Gareth Bale Tottenham 111 240
030 Santi Santi Cazorla Arsenal 97 198
149 Juan Mata Chelsea 102 190
177 Marouane Fellaini Everton 73 168
110 rows selected.
Elapsed: 00:01:38.26
Pipelined Function Solution
SOL_PROFIT SOL_PRICE RNK PO ITEM_ID CLUB_NAME PLAYER_NAME PRICE AVG_POINTS
---------- ---------- ---------- -- ---------- --------------- -------------------- ---------- ----------
1973 898 1 DF 165 Everton Leighton Baines 78 173
268 Liverpool Glen Johnson 65 141
332 Man Utd Patrice Evra 73 152
FW 286 Liverpool Luis Suarez 105 213
533 Southampton Rickie Lambert 69 178
GK 549 Stoke City Asmir Begovic 56 154
MF 177 Everton Marouane Fellaini 73 168
265 Liverpool Steven Gerrard 92 187
30 Arsenal Santi Santi Cazorla 97 198
641 Swansea Miguel Michu 79 169
661 Tottenham Gareth Bale 111 240
1971 899 2 DF 165 Everton Leighton Baines 78 173
268 Liverpool Glen Johnson 65 141
332 Man Utd Patrice Evra 73 152
FW 286 Liverpool Luis Suarez 105 213
47 Aston Villa Christian Benteke 74 166
533 Southampton Rickie Lambert 69 178
GK 549 Stoke City Asmir Begovic 56 154
MF 265 Liverpool Steven Gerrard 92 187
30 Arsenal Santi Santi Cazorla 97 198
641 Swansea Miguel Michu 79 169
661 Tottenham Gareth Bale 111 240
1970 893 3 DF 165 Everton Leighton Baines 78 173
268 Liverpool Glen Johnson 65 141
332 Man Utd Patrice Evra 73 152
FW 286 Liverpool Luis Suarez 105 213
47 Aston Villa Christian Benteke 74 166
533 Southampton Rickie Lambert 69 178
GK 549 Stoke City Asmir Begovic 56 154
MF 177 Everton Marouane Fellaini 73 168
265 Liverpool Steven Gerrard 92 187
30 Arsenal Santi Santi Cazorla 97 198
661 Tottenham Gareth Bale 111 240
1968 900 4 DF 165 Everton Leighton Baines 78 173
268 Liverpool Glen Johnson 65 141
332 Man Utd Patrice Evra 73 152
FW 204 Fulham Dimitar Berbatov 71 161
286 Liverpool Luis Suarez 105 213
533 Southampton Rickie Lambert 69 178
GK 549 Stoke City Asmir Begovic 56 154
MF 149 Chelsea Juan Mata 102 190
177 Everton Marouane Fellaini 73 168
30 Arsenal Santi Santi Cazorla 97 198
661 Tottenham Gareth Bale 111 240
1966 896 5 DF 165 Everton Leighton Baines 78 173
268 Liverpool Glen Johnson 65 141
332 Man Utd Patrice Evra 73 152
FW 204 Fulham Dimitar Berbatov 71 161
286 Liverpool Luis Suarez 105 213
533 Southampton Rickie Lambert 69 178
GK 549 Stoke City Asmir Begovic 56 154
MF 265 Liverpool Steven Gerrard 92 187
30 Arsenal Santi Santi Cazorla 97 198
641 Swansea Miguel Michu 79 169
661 Tottenham Gareth Bale 111 240
1965 890 6 DF 165 Everton Leighton Baines 78 173
268 Liverpool Glen Johnson 65 141
332 Man Utd Patrice Evra 73 152
FW 204 Fulham Dimitar Berbatov 71 161
286 Liverpool Luis Suarez 105 213
533 Southampton Rickie Lambert 69 178
GK 549 Stoke City Asmir Begovic 56 154
MF 177 Everton Marouane Fellaini 73 168
265 Liverpool Steven Gerrard 92 187
30 Arsenal Santi Santi Cazorla 97 198
661 Tottenham Gareth Bale 111 240
897 7 DF 165 Everton Leighton Baines 78 173
248 Liverpool Daniel Agger 64 133
332 Man Utd Patrice Evra 73 152
FW 286 Liverpool Luis Suarez 105 213
533 Southampton Rickie Lambert 69 178
GK 549 Stoke City Asmir Begovic 56 154
MF 177 Everton Marouane Fellaini 73 168
265 Liverpool Steven Gerrard 92 187
30 Arsenal Santi Santi Cazorla 97 198
641 Swansea Miguel Michu 79 169
661 Tottenham Gareth Bale 111 240
1964 895 8 DF 165 Everton Leighton Baines 78 173
268 Liverpool Glen Johnson 65 141
332 Man Utd Patrice Evra 73 152
FW 286 Liverpool Luis Suarez 105 213
533 Southampton Rickie Lambert 69 178
720 West Brom Romelu Lukaku 66 157
GK 549 Stoke City Asmir Begovic 56 154
MF 149 Chelsea Juan Mata 102 190
177 Everton Marouane Fellaini 73 168
30 Arsenal Santi Santi Cazorla 97 198
661 Tottenham Gareth Bale 111 240
1963 898 9 DF 165 Everton Leighton Baines 78 173
248 Liverpool Daniel Agger 64 133
332 Man Utd Patrice Evra 73 152
FW 286 Liverpool Luis Suarez 105 213
47 Aston Villa Christian Benteke 74 166
533 Southampton Rickie Lambert 69 178
GK 549 Stoke City Asmir Begovic 56 154
MF 265 Liverpool Steven Gerrard 92 187
30 Arsenal Santi Santi Cazorla 97 198
641 Swansea Miguel Michu 79 169
661 Tottenham Gareth Bale 111 240
1962 891 10 DF 165 Everton Leighton Baines 78 173
268 Liverpool Glen Johnson 65 141
332 Man Utd Patrice Evra 73 152
FW 286 Liverpool Luis Suarez 105 213
533 Southampton Rickie Lambert 69 178
720 West Brom Romelu Lukaku 66 157
GK 549 Stoke City Asmir Begovic 56 154
MF 265 Liverpool Steven Gerrard 92 187
30 Arsenal Santi Santi Cazorla 97 198
641 Swansea Miguel Michu 79 169
661 Tottenham Gareth Bale 111 240
110 rows selected.
Elapsed: 00:04:49.92
Conclusions
My idea for using recursive subquery factoring to solve combinatorial optimisation problems, such as knapsack problems, described in other articles on my blog, was previously only practical for small problems. The extensions described here render it a practical proposition even for larger problems. It is also relatively simple compared with procedural approaches.
