0

I have a list of integers values and I want to find the largest successive sequence integers in the list.

For example, let L be the following list of integers:

L = {1, 3, 4 , 6, 7, 8, 10, 12, 13}

Then I want to collect out of the stream only the following integers:

6, 7, 8

Because these numbers are the largest successive sequence integers in the list L.

Is it possible to do it using streams in Java 8?

This is what I have so far using simple iteration in Java:

    int maxSeqSize = 0;
    List<Cards> maxSeq;
    int currentNumber;
    int startSeq = -1;

    List<Card> currentCards = new ArrayList<> Cards.getCards());
    Collections.sort(currentCards, Cards::CompareByNumber);

    for (currentNumber = 0; currentNumber< Cards.getCards().size() - 1; currentNumber++){
           if((isSequentialCards(Cards.getCards().get(currentNumber ),
                                Cards.getCards().get(currentNumber + 1)))) {
            if (startSeq == -1) 
               startSeq = currentNumber ;

           }
           else {
             if(startSeq > 0 && currentNumber - startSeq + 1 >= maxSeqSize ) 
             {                                        
                  maxSeqSize = currentNumber - startSeq + 1;
                  maxSeq = currentCards .subList(startSeq,currentNumber +1);
             }
                    startSeq = -1;
           }
      }

      return maxSeq;

While isSequentialCards compare two cards by their value:

private boolean isSequentialCards(Card c1, Card c2) {
    if((c1.getNumber() == c2.getNumber() - 1))
        return true;
    return false;
}

Thanks in advance

SyndicatorBBB
  • 1,757
  • 2
  • 26
  • 44
  • 2
    Did you try something or you hoping someone will give you a solution ? – StackFlowed Nov 20 '15 at 18:24
  • streams are a bad choice for such a problem. you are looking to iterate over the list and for each element start another iteration to see how far ahead you have successive elements. A for loop with integer index seems more natural – Manos Nikolaidis Nov 20 '15 at 18:25
  • That is not so hard. You just have to sort the list (if unsorted), iterate over (checking if element in position `i+1` is equal to the element in position `i` + 1 – cr0ss Nov 20 '15 at 18:29
  • it can be done functionally, and in linear time, in the stream using reduce() where the reduction partial result carries a tuple of the largest successive sequence seen so far and the current successive sequence. That should get you going. – davidbak Nov 20 '15 at 18:30
  • Actually, now that I read the documentation, it is probably best done using combine(). Let us know your solution to this homework problem, just for fun. – davidbak Nov 20 '15 at 18:57
  • 5
    It's a one-liner using my [StreamEx](https://github.com/amaembo/streamex) library: `StreamEx.of(1, 3, 4, 6, 7, 8, 10, 12, 13).groupRuns((a, b) -> b-a == 1).maxBy(List::size).orElse(Collections.emptyList())` – Tagir Valeev Nov 21 '15 at 02:51
  • @davidbak It's not homework... I will try it. Thank you. – SyndicatorBBB Nov 21 '15 at 09:02
  • @TagirValeev - thanks for bringing my attention to your library, looks interesting. – davidbak Nov 21 '15 at 17:28
  • BTW, with my low rep I can't affect close votes or anything, but it doesn't seem off topic to me. It's a question of the form: I know how to do this in a typical way (and here's my code), but I don't understand how to do it with some specific new(ish) language feature, which should be usable for this purpose. And what is requested to be done is _possible_ with that feature, but not at all obvious. There are, for example, few or no examples of this sort of thing on the web, using Google with straightforward search terms. It's a good question. – davidbak Nov 21 '15 at 17:39
  • And I take back what I said about homework. On reconsideration, it is a good question. I learned something by working on it. (Stream::combine() is in fact the ticket. But look elsewhere and learn how to ensure the stream is _not_ processed in parallel.) – davidbak Nov 21 '15 at 17:41
  • 1
    Look at this [gist](https://gist.github.com/david-bakin/96f15141accbebb7729f) for two answers using collect(). I'll make it an answer if this question doesn't get (unfairly) closed. – davidbak Nov 21 '15 at 17:53
  • @davidbak, it's possible to write a combiner in your answers, though some people would consider this just a wasting of time. Btw, StreamEx solution is parallel-friendly and will likely to have better performance in parallel stream when input contains thousands of elements. – Tagir Valeev Nov 22 '15 at 01:58
  • @TagirValeev - yes - that's what I say at my [gist](https://gist.github.com/david-bakin/96f15141accbebb7729f) (where the second one does use a Collector class) - that it seems heavyweight - between the API itself - 5 functions to write - and the usual _non_-terse Java syntax ... oh well. Anyway, the issue with parallel _in this case_ or any similar case where you're doing things with adjacent elements is that you can't cross spliterated batches (is that a word) with your processing. Right? – davidbak Nov 22 '15 at 02:30
  • @davidbak, you can cross, but it's necessary to handle such cases separately and there are really a lot of cases. You may take a look on my [CollapseSpliterator](https://github.com/amaembo/streamex/blob/master/src/main/java/one/util/streamex/CollapseSpliterator.java) which is inside the `groupRuns` to get the idea how it works. It's really complex thing. – Tagir Valeev Nov 22 '15 at 03:36

1 Answers1

1

Best I could do with streams :

List<Card> largestSequence = cards.stream()
            //.sorted((card1, card2) -> card1.getNumber() - card2.getNumber())
            .collect(
                    (Supplier<List<List<Card>>>) ArrayList::new,
                    (sequences, currentCard) -> {
                        if (sequences.size() == 0 || !isSequentialCards(getLast(getLast(sequences)), currentCard)) {
                            sequences.add(new ArrayList<>());
                        }
                        getLast(sequences).add(currentCard);
                    },
                    List::addAll)
            .stream()
            .sorted((sequence1, sequence2) -> sequence2.size() - sequence1.size())
            .findFirst()
            .get();

What are the steps :

  • find all sequences of consecutive numbers
  • order sequences from the biggest to the smallest
  • get the first sequence (the biggest)

How ?

  • sorted : which I commented because I don't know if you want the largest sequence in the list order, or as @cr0ss suggested. It basically sorts the list in ascending order, smallest number to the biggest.
  • collect : in which you can see the three "operations" that Collectors can provide (like Collectors.toList). It's where all the magic of finding a sequence of consecutive numbers happens. This implementation tries to collect a list of sequences (also a list) of consecutive numbers. :
    • supplier : initializes the container : a list of list of cards (a list of card sequences).
    • accumulator : what makes a number to be inserted in a sequence (described in the next part).
    • combiner : defines how to merge two list. Not used but needed, the basic addAll is enough.
  • sorted : orders the sequences from the biggest to the smallest
  • findFirst : takes the first, hence the biggest

I've found information on collectors in another answer. The rest is all from the java documentation.

What makes a number being part of a sequence ?

Given a list 3, 4, 6 No sequences exists, create a new sequence.

[] -> [[]]

Insert 3 at the end of the last sequence.

[[]] -> [[3]]

At least one sequence exists and 4 is consecutive to 3, the last number of the last sequence. Insert 4 at the end of the last sequence.

[[3]] -> [[3, 4]]

A sequence exists, but 6 is not consecutive to 4, the last number of the last sequence. Create a new sequence.

[[3, 4]] -> [[3, 4], []]

Insert 6 at the end of the last sequence.

[[3, 4], []] -> [[3, 4], [6]]

Like @Manos said, streams are an odd choice to solve this problem. I think the problem is that it can be hard to maintain when you are not used to streams, lambda or collectors, especially with a one-liner like here (personal choice, I prefer my code to be maintainable by anyone).

Community
  • 1
  • 1
Aigrefin
  • 125
  • 8