CODEWITHSUNDEEP
scala
S.H
S.H

Reputation: 33

Subsequence in a sequence of numbers in scala

For example i have: List(1,3,2,5)

How i get all these: List(1), List(3), List(2), List(5), List(1,3), List(1,2), List(1,5), List(3,2), List(3,5), List(2,5), List(1,3,2), List(1,3,5), List(1,2,5), List(3,2,5), List(1,3,2,5))

I need this for Longest Increasing Subsequence -problem and this answer for example would be: (1,3,5)

And I want use it for bigger Lists.

Upvotes: 2

Views: 1887

Answers (2)

Tim
Tim

Reputation: 27366

[ Update in response to updated question ]

[ Thanks to @jwvh for spotting error in original version ]

This method will generate all possible sub-sequences of a List:

def subsequences[T](list: List[T]): List[List[T]] =
  list match {
    case Nil =>
      List(List())
    case hd :: tl =>
      val subs = subsequences(tl)

      subs.map(hd +: _) ++ subs
  }

Note that this is not efficient for a number of reasons, so it is not a good way to solve the "longest increasing subsequence problem".

[ Original answer ]

This function will generate all the non-empty contiguous sub-sequences of any sequence:

 def subsequences[T](seq: Seq[T]) =
   seq.tails.flatMap(_.inits).filter(_.nonEmpty)

This returns an Iterator so it creates each sub-sequence in turn which reduces memory usage.

Note that this will generate all the sub-sequences and will preserve the order of the values, unlike solutions using combinations or Set.

You can use this in your "longest increasing subsequence problem" like this:

def isAscending(seq: Seq[Int]): Boolean =
  seq.length <= 1 || seq.sliding(2).forall(x => x(0) < x(1))

subsequences(a).filter(isAscending).maxBy(_.length)

The result will be the longest sequence of ascending values in the input a.

Upvotes: 0

jwvh
jwvh

Reputation: 51271

You want all the combinations() from 1 to array length.

val arr = Array(4, 3, 1)

arr.indices.flatMap(x => arr.combinations(x + 1))
//res0: Seq[Array[Int]] = Vector(Array(4), Array(3), Array(1), Array(4, 3), Array(4, 1), Array(3, 1), Array(4, 3, 1))

update

This will give you all possible combinations, retaining original order and duplicate elements.

def subseqs[A](seq :Seq[A]) :List[Seq[A]] = seq match {
  case hd +: tl =>
    val res = subseqs(tl)
    Seq(hd) :: res ++ res.map(hd +: _)
  case Seq() => Nil
}

The result is a List of n^2 - 1 possible sub-sequences. So for a collection of 8 elements you'll get 255 sub-sequences.

This, of course, is going to be way too tedious and inefficient for your purposes. Generating all possible sub-sequences in order to find the Longest Increasing is a little like washing all the clothes in your neighborhood so you'll have clean socks in the morning.

Much better to generate only the increasing sub-sequences and find the longest from that set (9 lines of code).

Upvotes: 6

Related Questions