osepedro / trinities

Trinities

Problem Statement

Given n finite, disjoint sets with cardinalities c = [c_1, …​, c_n], form the largest possible set T of triplets by selecting elements from the sets without replacement. A triplet may not contain multiple elements from the same set. What’s the cardinality of T?

Naive Attempt

Phase

A sequence of consecutive removals of triplets from three sets.

The naivePhases function in app/Main.hs is an obvious, but incorrect, attempt at a solution. The idea is to:

1. identify the biggest three sets X, Y & Z (the choice doesn’t matter if there are multiple options);

2. remove min(|X|, |Y|, |Z|) triplets from these sets;

3. repeat until there are no triplets left.

This algorithm underestimates some cases though, e.g. if sets A, B, C and D have cardinalities 26, 26, 31 and 4, then naivePhases only manages to remove 26 triplets, i.e.

countTriplets (naivePhases $ mkProblem [26,26,31,4]) == 26

But you can form 28 triplets as follows:

Phase No.	|A|	|B|	|C|	|D|	|T|
0	26	26	31	4	0
1	2	2	7	4	24
2	0	2	5	2	26
3	0	0	3	0	28

Better Attempt

We can achieve better results by only removing one triplet from the biggest three sets. The betterPhases function does this, and it removes 28 triplets in the [26,26,31,4] case.

Functionality

The main function does the following:

1. Tests betterPhases on randomly generated problems, and prints all identified failures and improvements.

2. Loads the example problems from data/TrinitySnapshotTest-12_20-12_22.csv, evaluates them using naivePhases and betterPhases, and prints all identified failures and improvements.

Failure

a case where a *Phases function performs worse than a known lower bound (e.g. a lower bound specified in the file).

Improvement

a case where it performs better.

Failures and improvements are printed as a CSV table, in which each phase is specified with the notation n × (i,j,k), meaning: remove n triplets from sets i, j and k. If a *Phases function produces no failures on a given set of problems, nothing is printed. The same goes for improvements.

Results

• naivePhases:

  1. Matches the example-problem triplet counts.

  2. Fails hundreds of the randomly generated problems (see Building & Running).

• betterPhases:

  1. Produces no failures and several improvements on the example problems, shown in data/Improvements.csv.

  2. Matches the triplet counts on the randomly generated problems.

Building & Running

Build and run by executing the following in the root directory:

stack run

To call functions directly, load GHCi in the root directory with:

stack ghci

To view the naivePhases failures on the randomly-generated problems, run

testPhases "naivePhases" naivePhases

in GHCi.