Two years ago when we completed version 1 of The Classics of Science Fiction Short Story list I proposed a math challenge. Version 1 came up with 275 stories. I asked if there was any mathematically way to decide what were the fewest anthologies that contained all 275 stories using ISFDB.org as a reference database. Version 1 was generated using .csv files. Since then we updated the process to a database for version 2 of the list, which produced 101 stories — we believe that was a more practical reading list.
A science fiction fan could read the entire list over the summer by reading one story a day, or in a year by reading one story every three days, but where would they get the 101 science fiction short stories? It might be possible to track down many stories on the internet, but what if people wanted to read them in a printed book? What would be the minimum number of anthologies to buy to get all the stories? That seem like an fascinating mathematical problem to me.
Well, Szymon Szott just came up with a solution using version 2 of the list. The second link goes to GitHub for Szymon’s Python code and documentation. The first link goes to his bio. Even if you can’t read the programming code you should visit this page that explains his solution. Szymon was able to come up with 22 anthologies that collected the 101 stories on the v. 2 of The Classics of Science Fiction Short Stories list.
The photo above pictures eight anthologies that get 81 stories of the version 2 list. Of course, those eight anthologies gets you a lot more than 81 stories. I tried to figure out the solution myself by using a spreadsheet and the best I could do was find fifteen anthologies to cover 81 stories, and then gave up. I figured my eyeballing method might have gotten me to 30-35 anthologies.
Here’s what Szymon says about the project:
As a fan of science fiction and a compulsive completionist, Worlds Without End is one of my favorite sites on the Internet. It was there that I learned about Jim and Mike's work on the list of classic science fiction novels which I've been eagerly following. When the list of classic science fiction short stories was announced and Jim blogged about The Mathematics of Buying Science Fiction Anthologies, I knew this was an interesting problem to solve. But it wasn't until I started dabbling in Python that I realized that, along with the 2020 travel-restricted summer holidays, I now had the tools to start chipping away at this. Creating a story-to-anthology mapping using data from the Internet Speculative Fiction Database didn't take too long, but the underlying mathematical problem was harder than I initially thought: it turned out that a brute-force approach of checking all possible combinations is unfeasible. Still, the heuristic used has given us a solution which I'm satisfied with and I don't think there exists a much better global solution. I was most surprised that the Science Fiction Hall of Fame series did not make the list (as I've already read volume one). Thank you Jim for this challenge! Now, all this coding was fun, but it's time to get back to reading: Sense of Wonder is next!
This isn’t an easy problem. Szymon had to screenscrape the table of contents from 290 anthologies from ISFDB.org, which contained one or more of the 101 stories. Just look at this listing to see how often each of these stories was reprinted. Towards the end of his programming loops, he had to use eight anthologies to cover eight stories. If all those singletons had been in one anthology, Szymon’s finally anthology list would have been 15. Most of those singletons were newer stories and there haven’t been enough time for them to be collected into a retrospective anthology. One new anthology could shorten Szymon’s final list.
I know many people won’t follow links, so here is Szymon’s program results:
Sense of Wonder - "Arena" by Fredric Brown - "Bears Discover Fire" by Terry Bisson - "Black Destroyer" by A. E. van Vogt - "Blood Music" by Greg Bear - "Bloodchild" by Octavia E. Butler - "The Cold Equations" by Tom Godwin - "The Country of the Kind" by Damon Knight - "Day Million" by Frederik Pohl - "First Contact" by Murray Leinster - "Fondly Fahrenheit" by Alfred Bester - "The Game of Rat and Dragon" by Cordwainer Smith - "Hell Is the Absence of God" by Ted Chiang - "Jeffty Is Five" by Harlan Ellison - "The Little Black Bag" by C. M. Kornbluth - "Lobsters" by Charles Stross - "The Lucky Strike" by Kim Stanley Robinson - "A Martian Odyssey" by Stanley G. Weinbaum - "Microcosmic God" by Theodore Sturgeon - "The Mountains of Mourning" by Lois McMaster Bujold - "Nightfall" by Isaac Asimov - "The Only Neat Thing to Do" by James Tiptree, Jr. - "Or All the Seas with Oysters" by Avram Davidson - "Passengers" by Robert Silverberg - "The Persistence of Vision" by John Varley - "Rachel in Love" by Pat Murphy - "A Rose for Ecclesiastes" by Roger Zelazny - "The Sentinel" by Arthur C. Clarke - "Seven American Nights" by Gene Wolfe - "Souls" by Joanna Russ - "Surface Tension" by James Blish - "That Only a Mother" by Judith Merril - "Think Like a Dinosaur" by James Patrick Kelly - "The Ugly Chickens" by Howard Waldrop - "Who Goes There?" by John W. Campbell, Jr. Running story total: 34 The Wesleyan Anthology of Science Fiction - ""Repent, Harlequin!" Said the Ticktockman" by Harlan Ellison - "Air Raid" by John Varley - "All You Zombies—" by Robert A. Heinlein - "And I Awoke and Found Me Here on the Cold Hill's Side" by James Tiptree, Jr. - "Aye, and Gomorrah …" by Samuel R. Delany - "Burning Chrome" by William Gibson - "Coming Attraction" by Fritz Leiber - "Desertion" by Clifford D. Simak - "Nine Lives" by Ursula K. Le Guin - "Speech Sounds" by Octavia E. Butler - "The Star" by H. G. Wells - "There Will Come Soft Rains" by Ray Bradbury - "Thunder and Roses" by Theodore Sturgeon - "We Can Remember It for You Wholesale" by Philip K. Dick - "When It Changed" by Joanna Russ Running story total: 49 Science Fiction: Stories and Contexts - "At the Rialto" by Connie Willis - "Flowers for Algernon" by Daniel Keyes - "For a Breath I Tarry" by Roger Zelazny - "The Girl Who Was Plugged In" by James Tiptree, Jr. - "Mimsy Were the Borogoves" by Henry Kuttner, C. L. Moore - "The Nine Billion Names of God" by Arthur C. Clarke - "Second Variety" by Philip K. Dick - "Story of Your Life" by Ted Chiang - "Vaster Than Empires and More Slow" by Ursula K. Le Guin - "Vintage Season" by Henry Kuttner, C. L. Moore Running story total: 59 The Big Book of Science Fiction: The Ultimate Collection - "Sandkings" by George R. R. Martin - "Snow" by John Crowley - "Swarm" by Bruce Sterling - "The Last Question" by Isaac Asimov - "The Man Who Lost the Sea" by Theodore Sturgeon - "The Star" by Arthur C. Clarke - "The Voices of Time" by J. G. Ballard Running story total: 66 The Science Fiction Hall of Fame, Volume IV - "A Meeting with Medusa" by Arthur C. Clarke - "Born with the Dead" by Robert Silverberg - "Of Mist, and Grass, and Sand" by Vonda N. McIntyre - "The Day Before the Revolution" by Ursula K. Le Guin - "The Death of Doctor Island" by Gene Wolfe - "The Queen of Air and Darkness" by Poul Anderson Running story total: 72 The Very Best of Fantasy & Science Fiction: 60th Anniversary Anthology - "Harrison Bergeron" by Kurt Vonnegut, Jr. - "The Merchant and the Alchemist's Gate" by Ted Chiang - "The Women Men Don't See" by James Tiptree, Jr. Running story total: 75 The Science Fiction Century - "Beggars in Spain" by Nancy Kress - "Fire Watch" by Connie Willis - "Great Work of Time" by John Crowley Running story total: 78 The Best of the Nebulas - "A Boy and His Dog" by Harlan Ellison - "Houston, Houston, Do You Read?" by James Tiptree, Jr. - "Time Considered as a Helix of Semi-Precious Stones" by Samuel R. Delany Running story total: 81 Armageddons - "Inconstant Moon" by Larry Niven - "The Screwfly Solution" by James Tiptree, Jr. Running story total: 83 Survival Printout - "I Have No Mouth, and I Must Scream" by Harlan Ellison - "Scanners Live in Vain" by Cordwainer Smith Running story total: 85 Modern Classic Short Novels of Science Fiction - "Sailing to Byzantium" by Robert Silverberg - "The Star Pit" by Samuel R. Delany Running story total: 87 The Legend Book of Science Fiction - "The Fifth Head of Cerberus" by Gene Wolfe - "The Moon Moth" by Jack Vance Running story total: 89 The Arbor House Treasury of Modern Science Fiction - "Light of Other Days" by Bob Shaw - "The Bicentennial Man" by Isaac Asimov Running story total: 91 The Locus Awards: Thirty Years of the Best in Science Fiction and Fantasy - "Even the Queen" by Connie Willis - "The Way of Cross and Dragon" by George R. R. Martin Running story total: 93 Hugo and Nebula Award Winners from Asimov's Science Fiction - "Press ENTER ■" by John Varley Running story total: 94 The Hugo Winners, Volume Three - "A Song for Lya" by George R. R. Martin Running story total: 95 The Best Science Fiction and Fantasy of the Year Volume Six - "The Man Who Bridged the Mist" by Kij Johnson Running story total: 96 The Best Science Fiction and Fantasy of the Year Volume Five - "The Things" by Peter Watts Running story total: 97 The Year's Best Science Fiction: Fourth Annual Collection - "R & R" by Lucius Shepard Running story total: 98 The Unreal and the Real: The Selected Short Stories of Ursula K. Le Guin - "Buffalo Gals, Won't You Come Out Tonight" by Ursula K. Le Guin Running story total: 99 The New Space Opera 2 - "The Island" by Peter Watts Running story total: 100 The New Hugo Winners, Volume III - "The Last of the Winnebagos" by Connie Willis Running story total: 101 Selected books: - Sense of Wonder - The Wesleyan Anthology of Science Fiction - Science Fiction: Stories and Contexts - The Big Book of Science Fiction: The Ultimate Collection - The Science Fiction Hall of Fame, Volume IV - The Very Best of Fantasy & Science Fiction: 60th Anniversary Anthology - The Science Fiction Century - The Best of the Nebulas - Armageddons - Survival Printout - Modern Classic Short Novels of Science Fiction - The Legend Book of Science Fiction - The Arbor House Treasury of Modern Science Fiction - The Locus Awards: Thirty Years of the Best in Science Fiction and Fantasy - Hugo and Nebula Award Winners from Asimov's Science Fiction - The Hugo Winners, Volume Three - The Best Science Fiction and Fantasy of the Year Volume Six - The Best Science Fiction and Fantasy of the Year Volume Five - The Year's Best Science Fiction: Fourth Annual Collection - The Unreal and the Real: The Selected Short Stories of Ursula K. Le Guin - The New Space Opera 2 - The New Hugo Winners, Volume III Number of selected books: 22
Most of those 22 anthologies are out-of-print and you’ll need to shop ABEbooks.com or eBay.com to find them. I’ve added links to the final 22 anthologies so you can find the various editions of these books that have been published over the years. Clicking on links to individual editions will show you the table of contents and usually a photo of the book’s cover. Some anthologies have been published under multiple titles, and some of those are easier to find used. For Sense of Wonder, I highly recommend getting it in the Kindle edition, the paper edition is much too big to comfortably hold. Ditto for The Big Book of Science Fiction.
If you click on the story title in the Classics of Science Fiction Short Story list it will take you to its entry on ISFDB.org where you can see all the anthologies and collections where it’s been reprinted. This will let you find an alternative source for the story, or even let you try to beat Szymon’s results by coming up with another combination of anthologies.
Update: See The Science Fiction Anthology Problem – Kindle Edition for the solution using ebooks.
James Wallace Harris, 8/9/20
28 thoughts on “The SF Anthology Problem – Solved”
I have a sneaking suspicion that, given all the stragglers at the end, you are not at the minimum number.
Yeah, you can get rid of three anthologies (Locus/Hugo/New Hugo) and replace them with two Willis and Martin retrospective collections. I suspect that’s just the tip of the iceberg.
I told Szymon not to use collections if he couldn’t help it. I wanted anthologies. He did leave the Le Guin collection, but I believe an anthology is available for that story.
I preferred anthologies because it would get readers more great SF stories that didn’t make the v. 2 list. For example, if they thought the 8 cutoff was too strick and picked 7 for the cutoff which would generate 151 stories, having anthologies would give them a better chance of having those stories. For example, here’s the 7 cutoff list:
But here’s your chance Paul, beat the number 22 for the 8-cutoff list. If you do it, post a comment with a listing like Szymon’s if you can.
If you are only interested in the 101 stories you’d want minimum books: minimum anthologies, and reading non-relevant stories is another problem entirely.
Thank you Paul for your comment! I’ve created a branch in the code repository to check for the “true minimum” (including all book types). The best I could come up with is 21 books as you can see at the bottom of this page:
Initially I was also surprised that there are so many singletons. Some of them such as “R & R” don’t share books with other classics. In other cases note that when the algorithm prints for example:
RRM: A RRetrospective
– “A Song for Lya” by George R. R. Martin
Running story total: 101
This means that “A Song for Lya” was the only “new” story that the RRetrospective contributed. This book contains other classics, but they were already added in previous steps (from other books). I tried adding “RRM: A RRetrospective” first, before “Sense of Wonder”, but this didn’t improve the score as did none of my other attempts.
If you can find a collection with less than 21 books, I’d be happy to hear!
Probably too difficult for me to do manually, but if you replace all the single story publications at the end by Martin, Tiptree, and Le Guin (and anyone who also appears earlier in the lists) with their retrospectives, this will knock out some mid-list stories by those writers and you may be able to squeeze the number of mid-list books down by using different combinations.
More simply, you may get better results working two ends into the middle rather than from one end to the other (if, indeed, that is what your program does). How you program that I have no idea. I suspect you keep your first two or three books, then prioritise the loners as “anchors” before starting the far end reduction run.
This probably demonstrates my complete ignorance of what you’ve done (I only skimmed) and won’t work, but I’ve typed it out now, so what the hell 🙂
Paul, did you see the solution found using an integer programming solver by S? I ran it for the complete book set to find the true minimum (including author collections) and it is 20 books:
Looking through the list there are 36 of the stories that I am sure I have read, and maybe a dozen or so more that I might have, but can’t be certain (the titles are generic enough that I have some doubt.)
And I consider myself something of a short story fan. It’s sobering to think of how much is out there.
In recent years I’ve switched from reading SF novels to SF short stories. I feel I get more science fiction that way.
I’ve switched to writing short fiction these days. I’d like to read more, but most of my pleasure reading is by audiobook these days and short story anthologies tend not to be made in audio, I’ve found.
Thanks for sharing this. This is really, really cool, and a lot of fun.
This is fun. I haven’t followed all the details, but this is a typical set-cover problem, and least using the data from main.csv in the master branch of the SzymonSzott/science-fiction-anthology-problem repo on GitHub, one finds that the optimal solution involves 21 books:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
hosted with ❤ by GitHub
This was found by a program that takes less than a tenth of a second, based on the first search result for “integer programming solver” (which was Google OR-Tools). If I’ve understood the problem correctly, I can try writing this up in more detail if anyone’s interested, but I basically used the formulation from the Wikipedia article on Set cover problem. With such a solver one can also find answers to lots of other questions like the most stories one can get using a set of anthologies without overlap, or weighting by cost to find the minimum-cost set, etc.
LikeLiked by 1 person
Thanks, this is great! Can you share your code? No problem if its raw — I’d really like to learn how to use such a solver in a practical setting.
LikeLiked by 1 person
Sure! Following your lead I wrote it up as a notebook though it’s quite raw — I don’t know anything about pandas etc, so it’s possible I’ve done things in a very unsophisticated way or misunderstood something. See the “Solving the integer program” section for the solver:
Look forward to interesting variants being solved optimally 🙂
And it looks like I’ve read just under 20 of these 101 stories, so I have some reading to do 🙂
LikeLiked by 1 person
Okay, first some facts:
I’ve been reading SF for the last 45 years, both short stories and “normal” novels.
I’m from Vienna and in that city there were 2 or 3 good bookshops that had english literature. Living now for the past 30 years in Germany that turned out to be a downfall.
I think, that about 70% of SF isn’t translated, but you don’t get the original english.
With WWW things changed, but my personal problem is: i have to touch a book, read a short overview. So i tend to stay with the “big” names.
Of that list i’ve read about 40, but i’m not sure, as the german titles are quite different.
Nevertheless this list gave me some perspective of what to read the following months (maybe years🤔🤓).
Thank you for your work and keep it up !😜😇