For Inspiration:
This is a simple proof of concept to find the minimal number of sets to cover these 3-number-sequences using Cartesian product blocks.
It checks all possible subsets of the input to identify those that form complete Cartesian blocks, then recursively searches for minimal sets of such blocks that cover the entire input.
The approach is brute-force and not optimized:
from itertools import combinations, product
from collections import defaultdict
input_combinations = {
(1, 3, 5),
(1, 4, 5),
(1, 8, 5),
(2, 4, 5),
(3, 4, 5),
(2, 4, 7)
}
# Check if a set of tuples forms a Cartesian product
def is_cartesian_block(subset):
zipped = list(zip(*subset))
candidate = tuple(set(z) for z in zipped)
generated = set(product(*candidate))
return generated == set(subset), candidate
# Find all possible Cartesian blocks within a set of combinations
def find_all_blocks(combos):
all_blocks = []
combos = list(combos)
for r in range(1, len(combos)+1):
for subset in combinations(combos, r):
ok, block = is_cartesian_block(subset)
if ok:
all_blocks.append((block, set(subset)))
return all_blocks
# Recursive search for all minimal covers
def search(combos, blocks, current=[], results=[]):
if not combos:
normalized = frozenset(frozenset(map(frozenset, block)) for block in current)
if not results or len(current) < len(results[0][0]):
results.clear()
results.append((current, normalized))
elif len(current) == len(results[0][0]):
if normalized not in {n for _, n in results}:
results.append((current, normalized))
return
for block, covered in blocks:
if covered <= combos:
search(combos - covered, blocks, current + [block], results)
def find_all_minimal_decompositions(input_combinations):
all_blocks = find_all_blocks(input_combinations)
results = []
search(set(input_combinations), all_blocks, [], results)
return [sol for sol, _ in results]
solutions = find_all_minimal_decompositions(input_combinations)
for i, sol in enumerate(solutions, 1):
print(f"Solution {i}:")
for row in sol:
print(f" {row}")
Output:
What was/is your use case?
Solution 1:
({2}, {4}, {7})
({2, 3}, {4}, {5})
({1}, {8, 3, 4}, {5})
Solution 2:
({2}, {4}, {7})
({1}, {8, 3}, {5})
({1, 2, 3}, {4}, {5})
Solution 3:
({3}, {4}, {5})
({2}, {4}, {5, 7})
({1}, {8, 3, 4}, {5})
Solution 4:
({2}, {4}, {5, 7})
({1}, {8, 3}, {5})
({1, 3}, {4}, {5})
