generating the cartesian power of a set

Question

Is there a fast way to generate the cartesian power of a set?

For example, if the set is {1, 2}, then {1, 2} x {1, 2} = {(1, 1), (1, 2), (2, 1), (2, 2)}. How would I go about generating it for any given power?

Thank you.

Answer 1

I guess with power, you mean how often the set is combined with itself? So power 3 would be:

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

so you can solve it recursively, combine the set once, and then the set with the result...

If you like, you can adapt my Iterator for Lists of Lists to List of Sets , and build an interator: 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 <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 ();
        }
    }
}

Output: 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

If you can use external libraries, Guava has Sets.cartesianProduct(Set<E>...), so you can just do:

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

(Disclosure: I contribute to Guava.)

Answer 3

You can try with for two vectors 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;
}