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
kmean ratioworst ratiogreedy hits optguarantee
11.00001.00001.00001.0000
20.99060.81580.87000.7500
30.98820.84910.77330.7037
40.99530.91490.87000.6836
50.99950.94440.98330.6723
61.00001.00001.00000.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