Feature/longest increasing subsequence #7
Conversation
Add .clang-format configuration file (requires version >3.5.0). Conflicts: test/Jamfile.v2
…onal argument. Rename variables.
…ining the return type (a collection of values or a collection of iterators).
A) with two iterators B) with a range C) with two pointers D) using object methods directly with case A. 1) output iterator 2) vector of values (with value_output_tag as argument) 3) vector of iterators (with iterator_output_tag as argument)
|
@mclow what do you think about this pull request? I think, these functions are very-very useful. We should add it to Boost.Algorithm. |
|
I know this pull request is a bit old, but I had to compute the length longest non-decreasing subsequence of a sequence at some point (to compute the measure of presortedness Rem), which is notably one of the features proposed here, so I'm willing to share some thoughts about implementation details:
Now I'm not sure whether these improvements are useful since they are limited to the computation of the size of a longest increasing subsequence (I haven't try to compute the subsequence itself), which is rather specific, but it can be done to make the current proposed implementation more powerful if needed :) |
|
@Morwenn, that looks like nice optimizations for Anyway, I don't really work on this kind of things now and I don't have much time to work on this PR, so I let anyone interested hijack the authorship of this PR and continue the work. |
A new algorithm: longest increasing subsequence that permits as well to find the longest decreasing/non-increasing/non-decreasing or differently ordered subsequence by defining comparison predicate. I have added tests for it using iterators, ranges, pointers and object's
operator().There are 2 functionalities actually: computing length (function
longest_increasing_subsequence_lengthor methodlongest_increasing_subsequence::compute_length) and retrieving the subsequence (functionlongest_increasing_subsequence_searchorlongest_increasing_subsequence::operator()).There is also a creator function
make_longest_increasing_subsequence.There are 3 possibilities to retrieve the subsequence:
The two latter variants are chosen by giving a corresponding tag as an argument.
Documentation will come soon.