Hallo, when there are S seats and C candidates (with C > S), then there are C!/(S!*(C-S)!) possible ways to fill these seats. When you compare every possible way to fill these seats with every other possible way that differs in exactly one candidate, then you have to make C!/(S!*(C-S-1)!) comparisons. This cannot be done in a runtime that is polynomial in S and C. The largest example in Tideman's database is example A90 with S=12 seats and C=20 candidates. It takes 49.0 s (on a computer with two 6-core "E5-2630v2 @ 2.60 GHz" processors) to calculate the winning set of Schulze STV. See section 10.3 of this paper: http://m-schulze.9mail.de/verylong.pdf The source code (multi01g.cpp, multi01v.cpp, singl01g.cpp, singl01v.cpp) can be found in this paper: http://m-schulze.9mail.de/schulze3.zip singl01g.cpp and singl01v.cpp are single-threading. multi01g.cpp and multi01v.cpp are multi-treading. singl01g.cpp and multi01g.cpp are for g++. singl01v.cpp and multi01v.cpp are for Microsoft Visual C++. Markus Schulze

49 seconds to count 366 votes is pretty rough. Even if all the explosive combinatorics is in Candidates and Seats and that just scales linearly with additional votes, anything more than a small town starts to take all day to compute. On Sun, Jan 15, 2017 at 7:21 AM, Markus Schulze < markus.schulze@alumni.tu-berlin.de> wrote: > Hallo, > > when there are S seats and C candidates (with C > S), > then there are C!/(S!*(C-S)!) possible ways to fill > these seats. When you compare every possible way > to fill these seats with every other possible way > that differs in exactly one candidate, then you have > to make C!/(S!*(C-S-1)!) comparisons. This cannot be > done in a runtime that is polynomial in S and C. > > The largest example in Tideman's database is example A90 > with S=12 seats and C=20 candidates. It takes 49.0 s > (on a computer with two 6-core "E5-2630v2 @ 2.60 GHz" > processors) to calculate the winning set of Schulze STV. > See section 10.3 of this paper: > > http://m-schulze.9mail.de/verylong.pdf > > The source code (multi01g.cpp, multi01v.cpp, singl01g.cpp, > singl01v.cpp) can be found in this paper: > > http://m-schulze.9mail.de/schulze3.zip > > singl01g.cpp and singl01v.cpp are single-threading. > multi01g.cpp and multi01v.cpp are multi-treading. > > singl01g.cpp and multi01g.cpp are for g++. > singl01v.cpp and multi01v.cpp are for Microsoft Visual C++. > > Markus Schulze > > > ---- > Election-Methods mailing list - see http://electorama.com/em for list info >