|
|
|
|
|
|
| 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;
|
| 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) {
|
|
|
|
|
| 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;
|
| }
|
|
|
