在Java中查找笛卡爾積

Question

我想找到一組元素的笛卡爾積。這裏有一個例子

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

笛卡兒積是，

ABC ABA ACC ACA BBC BBA BCC BCA

example 2 : 
sets : (zyx) b c 

笛卡兒積是，

ZBC YBC命苦

所以我想在java中執行一個算法，它可以在編譯時在開始時定義特定數量的組的笛卡爾乘積。

Answer 1

您可以使用從Google's Guava libraries的Sets.cartesianProduct() method產生笛卡爾乘積：

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

如果只是一切是那麼容易！

Answer 2

對此的一種純粹的功能方法可以在this paper（a "functional pearl"）中找到......不過，它可能不易於轉換爲Java。

Answer 3

定義你自己的迭代器/可迭代：

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)