产生集合的笛卡尔幂 [英] generating the cartesian power of a set

问题描述

是否有一种快速的方法来生成集合的笛卡尔幂?

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

例如，如果集合为{1，2}，则{1，2} x {1，2} = {(1，1)，(1，2)，(2，1)，(2 ，2)}.我将如何在任何给定的功率下生成它?

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?

谢谢.

推荐答案

我想使用 power ，您是说集合与自身结合的频率是多少?因此，幂3将是:

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...

如果愿意，您可以将我的Iterator for Lists Lists调整为Sets Sets，并构建一个Interator: 导入java.util.*;

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 ();
        }
    }
}

输出: java SetItTest

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 

这篇关于产生集合的笛卡尔幂的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！