# Finding the best combination of sets that gives the maximum number of unique items

A couple of months ago I went to a Bruce Springsteen concert. I hadn't heard much of his songs before that, but really liked the concert and bought the live recording of it afterwards (which he sells via live.brucespringsteen.net). A bit later I even bought another live recording of a different concert and after listening to them on repeat I'm liking his music more and more. I like it in fact so much that I want to buy more of his live recordings... and this is where I ran into my problem: he has a lot of recordings!

So now as a developer I want to write an piece of code that will give me the minimum/optimum numbers of recordings to buy that will give me a maximum number of different songs with the least duplicates (taking into account the 2 recordings I already have).

I could brute force it of course, but I'm hoping that there is some algorithm or library that could help me determine the correct set of recordings to buy? Scraping the set lists from the site is the easy part.

I've already tried searching for algorithms and it looks like it might be some sort of Cover Set Problem, which would make it NP-complete, which is a problem, but I'm not looking for a combination that gives me all different songs, just which x recordings to buy additionally to get the best amount of different songs in total (song length doesn't matter).

Clarification: as Doc Brown points out I need to be even more specific. I'd like to know which recordings to buy that give me the most, but not all, songs, with a fixed maximum of duplicates.

Possibility? After thinking about this some more I'm starting to wonder if maybe Genetic Programming can be applied to this? You could start off with a population of randomly generated individuals (combinations of recordings) and then applying a fitness function that gives a score based on the amount of unique songs, duplicates & total recordings needed. After enough generations this could also maybe give a good approximation?

• I guess you will have to decide first if you want either all songs with the minimum number of duplicates, or as many songs as possible with a fixed maximum number of duplicates.Otherwise your optimization goal is not clear. – Doc Brown Aug 2 '16 at 10:52
• @DocBrown all songs, certainly in the case Bruce's oeuvre seems to be impossible (even though his set list varies a lot per concert), so my goal is to have as many songs with a fixed maximum of duplicates. – fimez Aug 2 '16 at 11:38

You can use genetic algorithms with a simple binary representation for the individuals:

``````individual = 01010100000111000011010111001110
``````

Every locus of an individual is related to the recordings of a specific show. If:

``````individual[k] == 1
``````

then you're going to buy the `k-th` album.

You should code two / three functions:

``````unique_songs(individual) = number of unique songs

duplicates(individual) = number of duplicates

cost(individual) = total purchase cost
``````

The fitness function is something like:

``````fitness(individual) =        unique_songs(individual)
- k1 *   duplicates(individual)
- k2 *         cost(individual)
``````

`k1` / `k2` have to be tuned. This will treat `duplicates(individual)` as a soft constraint.

If you want as many songs as possible with a fixed maximum number of duplicates (`limit`) you need a hard constraint. The simplest approach is changing the fitness from a scalar value to a bi-dimensional vector:

``````fitness(individual) = [-penalty(individual),
unique_songs(individual) - k * cost(individual)]

/ duplicates(individual) - limit   constraint not satisfied
penalty(individual) = {
\ 0                                otherwise
``````

For further details about this approach you can read An Efficient Constraint Handling Method for Genetic Algorithms - Kalyanmoy Deb.

You can use the same library / framework, just change the fitness comparison operator to a lexicographic comparison function.

• Thank you. This looks like a great approach. I just finished the code that can scrape the set lists so that I have the necessary data to start on the Genetic Algorithm part. I think I might try to use Jenetics for that. – fimez Aug 2 '16 at 21:21
• Finally got the data into Jenetics and implemented a fitness function and started playing around with the parameters and the first results are encouraging. Will have to do some additional fiddling, but it looks promising enough for me to mark this as the answer. Thank you and also the other people that answered and gave great alternative options. – fimez Aug 6 '16 at 22:39

Simulated annealing is a technique that is useful for generating approximate results for computationally difficult problems where it is easy to determine if one potential solution is better than another.

At its simplest, you pick a random solution and generate a small change (eg swapping one recording for another) and see whether this has got you closer to your result. If it has, you keep the new solution and repeat. If it hasn't, you have a random chance of accepting the change anyway. The process is governed by a "temperature" variable that decreases as you approach your iteration limit; the chance of accepting a change that is less optimal reduces as the temperature decreases. As well as tracking the current solution you also track the best ever solution.

For many problem types, this approach usually converges to a reasonable approximation of the best solution.

• This, together with the distance approach JimmyJames put in his answer, is what I was basically doing by hand yesterday before I got tired of it and thought "dude, you're a developer, why aren't you solving this by code"! It did however give me something to compare the result that the code produces against. I'm first going to try the Genetic Algorithm approach described by manlio, but if that doesn't work for me I'm switching to your and JimmyJames's approach. – fimez Aug 2 '16 at 21:30

This looks like a variation of the Knapsack problem for me. I solved the problem with the Jenetics GA library:

``````import static java.util.Objects.requireNonNull;

import java.util.function.Function;
import java.util.stream.Collectors;

import org.jenetics.BitGene;
import org.jenetics.engine.Codec;
import org.jenetics.engine.Engine;
import org.jenetics.engine.EvolutionResult;
import org.jenetics.engine.Problem;
import org.jenetics.engine.codecs;
import org.jenetics.util.ISeq;

public class Springsteen
implements Problem<ISeq<Springsteen.Record>, BitGene, Double>
{

public static final class Record {
final String name;
final double price;
final ISeq<String> songs;

public Record(
final String name,
final double price,
final ISeq<String> songs
) {
this.name = requireNonNull(name);
this.price = price;
this.songs = requireNonNull(songs);
}
}

private final ISeq<Record> _records;
private final double _maxPricePerUniqueSong;

public Springsteen(final ISeq<Record> records, final double maxPricePerUniqueSong) {
_records = requireNonNull(records);
_maxPricePerUniqueSong = maxPricePerUniqueSong;
}

@Override
public Function<ISeq<Record>, Double> fitness() {
return records -> {
final double cost = records.stream()
.mapToDouble(r -> r.price)
.sum();

final int uniqueSongCount = records.stream()
.flatMap(r -> r.songs.stream())
.collect(Collectors.toSet())
.size();

final double pricePerUniqueSong = cost/uniqueSongCount;

return pricePerUniqueSong <= _maxPricePerUniqueSong
? uniqueSongCount
: 0.0;
};
}

@Override
public Codec<ISeq<Record>, BitGene> codec() {
return codecs.ofSubSet(_records);
}

public static void main(final String[] args) {
final double maxPricePerUniqueSong = 2.5;

final Springsteen springsteen = new Springsteen(
ISeq.of(
new Record("Record1", 25, ISeq.of("Song1", "Song2", "Song3", "Song4", "Song5", "Song6")),
new Record("Record2", 15, ISeq.of("Song2", "Song3", "Song4", "Song5", "Song6", "Song7")),
new Record("Record3", 35, ISeq.of("Song5", "Song6", "Song7", "Song8", "Song9", "Song10")),
new Record("Record4", 17, ISeq.of("Song9", "Song10", "Song12", "Song4", "Song13", "Song14")),
new Record("Record5", 29, ISeq.of("Song1", "Song2", "Song13", "Song14", "Song15", "Song16")),
new Record("Record6", 5, ISeq.of("Song18", "Song20", "Song30", "Song40"))
),
maxPricePerUniqueSong
);

final Engine<BitGene, Double> engine = Engine.builder(springsteen)
.build();

final ISeq<Record> result = springsteen.codec().decoder().apply(
engine.stream()
.limit(10)
.collect(EvolutionResult.toBestGenotype())
);

final double cost = result.stream()
.mapToDouble(r -> r.price)
.sum();

final int uniqueSongCount = result.stream()
.flatMap(r -> r.songs.stream())
.collect(Collectors.toSet())
.size();

final double pricePerUniqueSong = cost/uniqueSongCount;

System.out.println("Overall cost:  " + cost);
System.out.println("Unique songs:  " + uniqueSongCount);
System.out.println("Cost per song: " + (cost/uniqueSongCount));
System.out.println("Records:       " + result.map(r -> r.name).toString(", "));

}
}
``````

The fitness function is simple the number of unique songs, restricted by the maximal price per song, which you are willing to pay. Running the code will print the following output:

``````Overall cost:  37.0
Unique songs:  15
Cost per song: 2.466666666666667
Records:       Record2, Record4, Record6
``````
• I've been trying this out, but it doesn't quite do what I want. Against the scraped setlists of the shows I seem to be getting way too much shows in the result, even when lowering the max cost per song. The result I'm trying to achieve is to know which e.g. 5 shows I'd need to buy to have the most unique songs. I don'y need to have all songs, just the best combination of a fixed amount of shows that will give me the best mix of unique songs. An example of the output against the scraped setlists: gist.github.com/planetsizebrain/… – fimez Aug 9 '16 at 19:28
• I think there is still room for improving the fitness function. E.g. you can define a limit for the overall cost. But in the end, you have to formalize the " I don'y need to have all songs". – Franz Wilhelmstötter Aug 9 '16 at 22:13
• That's what I'm trying to do, in the code I already had and now in yours, by returning 0 when the number of records is bigger than a certain number, e.g. 5. In my version, after twiddling a lot with the parameters of the engine builder this seems to work and gives me a 'Best Genotype' that has the asked amount of records, but when adding this record limit to the code your provided this still gives me a 'Best Genotype' in the end that has a whole lot more records, usually even 45 or more. – fimez Aug 9 '16 at 22:55

If you have a limit to the number of albums you are willing to buy and that number is not large, I think there's a pretty straightforward approach. First you want to create a distance function between one set and another. At the simplest level, it's the count of songs that are not in both sets. You say you want to limit the number of duplicates but I question that since it could also limit the number of different songs you end up with. For example, if one recording has all new songs except one that you already have a bunch of times, you would reject it and possibly choose an album with very few new songs. Given the artist, I imagine a few songs (e.g. "Born in the USA", "Born to Run", "Born ...") are going to show up very often if not in every recording.

Once you have that calculation. You take your two recordings and combine them into one set. Calculate the distance of that set and every other recording. Then take those sets and repeat until you reach the max number recordings you are willing to buy.

That could be really costly if you are willing to buy a lot of recordings and I'm not sure how many there are but it sounds like a bunch. If that will take too long, you could cull the starting sets based on their score for each iteration. It's not guaranteed that you will get the best result this way but it's likely to be pretty close.

Here's an example to demonstrate why you might not want to set a hard limit on duplicates:

Let's say your starting set is:

``````Apple
Banana
Carrot
Durian
``````

And you have the following 4 sets to choose from.

``````Apple       Apple        Banana  Carrot
Escarole    Horseradish  Durian  Escarole
Fig         Jalapeno
Grapefruit  Kale
Lemon
``````

And you want to select the best 2 sets from those four to add to your set. Here are the 6 options:

`````` 1 & 2          1 & 3     1 & 4
Apple       3  Apple  2  Apple    2
Banana      1  Banana 2  Banana   2
Carrot      1  Carrot 1  Carrot   2
Durian      1  Durian 2  Durian   1
Escarole    1            Escarole 1
Fig         1
Grapefruit  1
Jalapeno    1
Kale        1
Lemon       1

2 & 3          2 & 4          3 & 4
Apple       2  Apple       2  Apple    1
Banana      2  Banana      1  Banana   2
Carrot      1  Carrot      2  Carrot   2
Durian      2  Durian      1  Durian   2
Jalapeno    1  Jalapeno    1
Kale        1  Kale        1
Lemon       1  Lemon       1
Escarole    1
``````

Now let's say you started with the rule that no item could be repeated more than twice. This would exclude the the option of 1 & 2. I would say that excludes the best option since it provides the largest number of unique items.

Obviously this is a contrived example but as you get lots of sets where the same values appear often, this situation becomes more likely.

• I don't want to completely eliminate duplicates, but I'd like to have the least possible, but maximizing the amount of unique songs of course outweighs a couple of dupes. Luckily a manual scan shows that The Boss has a habit of really changing the set list between shows which frequently gives 8 or more different songs on a set list of +/- 30. – fimez Aug 2 '16 at 21:26
• @fimez My point here is that minimizing the number of duplicates doesn't maximize the number of unique items. I'll update my answer with an example to demonstrate. – JimmyJames Aug 2 '16 at 21:29
• I get your point with the example. I think it should be a weighted value so that it is counted, but to a lesser extend than the amount of unique songs. Thank you for providing the written out example. – fimez Aug 3 '16 at 7:36
• I'm thinking about this in the context of economics and there are likely diminishing returns in this problem You can use the process I suggested and cull everything but the sets that provide the most new songs. Then you repeat this process until there is no new recording that adds more than N new songs (marginal return). If you are willing to buy a fair number of recordings, I think this is will get you a pretty good result. My guess is that there's at least one song that will be in every set and if you limit the number of duplicates, it will be same as limiting the number of recordings. – JimmyJames Aug 3 '16 at 13:13