Generating subsets three ways

import random
from itertools import combinations

from bundles import unique_bundles


def trusted(items):
    """The answer the tests trust: every combination of entries, sorted, repeats dropped, then sorted."""
    return [list(t) for t in sorted({tuple(sorted(c)) for k in range(len(items) + 1) for c in combinations(items, k)})]


def test_prompt_example():
    """the example of the prompt: two pens and a cap"""
    assert unique_bundles(["pen", "cap", "pen"]) == [[], ["cap"], ["cap", "pen"], ["cap", "pen", "pen"], ["pen"], ["pen", "pen"]]


def test_all_different():
    """three different things give all 8 bundles, in sorted order"""
    assert unique_bundles(["b", "a", "c"]) == [[], ["a"], ["a", "b"], ["a", "b", "c"], ["a", "c"], ["b"], ["b", "c"], ["c"]]


def test_one_value_repeated():
    """three copies of one value: only 4 distinct bundles"""
    assert unique_bundles([7, 7, 7]) == [[], [7], [7, 7], [7, 7, 7]]


def test_empty():
    """no items: one bundle, the empty one"""
    assert unique_bundles([]) == [[]]


def test_numbers_in_numeric_order():
    """integers are sorted as numbers: 9 comes before 10"""
    assert unique_bundles([10, 9, 10]) == [[], [9], [9, 10], [9, 10, 10], [10], [10, 10]]


def test_bundles_are_separate_lists():
    """changing one returned bundle changes no other, and items is left as it was"""
    items = ["pen", "cap", "pen"]
    found = unique_bundles(items)
    found[1].append("ink")
    assert found[2:] == [["cap", "pen"], ["cap", "pen", "pen"], ["pen"], ["pen", "pen"]]
    assert items == ["pen", "cap", "pen"]


def test_sixteen_entries_four_values():
    """4 values, 4 copies each: 65,536 ways to pick entries, 625 distinct bundles"""
    items = [v for v in ["ink", "cap", "pen", "nib"] for _ in range(4)]
    found = unique_bundles(items)
    assert len(found) == 625
    assert found == trusted(items)


def test_random_lists():
    """300 random lists with many repeats, checked against every combination"""
    rng = random.Random(21)
    for _ in range(300):
        items = [rng.randint(1, 4) for _ in range(rng.randint(0, 9))]
        assert unique_bundles(items) == trusted(items), items

import { test, assert } from 'mysmartcopilot:test';
import { uniqueBundles } from './bundles.mjs';

let seed = 21;
const random = () => (seed = (seed * 48271) % 2147483647) / 2147483647;
const randInt = (lo, hi) => lo + Math.floor(random() * (hi - lo + 1));
const less = (a, b) => (a < b ? -1 : a > b ? 1 : 0);
/** Compares two sorted bundles item by item: a bundle comes before every bundle that extends it. */
function compareBundles(a, b) {
  for (let i = 0; i < Math.min(a.length, b.length); i++) if (a[i] !== b[i]) return less(a[i], b[i]);
  return a.length - b.length;
}

/** The answer the tests trust: every pick of entries by bitmask, sorted, repeats dropped, then sorted. */
function trusted(items) {
  const seen = new Map();
  for (let m = 0; m < 2 ** items.length; m++) {
    const bundle = items.filter((_, i) => Math.floor(m / 2 ** i) % 2 === 1).sort(less);
    seen.set(JSON.stringify(bundle), bundle);
  }
  return [...seen.values()].sort(compareBundles);
}

test('the example of the prompt: two pens and a cap', () => {
  assert.deepEqual(uniqueBundles(['pen', 'cap', 'pen']), [[], ['cap'], ['cap', 'pen'], ['cap', 'pen', 'pen'], ['pen'], ['pen', 'pen']]);
});

test('three different things give all 8 bundles, in sorted order', () => {
  assert.deepEqual(uniqueBundles(['b', 'a', 'c']), [[], ['a'], ['a', 'b'], ['a', 'b', 'c'], ['a', 'c'], ['b'], ['b', 'c'], ['c']]);
});

test('three copies of one value give 4 bundles; no items give one, the empty one', () => {
  assert.deepEqual(uniqueBundles([7, 7, 7]), [[], [7], [7, 7], [7, 7, 7]]);
  assert.deepEqual(uniqueBundles([]), [[]]);
});

test('numbers are sorted as numbers, not as text: 9 comes before 10', () => {
  assert.deepEqual(uniqueBundles([10, 9, 10]), [[], [9], [9, 10], [9, 10, 10], [10], [10, 10]]);
});

test('changing one returned bundle changes no other, and items is left as it was', () => {
  const items = ['pen', 'cap', 'pen'];
  const found = uniqueBundles(items);
  found[1].push('ink');
  assert.deepEqual(found.slice(2), [['cap', 'pen'], ['cap', 'pen', 'pen'], ['pen'], ['pen', 'pen']]);
  assert.deepEqual(items, ['pen', 'cap', 'pen']);
});

test('4 values, 4 copies each: 65,536 ways to pick entries, 625 distinct bundles', () => {
  const items = ['ink', 'cap', 'pen', 'nib'].flatMap((v) => [v, v, v, v]);
  const found = uniqueBundles(items);
  assert.equal(found.length, 625);
  assert.deepEqual(found, trusted(items));
});

test('300 random lists with many repeats, checked against every pick of entries', () => {
  for (let trial = 0; trial < 300; trial++) {
    const items = Array.from({ length: randInt(0, 9) }, () => randInt(1, 4));
    assert.deepEqual(uniqueBundles(items), trusted(items), JSON.stringify(items));
  }
});