null program

Football Parity

All relevant sources: hamil.git/nfl/

I'm not a sports fan, but today I saw a graphic today demonstrating parity in the 2010 NFL season.

A demonstration of NFL parity in one handy, circular graphic

Basically, for any team in the league, you can use this graphic to trace a chain of wins back to your favored team. With it you can always prove to your buddies how much better your team is than theirs, because your team technically beat them.

To make one of these all you need is the win/loss information for the season. Create a directed graph with it, then find a Hamiltonian cycle in the graph and you have one of these circular graphs.

I wanted to this this out for myself with the 2008 and 2009 seasons. As usual, getting data in a usable format is the hardest part of the whole task. Using a combination of these two sources I managed to get some reasonable information,

So here's the score data in s-exp form.

And the resulting graphs, expressed using my preferred alist form,

graph2008.el

((Chargers Jets Patriots Raiders Chiefs Buccaneers Broncos)
 (Broncos Raiders Chargers Saints Buccaneers Browns Falcons Jets Chiefs)
 (Cardinals Dolphins Bills Cowboys 49ers Rams Seahawks)
 (Seahawks 49ers Rams Jets)
 (Eagles Rams Steelers 49ers Falcons Seahawks Cardinals Giants Browns Cowboys)
 (Cowboys Browns Eagles Packers Bengals Buccaneers Redskins 49ers Seahawks Giants)
 (Dolphins Patriots Chargers Broncos Seahawks Raiders Rams Bills 49ers Chiefs Jets)
 (Jets Dolphins Cardinals Bengals Chiefs Rams Patriots Titans Bills)
 (Ravens Dolphins Raiders Browns Texans Eagles Bengals Redskins Cowboys Jaguars)
 (Jaguars Colts Texans Broncos Lions Packers)
 (49ers Seahawks Lions Bills Jets Rams Redskins)
 (Redskins Saints Cardinals Cowboys Browns Lions Seahawks Eagles)
 (Texans Dolphins Lions Bengals Browns Jaguars Packers Titans Bears)
 (Bears Colts Eagles Vikings Lions Rams Jaguars Saints Packers)
 (Raiders Chiefs Jets Broncos Texans Buccaneers)
 (Buccaneers Falcons Bears Packers Panthers Seahawks Chiefs Lions Saints)
 (Steelers Texans Jaguars Redskins Chargers Bengals Patriots Cowboys Ravens Browns)
 (Browns Bengals Giants Jaguars)
 (Panthers Chargers Bears Falcons Chiefs Cardinals Raiders Lions Packers Buccaneers Broncos Saints)
 (Saints Buccaneers 49ers Raiders Chargers Chiefs Packers Falcons Lions)
 (Vikings Panthers Saints Texans Packers Jaguars Bears Lions Cardinals Giants)
 (Giants Rams Bengals Seahawks 49ers Steelers Cowboys Eagles Ravens Cardinals Redskins Panthers)
 (Colts Vikings Ravens Patriots Steelers Texans Chargers Browns Bengals Lions Jaguars Titans)
 (Titans Bengals Texans Vikings Ravens Chiefs Colts Packers Bears Jaguars Lions Browns Steelers)
 (Packers Vikings Seahawks Colts Bears Lions)
 (Lions)
 (Bengals Jaguars Eagles Redskins Browns Chiefs)
 (Chiefs Broncos Raiders)
 (Patriots Chiefs Jets 49ers Broncos Rams Dolphins Seahawks Raiders Cardinals Bills)
 (Bills Seahawks Jaguars Raiders Rams Chargers Chiefs Broncos)
 (Falcons Lions Chiefs Packers Bears Raiders Saints Panthers Chargers Buccaneers Vikings Rams)
 (Rams Redskins Cowboys))

graph2009.el

((Bengals Packers Bears Ravens Steelers Browns Lions Chiefs)
 (Jets Texans Patriots Titans Raiders Panthers Bills Buccaneers Colts Bengals)
 (Titans Jaguars 49ers Bills Texans Cardinals Rams Dolphins Seahawks)
 (Seahawks Jaguars Lions Rams 49ers)
 (Redskins Rams Buccaneers Broncos Raiders)
 (Chargers Dolphins Raiders Giants Eagles Broncos Chiefs Browns Cowboys Bengals Titans Redskins)
 (Packers Rams Browns Cowboys 49ers Lions Ravens Bears Seahawks Cardinals)
 (Cardinals Jaguars Texans Giants Bears Seahawks Vikings Lions Rams)
 (Ravens Chiefs Chargers Broncos Browns Steelers Lions Bears Raiders)
 (Raiders Chiefs Eagles Bengals Steelers Broncos)
 (Chiefs Redskins Raiders Steelers Broncos)
 (Broncos Bengals Browns Raiders Cowboys Patriots Chargers Giants Chiefs)
 (Eagles Panthers Chiefs Buccaneers Redskins Falcons Giants 49ers Broncos)
 (Cowboys Buccaneers Chiefs Falcons Seahawks Raiders Saints Redskins Eagles)
 (Patriots Falcons Ravens Titans Buccaneers Dolphins Jets Panthers Bills Jaguars)
 (Texans Titans Raiders Bengals 49ers Bills Seahawks Rams Dolphins Patriots)
 (Saints Lions Eagles Bills Jets Giants Dolphins Panthers Rams Buccaneers Patriots Redskins Falcons)
 (Panthers Redskins Cardinals Falcons Buccaneers Vikings Giants Saints)
 (Falcons Dolphins Panthers 49ers Bears Redskins Jets Bills Buccaneers)
 (Buccaneers Packers Seahawks Saints)
 (Giants Buccaneers Chiefs Raiders Falcons Cowboys Redskins)
 (Vikings Browns 49ers Rams Ravens Packers Lions Seahawks Bears Bengals Giants)
 (Steelers Titans Chargers Lions Browns Vikings Broncos Packers Ravens Dolphins)
 (Dolphins Bills Jets Buccaneers Panthers Patriots Jaguars)
 (49ers Seahawks Bears Jaguars Cardinals Lions Rams)
 (Rams Lions)
 (Bears Steelers Seahawks Browns Eagles Rams Vikings Lions)
 (Lions Redskins Browns)
 (Colts Dolphins Cardinals Seahawks Rams 49ers Patriots Ravens Texans Titans Broncos Jaguars)
 (Bills Buccaneers Jets Panthers Dolphins Chiefs Colts)
 (Jaguars Titans Rams Chiefs Jets Bills Texans)
 (Browns Bills Steelers Chiefs Raiders Jaguars))

I attempted to produce a nice visual of the 2009 graph, but this is the best I could get it. I think it's just too complex to display graphically.

So the next step is finding a Hamiltonian cycle in this tree. I've done such a search before. It's hard to find one by hand, but a computer can do it in a reasonable about of time. However, something to important note about 2008 is that there actually is no such cycle! As you can see in the graph s-expression, the Lions lost every single game they played.

Here's a couple 2009 Hamiltonian cycles,

;; 2009 Hamiltonian cycles
(Steelers Titans Jaguars Rams Lions Redskins Buccaneers Packers Browns
 Bills Jets Colts Texans Raiders Chiefs Broncos Bengals Ravens
 Chargers Dolphins Patriots Falcons Panthers Saints Eagles Giants
 Cowboys Seahawks 49ers Cardinals Vikings Bears Steelers)

(Steelers Titans Jaguars Jets Colts Ravens Chargers Browns Chiefs
 Raiders Eagles Giants Cowboys Saints Panthers Vikings Seahawks 49ers
 Cardinals Texans Patriots Falcons Dolphins Bills Buccaneers Packers
 Rams Lions Redskins Broncos Bengals Bears Steelers)

There's nothing unique about this particular cycle. There are about 2118 possible ways to arrange 32 teams. In our graph, there are on average 7 outgoing paths from a node, so we're searching in a space of around 290. There should be many different cycles in that set, but an exhaustive search is completely out of the question.

tags: [ lisp ]
blog comments powered by Disqus
Fork me on GitHub