Detect Maxima Using Persistent HomologyDetect Maxima Using Persistent Homology

code-golf

Inspired by this SO answer about peak detection.

Background

Persistent homology is a fancy term for a fancy math concept, but in this case all we care about is how it can be used for peak detection. In the case of a 1-dimensional array we can describe the algorithm as follows:

We are given an array as input. We begin by sorting it, while maintaining references to the original indices for each value. We also create some kind of data structure to group points together into peaks. We then loop over each point in the sorted array. For each point we have three cases:

• If it is not adjacent to any points in existing groups, a new group is created with a "position" of the point's original index and given a "birth time" equal to that point's value.
• If it is adjacent to one point that is in a group, it is added to said group.
• If it is adjacent to two points in different groups, the younger group is given a "death time" equal to that point's value, and all its points are given to the older group.

At the end, the single group which remains is given a death time of the final value. Now we have a list of groups, each of which have a position that corresponds to a local maximum, and a persistence which is equal to their "birth time" minus their "death time".

The challenge

Given a 1-dimensional sequence of inputs which support comparison and subtraction, and an integer \$n \geq 1\$, your task is to output the indices of the \$n\$ most persisent peaks, sorted by their persistence.

Your program does not need to follow the algorithm exactly as I've described it, nor does it need to be as efficient. You only need to support one class of inputs for the sequence (ie. integers, floats, etc.) and any reasonable format for I/O is allowed so long as it is consistent. You may assume that \$n\$ is less than or equal to the number of local maxima.

In the case that two local maxima to be merged have the same "birth time", the behavior for which one persists is undefined, and either is considered valid for this challenge. In the case that two or more maxima have the same persistence, they may appear in any order in the output.

This is code-golf, so the shortest answer in bytes wins.

Test Cases

Outputs here are 0-indexed.

[1, 2, 1, 2, 3, 2, 1, 2, 3, 4, 3, 2, 1]
2
->
[9, 4]

[1, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 6, 7, 6, 5, 4, 3, 4, 5, 6, 5, 4, 5, 4, 3, 2, 1]
3
->
[7, 19, 12]

[93, 92, 89, 88, 89, 88, 87, 87, 88, 88, 90, 89, 88, 87, 86, 90, 89, 89, 88, 88, 86, 82, 76, 69, 61, 52, 44, 38, 33, 30, 27, 24, 22, 21, 18, 15, 10, 6, 2, 0, 0, 2, 2, 1, 2, 5, 8, 10, 13, 16]
4
->
[0, 49, 15, 10]

More information can be found on wikipedia and this more detailed write-up by the author of the SO answer.

Questions:

• Is my explanation clear, should it be shortened/lengthened?
• Are there any weird edge case test cases I should add?