Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Find groups of continuous integers in a list in Java

Tags:

java

list

integer

I have a list of integers placed in order. I want to get groups of consecutive integers as arrays with 1st and last integer of each group.

For example, for (2,3,4,5,8,10,11,12,15,16,17,18,25) I want to get a list with those arrays: [2,5] [8,8] [10,12] [15,18] [25,25]

Here is my code:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class MyRangesTest {


public static void main(String[] args) {
    //create list of integers
    List<Integer> list=Arrays.asList(2,3,4,5,8,10,11,12,15,16,17,18,25);
    System.out.println("list:" + list);


        //create a list with integers where a new sequense of consecutive integers starts or ends
        List<Integer> sublistsStarsAndEnds= new ArrayList<>();
        sublistsStarsAndEnds.add(list.get(0));//1st line (always in sublistsStarsAndEnds list)
        for (int i=1; i<list.size()-1; i++){
            if (list.get(i)>1+list.get(i-1)){
                sublistsStarsAndEnds.add(list.get(i-1));
                sublistsStarsAndEnds.add(list.get(i));
            }
        }
        sublistsStarsAndEnds.add(list.get(list.size()-1));//last line (always in sublistsStarsAndEnds list)
        System.out.println("sublistsStarsAndEnds: " + sublistsStarsAndEnds);//present the result


        //create list with arrays that represents start and end of each subrange of consequent integers
        List<Integer[]> ranges= new ArrayList<>();
        for (int i=0; i<sublistsStarsAndEnds.size()-1; i=i+2){
            Integer[] currentrange=new Integer[2];
            currentrange[0]=sublistsStarsAndEnds.get(i);
            currentrange[1]=sublistsStarsAndEnds.get(i+1);
            ranges.add(currentrange);//present the result
        }

        //present the result
        String rangestxt="";//create result text
        for (int i=0; i<ranges.size(); i++){
            rangestxt=rangestxt+ranges.get(i)[0]+ " " + ranges.get(i)[1]+ "    ";
         }        
        System.out.println("ranges: " + rangestxt);//present the result


    }

}

This code works in the general case for what I want but when the last sequence has only 1 integer it fails to get the right result.

For example when using this list: (2,3,4,5,8,10,11,12,15,16,17,18,25) instead of getting the ranges [2,5] [8,8] [10,12] [15,18] [25,25] we get the ranges [2,5] [8,8] [10,12] [15,25].

The problem is with the detection of where the ranges start or end. In my code those places are stored in the sublistsStarsAndEnds list. Here instead of getting [2, 5, 8, 8, 10, 12, 15, 15, 25, 25] we get [2, 5, 8, 8, 10, 12, 15, 25]. I tried to correct the code but I without good results.

Any suggestions please?

P.S. Someone wanted to get the result I want and asked a question for Python here "Identify groups of continuous numbers in a list But I don't know Python so I tried my own coding.

like image 300
geo Avatar asked Oct 26 '14 05:10

geo


3 Answers

If I understand your question, you could write a POJO class Range like

static class Range {
    private int start;
    private int end;

    Range(int start, int end) {
        this.start = start;
        this.end = end;
    }

    @Override
    public String toString() {
        return String.format("%d - %d", start, end);
    }
}

Then your problem becomes adding a start to an end position where the end position is i-1 in list.get(i - 1) + 1 != list.get(i). Something like,

public static void main(String[] args) {
    List<Integer> list = Arrays.asList(2, 3, 4, 5, 8, 10, 11, 12, 15, 16,
            17, 18, 25);
    System.out.println("list:" + list);
    int start = 0;
    List<Range> ranges = new ArrayList<>();
    for (int i = 1; i < list.size(); i++) {
        if (list.get(i - 1) + 1 != list.get(i)) {
            ranges.add(new Range(list.get(start), list.get(i - 1)));
            start = i;
        }
    }
    ranges.add(new Range(list.get(start), list.get(list.size() - 1)));
    System.out.println(ranges);
}

Output is (as requested)

[2 - 5, 8 - 8, 10 - 12, 15 - 18, 25 - 25]

I will point out that this is very nearly Run-length Encoding.

like image 180
Elliott Frisch Avatar answered Oct 18 '22 16:10

Elliott Frisch


Another short answer in kotlin, Assuming no repetition in the list

    list.fold(mutableListOf<MutableList<Int>>()) { acc, i ->
        acc.also { outer ->
            outer.lastOrNull()?.takeIf { it[1] + 1 == i  }?.also {
                it[1] = i
            } ?: mutableListOf(i, i).also {
                outer.add(it)
            }
        }
    }
like image 30
jfawkes Avatar answered Oct 18 '22 15:10

jfawkes


Elegant Solution:

    static String pair(int[] array){
        String res = "";
        
        int i = 0, j = 1;
        //loop through all items in array.
        while(i < array.length){
            //increase j while array[j] - array[j - 1] equals 1
            while(j < array.length && array[j] - array[j - 1] == 1){
                j++;
            }
            //we came out of that loop, no longer in a sequence. 
            //write to the output.
            res += toTuple(i,j - 1, array);
            //i now points to j.
            //j is now i + 1;
            i = j;
            j = i + 1;
        }
    
        return res;
    }
    
    static String toTuple(int low, int high, int[] array){
        return "[" + array[low] + "," + array[high] + "]";
    }
  • Sample Input: {1, 2, 3, 6, 7,9,10,11,13,14,15,20}
  • Output: [1,3][6,7][9,11][13,15][20,20]
like image 34
Rafael Valle Avatar answered Oct 18 '22 16:10

Rafael Valle