How to find common sequences between two lists in Java

user_10438381 0
Viewed 574

I'm trying to find common sequences between two lists.If we try to find common sequences in lists which has all unique values , i can do it. For example:

list one: [1, 8, 3, 13, 14, 6, 11]
listTwo : [8, 9, 10, 11, 12, 13, 14, 15]

As we can see , the [13,14] sequence is common for two list. My algorithm is , with retainAll function i'm having the common values , and for this example it's [8,11,13,14]. But since the list one has changed by "retainAll" function, i'm creating copy of list one. Then i'm taking positions of these common values from their original lists (list one and list two). After that i'm getting difference of positions for consecutive values. Like:

       list1   list2   difList1     difList2
[8]     1      0     -1  (0-1)   -1  (0-1)
[11]    6      3     -5  (1-6)   -3  (0-3)
[13]    3      5      3  (6-3)   -2  (3-5)
[14]    4      6     -1  (3-4)   -1  (5-6)

If both difList1 and difLis2 values are shows "-1" that means , that value and the previous one is consecutive and makes sequence.Since [14] meets the condition in this example, the sequence is [13][14].

For this case , my code is:

public static void main(String args[]) {
    List<Integer> list1= new ArrayList(Arrays.asList(1, 8, 3, 13, 14, 6, 11));
    List<Integer> list2= new ArrayList(Arrays.asList(8, 9, 10, 11, 12, 13, 14, 15));
    list1.retainAll(list2);
    List<Integer> ori_list1= new ArrayList(Arrays.asList(1, 8, 3, 13, 14, 6, 11));
    List<Integer> difList1= new ArrayList<>();
    List<Integer> diffList2= new ArrayList<>();
    difList1.add(-1); // Since the first element doesn't have any previous element in common elements list,i'm putting -1 on first index.
    diffList2.add(-1); // Since the first element doesn't have any previous element in common elements list,i'm putting -1 on first index.
    System.out.println(list1); // common elements are [8, 13, 14, 11]


    for(int k=1;k<list1.size();k++){ // Let's say k = 2 ..
        int index1_1 = ori_list1.indexOf(list1.get(k)); // For index 2, it takes actual index of 14 value -> 4
        int index1_2 = ori_list1.indexOf(list1.get(k-1)); // it takes actual index of 13 value -> 3
        int diff_list1 = index1_2-index1_1; // 3-4= -1 -> we got -1 .That means they're consecutive.
        difList1.add(diff_list1); // And putting the -1 into the diffList1.
        int index2_1 = list2.indexOf(list1.get(k)); // doing the same thing for list2.. -> 6
        int index2_2 = list2.indexOf(list1.get(k-1)); // doing the same thing for list2.. -> 5
        int diff_doc2 = index2_2-index2_1;  // 5-6 = -1
        diffList2.add(diff_doc2); // put -1 in diffList2 
    }
    for(int y=1;y<difList1.size();y++){ 
        if(difList1.get(y)==-1 && diffList2.get(y)==-1){  // Since they are both -1 for 14 value 

            System.out.println("The common sequence is:"+list1.get(y-1)+" "+list1.get(y)); // Print them
        }
    }
}

But I need the solution for the duplicate elements situation. Let's say we have lists like

list one: [1, 8, 3,10, 13,8,10, 14, 6, 11] listTwo : [8, 9, 10, 11, 12,8,10, 13, 14, 15]

Now we have another common sequence [8,10].In the output , i wanna see both [13,14] and [8,10]. But i only see [13,14]. Because when indexes are calculating for 8 and 10 , the program takes the indexes of first 8 and 10. For list1 , it takes 1st index for 8 value and 3rd index for 10 value. But i need to pass them since i used them already, i need indexes like 5 and 6,not 1 and 3 again.

And i don't know how to find sequences which has more than two values. For example not only [13,14] but also [13,14,15] or more if they are consecutive. I know it's kinda tough question but i need your help.

pattern-matching list algorithm java
2 Answers

I am not exactly sure what you are trying to do but if I was doing common sequences I would do it by creating sublists and comparing them:

        public static Set<List<Integer>> findCommonSequence(List<Integer> source, List<Integer> target, int startLength) {
        Set<List<Integer>> sequences = new LinkedHashSet<>();

        // algorithm works in this way:
        // we prepare all possible sublists of source list that are at least startLength length
        // and then we check every of those sublists against the target list to see if it contains any

        // length is from startLength to maxSize, to check all sublists with that length
        // ie if startLength is 2 and source is 10, it will be 2 - 10 and thus it will check all sublist sizes
        for (int length = startLength; length < source.size(); length++) {
            // startIndex will move from 0 to original_list - length, so if length is 2, it will generate sublists
            // with indexes 0,1; 1,2; 2,3 ... 8,9
            for (int startIndex = 0; startIndex+length < source.size(); startIndex++) {
                // creates lightweight sublist that shares the data
                List<Integer> sublist = source.subList(startIndex, startIndex+length);
                // add all found subsequences into the set
                sequences.addAll(findSequenceIn(target, sublist));
            }
        }

        return sequences;
    }

    // Returns all subsequences that are inside the target list
    private static Set<List<Integer>> findSequenceIn(List<Integer> target, List<Integer> sublist) {
        Set<List<Integer>> subsequences = new LinkedHashSet<>();

        // simply do the same process as in first method but with fixed length to the length of sublist
        for (int i=0; i<target.size() - sublist.size(); i++) {
            // create another sublist, this time from target (again, share data)
            List<Integer> testSublist = target.subList(i, i+sublist.size());

            // compare two sublists, if they are equal, that means target list contains sublist from original list
            if (testSublist.equals(sublist)) {
                // add it to the set
                subsequences.add(new ArrayList<>(sublist));
            }
        }

        return subsequences;
    }

You can then optimize the algorithm to just do the checks via sending the indexes instead of sublists and do the comparing manually. Complexity of this algorithm should be from O(n3) to O(n4). Might be O(n4) because we do up to n2 sublists and then compare which is n operation against n sublists of list 2, but it might be n3 because comparisons are smaller, no idea mathematically how close it is to n3 or n4.

Of course there is another n with copy of sublist but you can optimize that one out.

user_28925150

handling the int-values as codePoints:
[1] convert list2 to str2
[2] convert list1 to str1 with all int-values on the left stripped, that are not in list2
[3] move str1 over str2 remembering the longest sequence of str1 standing on top of str2

ArrayList<int[]> results = new ArrayList<>();

String str2 = new String(
            new int[] { 1, 8, 3, 10, 13, 14, 8, 10, 14, 6, 11 }, 0, 11 ); //[1]
int[] tmp = new int[] { 8, 9, 10, 11, 12, 8, 10, 13, 14, 15 };
int[] arr1 = IntStream.of( tmp ).dropWhile(
    c -> str2.indexOf( c ) < 0 ).toArray();      //[2]
String str1 = new String( arr1, 0, arr1.length );
for( int i = str1.length() - 2; i >= 0; i-- ) {  //[3]
  int[] rslt = new int[0];
  for( int j = 0; j < str2.length() - 2; j++ ) {
    int[] idx2 = new int[] { j };
    rslt = str1.substring( i ).codePoints().takeWhile(
        c -> c == (int)str2.charAt( idx2[0]++ ) ).toArray();
    if( rslt.length >= 2 ) {
      results.add( rslt );
    }
  }
}
  
results.forEach(a -> System.out.println( Arrays.toString( a ) ));

gets: [13, 14], [10, 13, 14], [8, 10]

user_111998790
Related