Longest increasing subsequence: Difference between revisions

Content added Content deleted
m (→‎{{header|Perl 6}}: fix markup)
(Scala contribution maintained.)
Line 1,944: Line 1,944:
<pre>[2, 4, 5]
<pre>[2, 4, 5]
[0, 2, 6, 9, 11, 15]</pre>
[0, 2, 6, 9, 11, 15]</pre>


=={{header |Rust}}==
=={{header |Rust}}==
{{Output?}}
<lang Rust> fn lis(x: Vec<i32>)-> Vec<i32> {
<lang Rust> fn lis(x: Vec<i32>)-> Vec<i32> {
let n = x.len();
let n = x.len();
Line 1,991: Line 1,990:
println!("{:?}", o);
println!("{:?}", o);
}</lang>
}</lang>

=={{header|Scala}}==
=={{header|Scala}}==
===Simple solution===
<lang Scala>object LongestIncreasingSubsequence extends App {
<lang Scala>object LongestIncreasingSubsequence extends App {
⚫
def longest(l: Array[Int]) = l match {
case _ if l.length < 2 => Array(l)
⚫
case l =>
⚫
def increasing(done: Array[Int], remaining: Array[Int]): Array[Array[Int]] = remaining match {
case Array() => Array(done)
case Array(head, _*) =>
⚫
(if (head > done.last) increasing(done :+ head, remaining.tail) else Array()) ++
⚫
increasing(done, remaining.tail) // all increasing combinations
⚫
}
⚫
val all = (1 to l.length).flatMap(i => increasing(l take i takeRight 1, l.drop(i+1))).sortBy(-_.length)
⚫
all.takeWhile(_.length == all.head.length).toArray // longest from all increasing combinations
}

val tests = Map(
val tests = Map(
"3,2,6,4,5,1" -> Array("2,4,5", "3,4,5"),
"3,2,6,4,5,1" -> Seq("2,4,5", "3,4,5"),
"0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15" -> Array("0,2,6,9,11,15", "0,2,6,9,13,15", "0,4,6,9,13,15", "0,4,6,9,11,15")
"0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15" ->
Seq("0,2,6,9,11,15", "0,2,6,9,13,15", "0,4,6,9,13,15", "0,4,6,9,11,15")
)
)

⚫
def asInts(s: String): Array[Int] = s split "," map Integer.parseInt
⚫
def lis(l: Array[Int]): Seq[Array[Int]] =
⚫
assert(tests forall {case (given, expect) =>
val lis = longest(asInts(given))
if (l.length < 2) Seq(l)
else {
⚫
println(s"$given has ${lis.size} longest increasing subsequences, e.g. "+lis.last.mkString(","))
⚫
def increasing(done: Array[Int], remaining: Array[Int]): Seq[Array[Int]] =
⚫
expect contains lis.last.mkString(",")
if (remaining.isEmpty) Seq(done)
else
(if (remaining.head > done.last)
⚫
increasing(done :+ remaining.head, remaining.tail)
⚫
else Nil) ++ increasing(done, remaining.tail) // all increasing combinations

val all = (1 to l.length)
⚫
.flatMap(i => increasing(l take i takeRight 1, l.drop(i + 1)))
.sortBy(-_.length)
⚫
all.takeWhile(_.length == all.head.length) // longest of all increasing combinations
⚫
}

⚫
def asInts(s: String): Array[Int] = s split "," map (_.toInt)

⚫
assert(tests forall {
⚫
case (given, expect) =>
val allLongests: Seq[Array[Int]] = lis(asInts(given))
println(
⚫
s"$given has ${allLongests.length} longest increasing subsequences, e.g. ${
allLongests.last
⚫
.mkString(",")
}")
allLongests.forall(lis => expect.contains(lis.mkString(",")))
})
})
}</lang>
}</lang>
{{Out}}See it in running in your browser by [https://scalafiddle.io/sf/Wx8DsUO/1 ScalaFiddle (JavaScript)] or by [https://scastie.scala-lang.org/X1r0pzi9Q2WOyqqaXrxMcg Scastie (JVM)].

{{out}}
{{Out}}
<pre>3,2,6,4,5,1 has 2 longest increasing subsequences, e.g. 2,4,5
<pre>3,2,6,4,5,1 has 2 longest increasing subsequences, e.g. 2,4,5
0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15 has 4 longest increasing subsequences, e.g. 0,2,6,9,11,15</pre>
0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15 has 4 longest increasing subsequences, e.g. 0,2,6,9,11,15</pre>
⚫
===Brute force solution===

⚫
<lang Scala>def powerset[A](s: List[A]) = (0 to s.size).map(s.combinations(_)).reduce(_++_)
⚫
Brute force solution :
<lang Scala>
⚫
def powerset[A](s: List[A]) = (0 to s.size).map(s.combinations(_)).reduce(_++_)
def isSorted(l:List[Int])(f: (Int, Int) => Boolean) = l.view.zip(l.tail).forall(x => f(x._1,x._2))
def isSorted(l:List[Int])(f: (Int, Int) => Boolean) = l.view.zip(l.tail).forall(x => f(x._1,x._2))
def sequence(set: List[Int])(f: (Int, Int) => Boolean) = powerset(set).filter(_.nonEmpty).filter(x => isSorted(x)(f)).toList.maxBy(_.length)
def sequence(set: List[Int])(f: (Int, Int) => Boolean) = powerset(set).filter(_.nonEmpty).filter(x => isSorted(x)(f)).toList.maxBy(_.length)
Line 2,031: Line 2,039:
sequence(set)(_<_)
sequence(set)(_<_)
sequence(set)(_>_)</lang>
sequence(set)(_>_)</lang>

=={{header|Scheme}}==
=={{header|Scheme}}==
Patience sorting
Patience sorting
Retrieved from "https://rosettacode.org/wiki/Longest_increasing_subsequence"