Longest increasing subsequence: Difference between revisions
Added 2 C# implementations
No edit summary |
(Added 2 C# implementations) |
||
Line 288:
<pre>2, 4, 5,
0, 2, 6, 9, 11, 15, </pre>
=={{header|C sharp}}==
===Recursive===
{{works with|C sharp|6}}
<lang csharp>using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
public static class LIS
{
public static IEnumerable<T> FindRec<T>(IList<T> values, IComparer<T> comparer = null) =>
values == null ? throw new ArgumentNullException() :
FindRecImpl(values, Sequence<T>.Empty, 0, comparer ?? Comparer<T>.Default).Reverse();
private static Sequence<T> FindRecImpl<T>(IList<T> values, Sequence<T> current, int index, IComparer<T> comparer) {
if (index == values.Count) return current;
if (current.Length > 0 && comparer.Compare(values[index], current.Value) <= 0)
return FindRecImpl(values, current, index + 1, comparer);
return Max(
FindRecImpl(values, current, index + 1, comparer),
FindRecImpl(values, current + values[index], index + 1, comparer)
);
}
private static Sequence<T> Max<T>(Sequence<T> a, Sequence<T> b) => a.Length < b.Length ? b : a;
class Sequence<T> : IEnumerable<T>
{
public static readonly Sequence<T> Empty = new Sequence<T>(default(T), null);
public Sequence(T value, Sequence<T> tail)
{
Value = value;
Tail = tail;
Length = tail == null ? 0 : tail.Length + 1;
}
public T Value { get; }
public Sequence<T> Tail { get; }
public int Length { get; }
public static Sequence<T> operator +(Sequence<T> s, T value) => new Sequence<T>(value, s);
public IEnumerator<T> GetEnumerator()
{
for (var s = this; s.Length > 0; s = s.Tail) yield return s.Value;
}
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
}</lang>
===Patience sorting===
{{works with|C sharp|7}}
<lang csharp>public static class LIS
{
public static T[] Find<T>(IList<T> values, IComparer<T> comparer = null) {
if (values == null) throw new NullReferenceException();
if (comparer == null) comparer = Comparer<T>.Default;
var pileTops = new List<T>();
var pileAssignments = new int[values.Count];
for (int i = 0; i < values.Count; i++) {
T element = values[i];
int pile = pileTops.BinarySearch(element, comparer);
if (pile < 0) pile = ~pile;
if (pile == pileTops.Count) pileTops.Add(element);
else pileTops[pile] = element;
pileAssignments[i] = pile;
}
T[] result = new T[pileTops.Count];
for (int i = pileAssignments.Length - 1, p = pileTops.Count - 1; p >= 0; i--) {
if (pileAssignments[i] == p) result[p--] = values[i];
}
return result;
}
}</lang>
=={{header|Clojure}}==
| |||