fork download
copy 
  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.List;
  4.  
  5. public class Main {
  6.     /**
  7.      * Holds information about a sub set
  8.      *
  9.      * @param <T> type of subset items
  10.      */
  11.     private static class SubSet<T> {
  12.         List<T> items; // items of subset
  13.         int startIndex1; // start index in list 1
  14.         int endIndex1; // end index in list 1
  15.         int startIndex2; // start index in list 2
  16.         int endIndex2; // end index in list 2
  17.     }
  18.  
  19.     /**
  20.      * Run main example.
  21.      *
  22.      * @param args arguments - none honored.
  23.      * @throws java.lang.Exception - in case of any error.
  24.      */
  25.     public static void main(String[] args) throws java.lang.Exception {
  26.         // define 2 lists
  27.         List<Integer> list1 = Arrays.asList(1, 2, 3, 4, 5, 6, 3, 2, 5, 6, 7, 3, 8);
  28.         List<Integer> list2 = Arrays.asList(2, 8, 7, 2, 3, 4, 5, 3, 2, 5, 1, 5);
  29.  
  30.         // print the lists
  31.         System.out.println("First list: " + Arrays.toString(list1.toArray()));
  32.         System.out.println("Second list: " + Arrays.toString(list2.toArray()));
  33.  
  34.         // get largest sub set
  35.         SubSet<Integer> largest = getLargestSubSet(list1, list2);
  36.  
  37.  
  38.         if (largest == null) {
  39.             // nothing found
  40.             System.out.println("No subset found.");
  41.         } else {
  42.             // print info about subset
  43.  
  44.             System.out.println("Largest subset: " + Arrays.toString(largest.items.toArray()));
  45.  
  46.             if (largest.startIndex1 > 0) {
  47.                 List<Integer> beforeList1 = list1.subList(0, largest.startIndex1);
  48.                 System.out.println("Items before largest subset in first list: " 
  49.                         + Arrays.toString(beforeList1.toArray()));
  50.             }
  51.  
  52.             if (largest.endIndex1 < list1.size() - 1) {
  53.                 List<Integer> afterList1 = list1.subList(largest.endIndex1 + 1, list1.size());
  54.                 System.out.println("Items after largest subset in first list: " 
  55.                         + Arrays.toString(afterList1.toArray()));
  56.             }
  57.  
  58.             if (largest.startIndex2 > 0) {
  59.                 List<Integer> beforeList2 = list2.subList(0, largest.startIndex2);
  60.                 System.out.println("Items before largest subset in second list: " 
  61.                         + Arrays.toString(beforeList2.toArray()));
  62.             }
  63.  
  64.             if (largest.endIndex2 < list2.size() - 1) {
  65.                 List<Integer> afterList2 = list2.subList(largest.endIndex2 + 1, list2.size());
  66.                 System.out.println("Items after largest subset in second list: " 
  67.                         + Arrays.toString(afterList2.toArray()));
  68.             }
  69.  
  70.         }
  71.  
  72.  
  73.     }
  74.  
  75.     /**
  76.      * Equality check for items.
  77.      *
  78.      * @param obj1 first item.
  79.      * @param obj2 second item.
  80.      * @param <T>  item type.
  81.      * @return true if equal,false if not.
  82.      */
  83.     private static <T> boolean areEqual(T obj1, T obj2) {
  84.         return obj1 == obj2; // naive comparison
  85.     }
  86.  
  87.     /**
  88.      * Get largest subset (first occurrence) for given lists.
  89.      *
  90.      * @param list1 first list.
  91.      * @param list2 second list.
  92.      * @param <T>   list item type.
  93.      * @return Largest sub sequence list, or empty list.
  94.      */
  95.     private static <T> SubSet<T> getLargestSubSet(List<T> list1, List<T> list2) {
  96.         SubSet<T> output = null;
  97.  
  98.         for (int i = 0; i < list1.size(); i++) {
  99.             for (int j = 0; j < list2.size(); j++) {
  100.  
  101.                 // optimisation : exit early
  102.                 if (output != null && output.items.size() > Math.min(list1.size(), list2.size())) {
  103.                     return output;
  104.                 }
  105.  
  106.                 if (areEqual(list1.get(i), list2.get(j))) {
  107.                     // inspect sub sequence from this (i,j) onwards
  108.                     output = inspectSubSet(list1, list2, i, j, output);
  109.                 }
  110.             }
  111.         }
  112.  
  113.         return output;
  114.     }
  115.  
  116.     /**
  117.      * For given starting indices, inspect if there is a larger subset, than given one.
  118.      *
  119.      * @param list1     first list.
  120.      * @param list2     second list.
  121.      * @param index1    first index.
  122.      * @param index2    second index.
  123.      * @param oldSubSet existing largest subset, for comparison.
  124.      * @param <T>       list item type.
  125.      * @return larger subset, if found, else existing one is returned as is.
  126.      */
  127.     private static <T> SubSet<T> inspectSubSet(List<T> list1, List<T> list2,
  128.                                                int index1, int index2, SubSet<T> oldSubSet) {
  129.         // new subset candidate
  130.         SubSet<T> newSubSet = new SubSet<T>();
  131.         newSubSet.items = new ArrayList<T>();
  132.         newSubSet.startIndex1 = index1;
  133.         newSubSet.endIndex1 = index1;
  134.         newSubSet.startIndex2 = index2;
  135.         newSubSet.endIndex2 = index2;
  136.  
  137.         // keep building subset as subsequent items keep matching
  138.         do {
  139.             newSubSet.items.add(list1.get(index1));
  140.             newSubSet.endIndex1 = index1;
  141.             newSubSet.endIndex2 = index2;
  142.             index1++;
  143.             index2++;
  144.         } while (index1 < list1.size() && index2 < list2.size()
  145.                 && areEqual(list1.get(index1), list2.get(index2)));
  146.  
  147.         // return first, larger or same.
  148.         if (oldSubSet == null) {
  149.             return newSubSet;
  150.         } else if (newSubSet.items.size() > oldSubSet.items.size()) {
  151.             return newSubSet;
  152.         } else {
  153.             return oldSubSet;
  154.         }
  155.     }
  156.  
  157. }
Success #stdin #stdout 0.1s 320576KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
First list: [1, 2, 3, 4, 5, 6, 3, 2, 5, 6, 7, 3, 8]
Second list: [2, 8, 7, 2, 3, 4, 5, 3, 2, 5, 1, 5]
Largest subset: [2, 3, 4, 5]
Items before largest subset in first list: [1]
Items after largest subset in first list: [6, 3, 2, 5, 6, 7, 3, 8]
Items before largest subset in second list: [2, 8, 7]
Items after largest subset in second list: [3, 2, 5, 1, 5]
https://ideone.com/DehDwk
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!