File size: 2,535 Bytes
1cdfc83 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 | // Erdos-Straus DSS Greedy Sequence — Core Engine
// Computes the greedy sequence and provides DSS oracle operations.
export function isDSS(set) {
const n = set.length;
const sumsByCard = new Map();
const subsets = allSubsets(set);
for (const sub of subsets) {
const s = sub.reduce((a, b) => a + b, 0);
const card = sub.length;
if (!sumsByCard.has(s)) {
sumsByCard.set(s, card);
} else if (sumsByCard.get(s) !== card) {
return false;
}
}
return true;
}
function allSubsets(arr) {
const result = [];
const n = arr.length;
for (let mask = 1; mask < (1 << n); mask++) {
const sub = [];
for (let i = 0; i < n; i++) {
if (mask & (1 << i)) sub.push(arr[i]);
}
result.push(sub);
}
return result;
}
export function computeGreedySequence(k) {
const seq = [1];
for (let i = 1; i < k; i++) {
let x = seq[seq.length - 1] + 1;
while (true) {
const candidate = [...seq, x];
if (isDSS(candidate)) {
seq.push(x);
break;
}
x++;
}
}
return seq;
}
export function verifyQuadraticBound(seq) {
const results = [];
for (let k = 0; k < seq.length; k++) {
const kk = k + 1; // 1-indexed
const bound = Math.floor((kk * kk + 1) / 2);
const actual = seq[k];
results.push({
k: kk,
greedy: actual,
bound,
holds: actual >= bound,
ratio: (actual / bound).toFixed(3)
});
}
return results;
}
export function sumToCardinality(weights, observedSum) {
const n = weights.length;
for (let mask = 1; mask < (1 << n); mask++) {
let s = 0;
let card = 0;
for (let i = 0; i < n; i++) {
if (mask & (1 << i)) {
s += weights[i];
card++;
}
}
if (s === observedSum) return card;
}
return -1;
}
export function cardinalityFromSum(weights, observedSum) {
// DSS guarantees: from the sum alone, determine how many elements contributed.
// This is O(1) lookup after precomputation.
const table = buildCardinalityTable(weights);
return table.get(observedSum) ?? -1;
}
export function buildCardinalityTable(weights) {
const table = new Map();
const n = weights.length;
for (let mask = 1; mask < (1 << n); mask++) {
let s = 0;
let card = 0;
for (let i = 0; i < n; i++) {
if (mask & (1 << i)) {
s += weights[i];
card++;
}
}
table.set(s, card);
}
return table;
}
|