What does Retention Algebra for Book Adaptations conclude, in numbers, about “Submodular Coverage: the Greedy Algebra of Picking Sentences and the 1−1/e Guarantee”?
Answer: Chapter 1 writes sentence selection as submodular coverage maximisation, where greedy selection carries a worst-case guarantee of 0.6321 and salience ranking piles its places onto one topic.
Scope of the numbers: Its parameters are illustrative; all calculations are generated by its programs; it is not legal advice and not personalised business or investment advice. Marked boxes separate published evidence, runnable Python calculations (22 programs), classical sources and the author's hypotheses.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 0.6321
| greedy vs exhaustive optimum, 300 toy monographs | ||||
| 14 sentences, 10 weighted concepts | ||||
| k | mean ratio | worst ratio | greedy hits opt | guarantee |
| 1 | 1.0000 | 1.0000 | 1.0000 | 1.0000 |
| 2 | 0.9906 | 0.8158 | 0.8700 | 0.7500 |
| 3 | 0.9882 | 0.8491 | 0.7733 | 0.7037 |
| 4 | 0.9953 | 0.9149 | 0.8700 | 0.6836 |
| 5 | 0.9995 | 0.9444 | 0.9833 | 0.6723 |
| 6 | 1.0000 | 1.0000 | 1.0000 | 0.6651 |
| limit 1 - 1/e = 0.6321 |
Show the full program
# Chapter 1. p11: greedy sentence selection against the exhaustive optimum.
# A toy monograph has 14 sentences and 10 weighted concepts; each sentence
# covers a random subset of concepts. Coverage value f(S) is the total
# weight of concepts touched by the chosen sentences: monotone and
# submodular. Greedy picks the sentence with the largest marginal gain;
# the optimum is found by enumerating every subset of size k. The bound
# 1 - (1 - 1/k)^k >= 1 - 1/e is the classical guarantee for greedy.
# Weights and coverage probabilities illustrative; seed fixed.
import itertools
import math
import random
rng = random.Random(20261112)
N_SENT, N_CON, TRIALS = 14, 10, 300
def make_book():
w = [rng.randint(1, 9) for _ in range(N_CON)]
cover = []
for _ in range(N_SENT):
c = [j for j in range(N_CON) if rng.random() < 0.22]
if not c:
c = [rng.randrange(N_CON)]
cover.append(frozenset(c))
return w, cover
def value(w, cover, picks):
seen = set()
for i in picks:
seen |= cover[i]
return math.fsum(w[j] for j in sorted(seen))
def greedy(w, cover, k):
picks = []
for _ in range(k):
base = value(w, cover, picks)
best, gain = None, -1.0
for i in range(N_SENT):
if i in picks:
continue
g = value(w, cover, picks + [i]) - base
if g > gain:
best, gain = i, g
picks.append(best)
return value(w, cover, picks)
def optimum(w, cover, k):
return max(value(w, cover, c)
for c in itertools.combinations(range(N_SENT), k))
books = [make_book() for _ in range(TRIALS)]
print("greedy vs exhaustive optimum, {} toy monographs".format(TRIALS))
print("{} sentences, {} weighted concepts".format(N_SENT, N_CON))
print(" k mean ratio worst ratio greedy hits opt guarantee")
for k in range(1, 7):
ratios = []
hits = 0
for w, cover in books:
g, o = greedy(w, cover, k), optimum(w, cover, k)
ratios.append(g / o)
hits += g == o
bound = 1.0 - (1.0 - 1.0 / k) ** k
print("{:2d} {:10.4f} {:11.4f} {:15.4f} {:9.4f}".format(
k, math.fsum(ratios) / TRIALS, min(ratios), hits / TRIALS,
bound))
print("limit 1 - 1/e = {:.4f}".format(1.0 - math.exp(-1.0)))Single source and citation
Fan, Y. (2026). Content Fission Algebra: Compiling Hard-Core Monographs into Two-Host Podcasts, Study Slides and Quiz Banks (Version 1.0.0), Chapter 1: Submodular Coverage: the Greedy Algebra of Picking Sentences and the 1−1/e Guarantee. 5D Library. DOI pending
DOI pending · monograph page goes live after publication · 5DL-B-151 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026151,
author = {Fan, Yafu},
title = {Content Fission Algebra: Compiling Hard-Core Monographs into Two-Host Podcasts, Study Slides and Quiz Banks},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}Other chapter answers in this book
- Chapter 2 · Spoken Compression: Breadth against Repetition, Turn Length and Shannon Naming in a Two-Host Podcast
- Chapter 3 · Visual Card Compression: the Item Ceiling of a Slide, Dynamic Programming over Dependencies, and the Length of a Card
- Chapter 4 · The Pass-or-Retry Quiz Bank: Difficulty and Discrimination, Test Information at the Cut, and the Counter-Intuitive Testing Effect
- Chapter 5 · Spaced Review Scheduling: Optimal Gaps that Grow with the Retention Interval, the Leitner Boxes as an Absorbing Chain, and a Daily Review Cap
- Chapter 6 · The Portfolio Algebra of One Book, Many Products: Production Hours, Fidelity Audits, the Backfire of Excess and the Copyright Red Line
- Chapter 7 · The Classics Examined: Zhu Xi on Following the Order and Reading Thoroughly, and Bacon on Books to be Tasted, Swallowed and Chewed
- Chapter 8 · Practice and Falsification: an Owner's Checklist, a Front-End Style Library and a Pre-Registered Testing Plan