Поиск декартова продукта в Java

Question

Я хочу найти декартово произведение набора элементов. Вот пример

example 1 : 
sets :(ab) (bc) (ca) 

декартово произведение,

абв АБА согласно аса Би-би-BBA ОЦК BCA

example 2 : 
sets : (zyx) b c 

декартово произведение,

ZBC YBC XBC

Так что я думаю об алгоритме для выполнения в java, который может найти декартово произведение определенного количества групп, определенных во время компиляции в начале.

Answer 1

Вы можете использовать Sets.cartesianProduct() method от Google's Guava libraries генерировать декартовы произведения:

com.google.common.collect.Sets.cartesianProduct(Set[] yourSets) 

Если бы все было так просто!

Answer 2

Существенно функциональный подход к этому можно найти в this paper (a "functional pearl") ... Однако это может быть нелегко перевести на Java.

Answer 3

Определите свой итератора/Iterable:

import java.util.*; 

class CartesianIterator <T> implements Iterator <List <T>> { 

    private final List <List <T>> lilio;  
    private int current = 0; 
    private final long last; 

    public CartesianIterator (final List <List <T>> llo) { 
     lilio = llo; 
     long product = 1L; 
     for (List <T> lio: lilio) 
      product *= lio.size(); 
     last = product; 
    } 

    public boolean hasNext() { 
     return current != last; 
    } 

    public List <T> next() { 
     ++current; 
     return get (current - 1, lilio); 
    } 

    public void remove() { 
     ++current; 
    } 

    private List<T> get (final int n, final List <List <T>> lili) { 
     switch (lili.size()) 
     { 
      case 0: return new ArrayList <T>(); // no break past return; 
      default: { 
       List <T> inner = lili.get (0); 
       List <T> lo = new ArrayList <T>(); 
       lo.add (inner.get (n % inner.size())); 
       lo.addAll (get (n/inner.size(), lili.subList (1, lili.size()))); 
       return lo; 
      } 
     } 
    } 
} 

class CartesianIterable <T> implements Iterable <List <T>> { 

    private List <List <T>> lilio; 

    public CartesianIterable (List <List <T>> llo) { 
     lilio = llo; 
    } 

    public Iterator <List <T>> iterator() { 
     return new CartesianIterator <T> (lilio); 
    } 
} 

и проверить его с данными:

class CartesianIteratorTest { 

    public static void main (String[] args) { 
     List <Character> la = Arrays.asList (new Character [] {'a', 'b'}); 
     List <Character> lb = Arrays.asList (new Character [] {'b', 'c'});  
     List <Character> lc = Arrays.asList (new Character [] {'c', 'a'}); 
     List <List <Character>> llc = new ArrayList <List <Character>>(); 
     llc.add (la); 
     llc.add (lb); 
     llc.add (lc); 

     CartesianIterable <Character> ci = new CartesianIterable <Character> (llc); 
     for (List<Character> lo: ci) 
      show (lo); 

     la = Arrays.asList (new Character [] {'x', 'y', 'z'}); 
     lb = Arrays.asList (new Character [] {'b'});  
     lc = Arrays.asList (new Character [] {'c'}); 
     llc = new ArrayList <List <Character>>(); 
     llc.add (la); 
     llc.add (lb); 
     llc.add (lc); 

     ci = new CartesianIterable <Character> (llc); 
     for (List<Character> lo: ci) 
      show (lo);  
    } 

    public static void show (List <Character> lo) { 
     System.out.print ("("); 
     for (Object o: lo) 
      System.out.print (o); 
     System.out.println (")"); 
    } 
} 

Результат:

(abc) 
(bbc) 
(acc) 
(bcc) 
(aba) 
(bba) 
(aca) 
(bca) 
(xbc) 
(ybc) 
(zbc)