java - 集合のデカルト累乗を生成する

Question

セットのデカルト力を生成する高速な方法はありますか?

たとえば、セットが {1, 2} の場合、{1, 2} x {1, 2} = {(1, 1), (1, 2), (2, 1), (2, 2) }。与えられた力に対してそれを生成するにはどうすればよいですか？

ありがとうございました。

Answer 1

パワーとは、セットがそれ自体と組み合わされる頻度を意味しますか？したがって、パワー3は次のようになります。

{1, 2} x {1, 2} x {1, 2} = (({1, 2} x {1, 2}) x {1, 2}) 

したがって、再帰的に解決し、セットを1回結合してから、セットと結果を組み合わせることができます...

必要に応じて、リストのリスト用のイテレーターをセットのリストに適合させ、インターレーターを作成できます。importjava.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 <Set <T>> llo) {
    // transform Set<T> to List <T>, because we need an index later
        List <List <T>> llt = new ArrayList <List <T>> ();    
        for (Set <T> st : llo)
        {
        List <T> lt = new ArrayList <T> ();
        for (T t: st)
            lt.add (t);
        llt.add (lt);
    }
        lilio = llt;
        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 <Set <T>> lilio;  

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

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

public class SetItTest 
{
    public static void main ( String [] args )
    {
        Set <Integer> si = new HashSet<Integer> ();
        si.add (1);
        si.add (2);
        List <Set<Integer>> ls = new ArrayList <Set<Integer>> ();
        ls.add (si);
        ls.add (si);
        ls.add (si);
        CartesianIterable <Integer> ci = new CartesianIterable <Integer> (ls); 
        for (List <Integer> li : ci) 
        {
            for (int i : li)
                System.out.print (i + " ");
            System.out.println ();
        }
    }
}

出力：java SetItTest

1 1 1 
2 1 1 
1 2 1 
2 2 1 
1 1 2 
2 1 2 
1 2 2 
2 2 2 

Answer 2

外部ライブラリを使用できる場合、GuavaにはがSets.cartesianProduct(Set<E>...)あります。そのため、次のことができます。

Set<Integer> set = ImmutableSet.of(1, 2);
Set<List<Integer>> = Sets.cartesianProduct(set, set);
// returns {[1, 1], [1, 2], [2, 1], [2, 2]} as desired

（開示：私はグアバに貢献します。）

Answer 3

2 つのベクトル v1 = {x1...xn}、v2 = {y1...yn} で試すことができます。

public List producto(List a, List b) {
    List producto = new ArrayList();
    for (String s1 : a);
        for (String s2 : b) {
            List duo = new ArrayList();
            duo.add(s1);
            duo.add(s2);
            producto.add(duo);
        }
    }
    return producto;
}