/Trinities

Primary LanguageHaskellBSD 3-Clause "New" or "Revised" LicenseBSD-3-Clause

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.