roy@phri.UUCP (05/29/87)
[See end of article if you're wondering why this in news.software.b; if you
followup on the math issue, do it only to sci.math; if you followup on the
inews issue, do it only to news.software.b, and change the title, please.]
In article <1324@mmm.UUCP> cipher@mmm.UUCP (Andre Guirard) writes:
(regarding my vote-counting question)
-> Why is it that everyone is answering this person's question and not
-> commenting, hey, you probably don't want to do this because it'll
-> destroy the democratic process at your co-op.
I would guess they are answering the question because I asked it
and they knew the answer. That's the way it's supposed to work. I can
deal with my own ethics, thank you. Just to salve your conscience, however,
let me point out that the election in question was 6 months ago and far
past the point when any protest would have mattered; this was based on
real-life, but was mostly an academic exercise. Our most recent election
(last week) was uncontested.
Now, let me take this opportunity to explain why I think I should
be elected to the office of ... (oops, wrong speech) ... uh, to thank all
the people who wrote with suggestions and answers to my question. A number
of people posted answers, you all know who they are. In addition,
William C. Bauldry <cmcl2!seismo!mcnc.org!ecsvax!wmcb>
allegra!alice!amo (Andrew Odlyzko)
allegra!uiucdcs!b.cs.uiuc.edu!robison (Arch Robison)
wrote directly to me with suggestions. Numerous people pointed out that
what I described is the knapsack problem which is NP-complete and directed
me to texts on public key cryptology. Arch Robinson, however, gets the
prize for the best, clearest, and most helpful answer. First he sent me a
letter explaining a straight-forward way to enumerate the solution set
without running into the combinatoric problems I feared. To wit:
-> Your problem seems rather straightforward to do by brute-force enumeration.
-> The computationaly complexity would be O(M) space and O(NM) time,
-> where N is the number of apartments and M is the maximum possible V.
->
-> Let S be the set of possible V's. Start out with S = {0}. Now consider
-> each Vi in turn. For each v in S, include v+Vi in S. After considering
-> all Vi's, S will contain all possible sums. In pseudo-Pascal, the
-> algorithm would be:
->
-> var S: array [0..M] of boolean; (* representation of set S *)
-> V[1..N] : integer; (* the Vi's *)
->
-> begin
-> S[0] = 1; (* Let S = {0} *)
-> for k=1 to M do S[k] = 0;
->
-> for i=1 to N do (* consider each Vi *)
-> for k=1 to M do (* Look at each element in S *)
-> if S[k] then
-> S[k+V[i]] := true; (* If v in S, include v+Vi in S *)
-> end
->
-> Even a naive implementation like this is probably sufficient for your
-> problem. (Efficient bit-twiddling can probably speed it up by an order
-> of magnitude.) Its probably not too hard to extend this algorithm to
-> figure out what combinations of Vi produced a given sum.
As if that wasn't enough, he sent me a second letter:
-> Your voter problem was sufficiently interesting for me to code my solution
-> to question (1). For 54 random numbers between 300-700, it takes about
-> a second of CPU time on my PC/RT to run. I doubt that you will be able
-> to prove much, however, unless some of the vote totals were rather low
-> or the shares are not distributed randomly. For my random data, all sums
-> above ~920 were possible, and I suspect this is typical.
->
-> You can have the C-source to the program if you want it.
As I side note, I'm a bit peeved that I had to change all my "> "s
to "-> "s to make inews happy. I really think this was a mis-feature. It
doesn't help in the long run (people just learn to 1,$s/^>/->/) and it
seems to have generated a cult practice of "line-counter pacifier lines",
not unlike those dumb line-eater lines. A worthwhile experiment, but, in
my opinion, an experiment that failed.
--
Roy Smith, {allegra,cmcl2,philabs}!phri!roy
System Administrator, Public Health Research Institute
455 First Avenue, New York, NY 10016woods@hao.UUCP (05/30/87)
In article <2732@phri.UUCP> roy@phri.UUCP (Roy Smith) writes: > As I side note, I'm a bit peeved that I had to change all my "> "s >to "-> "s to make inews happy. I really think this was a mis-feature. And I'm peeved that you made OUR SITE pay to RE-transmit an article that all the math people have ALREADY READ. Do you think they are stupid? Is it *really* necessary to quote 20 lines of old article to make a two-line comment on it? I do not. You may be right in saying that having inews enforce a old/new text ratio is the wrong way to go about it, but we have to do SOMETHING to stop the excessive quoting of old articles. As always, the news software writers (read: Rick Adams) are always open to suggestions on how to do it better; without these, complaints are nothing more than yet more useless flames. --Greg -- UUCP: {hplabs, seismo, nbires, noao}!hao!woods CSNET: woods@ncar.csnet ARPA: woods%ncar@CSNET-RELAY.ARPA INTERNET: woods@hao.ucar.edu