intersecting each element of a list with one another

Question

I am trying to intersect each element in a list containing String [] with one another. Each element (String[]) in the input list will be of length 3 or 4

Input: [{'J', 'K', 'L'}, {'G', 'H', 'I'}]
Output: ["JG", "JH", "JI", 
         "KG", "KH", "KI", 
         "LG", "LH", "LI"]

Input: [{'J', 'K', 'L'}, {'G', 'H', 'I'}, {'A', 'B', 'C'}]
Output: ["JGA", "JGB", "JGC", 
         "KGA", "KGB", "KGC", 
         "LGA", "LGB", "LGC", 
         "JHA", "JHB", "JHC",
         "KHA", "KHB", "KHC", 
         "LHA", "LHB", "LHC", 
         "JIA", "JIB", "JIC",
         "KIA", "KIB", "KIC",
         "LIA", "LIB", "LIC"]

The size of each element in the output is equal to the total elements in the input list.

I've done the following but am not getting the correct results.

ArrayList<String> output = new ArrayList();
for (String [] s : InputList)
   for (int i = 0; i < s.length; i++) {
      if (output.size < 3)
         output.add(s[i])
      else {
         output.add(output.get(i)+s[i]);
      }
   }
}

This is similar to: http://stackoverflow.com/questions/11110174/java-get-all-concatenations-of-listliststring — fgb, Nov 04 '12 at 00:20

Keppil · Accepted Answer · 2012-11-04T00:53:34.873

You can use a recursive approach. This will work for any (reasonably) sized list:

public static List<String> combine(List<String[]> list) {
    List<String> elements = new ArrayList<String>();
    if (!list.isEmpty()) {
        String[] head = list.get(0);
        List<String> tail;
        if (list.size() > 1) {
            tail = combine(list.subList(1, list.size()));
        } else {
            tail = Arrays.asList("");
        }
        for (String headElem : head) {
            for (String tailElem : tail) {
                elements.add(headElem + tailElem);
            }
        }
    }
    return elements;
}

dan · Answer 2 · 2012-11-04T01:35:54.880

Here is a non recursive version, if you are still interested:

public String[] cartesian(char input[][]) {                 
    List<String> output = new ArrayList<String>();          
    int m = input.length;                                   
    int n = input[0].length;                                
    int c[] = new int[m];                                   
    int i = m - 1;                                          
    do {                                                    
        output.add(getElement(input, c, m));                
        do {                                                
            if (c[i] < n - 1) {                             
                c[i]++;                                     
                if (i < m - 1)                              
                    i++;                                    
                break;                                      
            } else {                                        
                c[i] = 0;                                   
                i--;                                        
            }                                               
        } while (i >= 0);                                   
    } while (i >= 0);                                       
    return output.toArray(new String[output.size()]);       
}                                                           

private String getElement(char[][] list, int[] c, int n) { 
    String element = "";                                    
    for (int i = 0; i < n; i++)                             
        element += list[i][c[i]];                           
    return element;                                         
}

You should be able to use any number of sublists. For your scenario you can do:

char[][] input={{'J', 'K', 'L'}, {'G', 'H', 'I'}, {'A', 'B', 'C'}};
String[] output = cartesian(input);

@birdy Got it, but that is not an intersection, it's variation of a cartesian product. — dan, Nov 04 '12 at 00:03

intersecting each element of a list with one another

2 Answers2