22

Javaで任意の数の空でないセットのデカルト積を計算したいと思います。

私はその反復コードを書きました...

public static <T> List<Set<T>> cartesianProduct(List<Set<T>> list) {
    List<Iterator<T>> iterators = new ArrayList<Iterator<T>>(list.size());
    List<T> elements = new ArrayList<T>(list.size());
    List<Set<T>> toRet = new ArrayList<Set<T>>();
    for (int i = 0; i < list.size(); i++) {
        iterators.add(list.get(i).iterator());
        elements.add(iterators.get(i).next());
    }
    for (int j = 1; j >= 0;) {
        toRet.add(Sets.newHashSet(elements));
        for (j = iterators.size()-1; j >= 0 && !iterators.get(j).hasNext(); j--) {
            iterators.set(j, list.get(j).iterator());
            elements.set(j, iterators.get(j).next());
        }
        elements.set(Math.abs(j), iterators.get(Math.abs(j)).next());
    }
    return toRet;
}

...しかし、私はそれがかなりエレガントではないと感じました。誰かがより良い、まだ反復的な解決策を持っていますか？いくつかの素晴らしい機能のようなアプローチを使用するソリューション？そうでなければ...それを改善する方法についての提案？エラー？

4

10 に答える 10

24

大量のコレクションをメモリに入力する必要のないソリューションを作成しました。残念ながら、必要なコードは数百行の長さです。Guavaプロジェクト（ https://github.com/google/guava ）に表示されるまで待たなければならない場合があります。これは、年末までに行われることを願っています。ごめん。:(

デカルト製品であるセットの数がコンパイル時にわかっている固定数である場合は、このようなユーティリティは必要ない場合があることに注意してください。ネストされたforループの数だけを使用できます。

編集：コードは現在リリースされています。

Sets.cartesianProduct()

とても満足していただけると思います。要求されたとおりに個々のリストを作成するだけです。それらのすべてのMxNxPxQでメモリをいっぱいにするわけではありません。

ソースを調べたい場合は、ここにあります。

楽しみ！

于 2009-11-12T15:29:15.560 に答える
5

GoogleGuava19とJava8の使用は非常に簡単です。

関連付けたいすべてのアレイのリストがあるとします...

public static void main(String[] args) {
  List<String[]> elements = Arrays.asList(
    new String[]{"John", "Mary"}, 
    new String[]{"Eats", "Works", "Plays"},
    new String[]{"Food", "Computer", "Guitar"}
  );

  // Create a list of immutableLists of strings
  List<ImmutableList<String>> immutableElements = makeListofImmutable(elements);

  // Use Guava's Lists.cartesianProduct, since Guava 19
  List<List<String>> cartesianProduct = Lists.cartesianProduct(immutableElements);

  System.out.println(cartesianProduct);
}

不変リストのリストを作成する方法は次のとおりです。

/**
 * @param values the list of all profiles provided by the client in matrix.json
 * @return the list of ImmutableList to compute the Cartesian product of values
 */
private static List<ImmutableList<String>> makeListofImmutable(List<String[]> values) {
  List<ImmutableList<String>> converted = new LinkedList<>();
  values.forEach(array -> {
    converted.add(ImmutableList.copyOf(array));
  });
  return converted;
}

出力は次のとおりです。

[
  [John, Eats, Food], [John, Eats, Computer], [John, Eats, Guitar],
  [John, Works, Food], [John, Works, Computer], [John, Works, Guitar], 
  [John, Plays, Food], [John, Plays, Computer], [John, Plays, Guitar],
  [Mary, Eats, Food], [Mary, Eats, Computer], [Mary, Eats, Guitar],
  [Mary, Works, Food], [Mary, Works, Computer], [Mary, Works, Guitar],
  [Mary, Plays, Food], [Mary, Plays, Computer], [Mary, Plays, Guitar]
]
于 2016-05-27T19:14:43.357 に答える
1

次の答えは、再帰ではなく反復を使用しています。Tuple以前の回答と同じクラスを使用しています。

IMHOはどちらも有効で異なるアプローチであるため、これは別の答えです。

新しいメインクラスは次のとおりです。

public class Example {
    public static <T> List<Tuple<T>> cartesianProduct(List<Set<T>> sets) {
        List<Tuple<T>> tuples = new ArrayList<Tuple<T>>();
        for (Set<T> set : sets) {
            if (tuples.isEmpty()) {
                for (T t : set) {
                    Tuple<T> tuple = new Tuple<T>();
                    tuple.add(t);
                    tuples.add(tuple);
                }
            } else {
                List<Tuple<T>> newTuples = new ArrayList<Tuple<T>>();
                for (Tuple<T> subTuple : tuples) {
                    for (T t : set) {
                        Tuple<T> tuple = new Tuple<T>();
                        tuple.addAll(subTuple);
                        tuple.add(t);
                        newTuples.add(tuple);
                    }
                }
                tuples = newTuples;
            }
        }
        return tuples;
    }
}
于 2009-11-12T04:44:47.367 に答える
1

これが私が書いた反復的で怠惰な実装です。インターフェースはGoogleのSets.cartesianProductに非常に似ていますが、もう少し柔軟性があります。SetsではなくIterablesを扱います。このコードとその単体テストはhttps://gist.github.com/1911614にあります。

/* Copyright 2012 LinkedIn Corp.

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
 */

import com.google.common.base.Function;
import com.google.common.collect.Iterables;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

/**
 * Implements the Cartesian product of ordered collections.
 * 
 * @author <a href="mailto:jmkristian@gmail.com">John Kristian</a>
 */
public class Cartesian {
  /**
   * Generate the <a href="http://en.wikipedia.org/wiki/Cartesian_product">Cartesian
   * product</a> of the given axes. For axes [[a1, a2 ...], [b1, b2 ...], [c1, c2 ...]
   * ...] the product is [[a1, b1, c1 ...] ... [a1, b1, c2 ...] ... [a1, b2, c1 ...] ...
   * [aN, bN, cN ...]]. In other words, the results are generated in same order as these
   * nested loops:
   * 
   * <pre>
   * for (T a : [a1, a2 ...])
   *   for (T b : [b1, b2 ...])
   *     for (T c : [c1, c2 ...])
   *       ...
   *         result = new T[]{ a, b, c ... };
   * </pre>
   * 
   * Each result is a new array of T, whose elements refer to the elements of the axes. If
   * you prefer a List, you can call asLists(product(axes)).
   * <p>
   * Don't change the axes while iterating over their product, as a rule. Changes to an
   * axis can affect the product or cause iteration to fail (which is usually bad). To
   * prevent this, you can pass clones of your axes to this method.
   * <p>
   * The implementation is lazy. This method iterates over the axes, and returns an
   * Iterable that contains a reference to each axis. Iterating over the product causes
   * iteration over each axis. Methods of each axis are called as late as practical.
   */
  public static <T> Iterable<T[]> product(Class<T> resultType,
                                          Iterable<? extends Iterable<? extends T>> axes) {
    return new Product<T>(resultType, newArray(Iterable.class, axes));
  }

  /** Works like product(resultType, Arrays.asList(axes)), but slightly more efficient. */
  public static <T> Iterable<T[]> product(Class<T> resultType, Iterable<? extends T>... axes) {
    return new Product<T>(resultType, axes.clone());
  }

  /**
   * Wrap the given arrays in fixed-size lists. Changes to the lists write through to the
   * arrays.
   */
  public static <T> Iterable<List<T>> asLists(Iterable<? extends T[]> arrays) {
    return Iterables.transform(arrays, new AsList<T>());
  }

  /**
   * Arrays.asList, represented as a Function (as used in Google collections).
   */
  public static class AsList<T> implements Function<T[], List<T>> {
    @Override
    public List<T> apply(T[] array) {
      return Arrays.asList(array);
    }
  }

  /** Create a generic array containing references to the given objects. */
  private static <T> T[] newArray(Class<? super T> elementType, Iterable<? extends T> from) {
    List<T> list = new ArrayList<T>();
    for (T f : from)
      list.add(f);
    return list.toArray(newArray(elementType, list.size()));
  }

  /** Create a generic array. */
  @SuppressWarnings("unchecked")
  private static <T> T[] newArray(Class<? super T> elementType, int length) {
    return (T[]) Array.newInstance(elementType, length);
  }

  private static class Product<T> implements Iterable<T[]> {
    private final Class<T> _resultType;
    private final Iterable<? extends T>[] _axes;

    /** Caution: the given array of axes is contained by reference, not cloned. */
    Product(Class<T> resultType, Iterable<? extends T>[] axes) {
      _resultType = resultType;
      _axes = axes;
    }

    @Override
    public Iterator<T[]> iterator() {
      if (_axes.length <= 0) // an edge case
        return Collections.singleton(newArray(_resultType, 0)).iterator();
      return new ProductIterator<T>(_resultType, _axes);
    }

    @Override
    public String toString() {
      return "Cartesian.product(" + Arrays.toString(_axes) + ")";
    }

    private static class ProductIterator<T> implements Iterator<T[]> {
      private final Iterable<? extends T>[] _axes;
      private final Iterator<? extends T>[] _iterators; // one per axis
      private final T[] _result; // a copy of the last result
      /**
       * The minimum index such that this.next() will return an array that contains
       * _iterators[index].next(). There are some special sentinel values: NEW means this
       * is a freshly constructed iterator, DONE means all combinations have been
       * exhausted (so this.hasNext() == false) and _iterators.length means the value is
       * unknown (to be determined by this.hasNext).
       */
      private int _nextIndex = NEW;
      private static final int NEW = -2;
      private static final int DONE = -1;

      /** Caution: the given array of axes is contained by reference, not cloned. */
      ProductIterator(Class<T> resultType, Iterable<? extends T>[] axes) {
        _axes = axes;
        _iterators = Cartesian.<Iterator<? extends T>> newArray(Iterator.class, _axes.length);
        for (int a = 0; a < _axes.length; ++a) {
          _iterators[a] = axes[a].iterator();
        }
        _result = newArray(resultType, _iterators.length);
      }

      private void close() {
        _nextIndex = DONE;
        // Release references, to encourage garbage collection:
        Arrays.fill(_iterators, null);
        Arrays.fill(_result, null);
      }

      @Override
      public boolean hasNext() {
        if (_nextIndex == NEW) { // This is the first call to hasNext().
          _nextIndex = 0; // start here
          for (Iterator<? extends T> iter : _iterators) {
            if (!iter.hasNext()) {
              close(); // no combinations
              break;
            }
          }
        } else if (_nextIndex >= _iterators.length) {
          // This is the first call to hasNext() after next() returned a result.
          // Determine the _nextIndex to be used by next():
          for (_nextIndex = _iterators.length - 1; _nextIndex >= 0; --_nextIndex) {
            Iterator<? extends T> iter = _iterators[_nextIndex];
            if (iter.hasNext()) {
              break; // start here
            }
            if (_nextIndex == 0) { // All combinations have been generated.
              close();
              break;
            }
            // Repeat this axis, with the next value from the previous axis.
            iter = _axes[_nextIndex].iterator();
            _iterators[_nextIndex] = iter;
            if (!iter.hasNext()) { // Oops; this axis can't be repeated.
              close(); // no more combinations
              break;
            }
          }
        }
        return _nextIndex >= 0;
      }

      @Override
      public T[] next() {
        if (!hasNext())
          throw new NoSuchElementException("!hasNext");
        for (; _nextIndex < _iterators.length; ++_nextIndex) {
          _result[_nextIndex] = _iterators[_nextIndex].next();
        }
        return _result.clone();
      }

      @Override
      public void remove() {
        for (Iterator<? extends T> iter : _iterators) {
          iter.remove();
        }
      }

      @Override
      public String toString() {
        return "Cartesian.product(" + Arrays.toString(_axes) + ").iterator()";
      }
    }
  }
}
于 2012-02-26T00:05:38.150 に答える
1

インデックスベースのソリューション

インデックスの操作は、高速でメモリ効率が高く、任意の数のセットを処理できる単純な代替手段です。Iterableを実装すると、for-eachループで簡単に使用できます。使用例については、＃mainメソッドを参照してください。

public class CartesianProduct implements Iterable<int[]>, Iterator<int[]> {
    private final int[] _lengths;
    private final int[] _indices;
    private boolean _hasNext = true;

    public CartesianProduct(int[] lengths) {
        _lengths = lengths;
        _indices = new int[lengths.length];
    }

    public boolean hasNext() {
        return _hasNext;
    }

    public int[] next() {
        int[] result = Arrays.copyOf(_indices, _indices.length);
        for (int i = _indices.length - 1; i >= 0; i--) {
            if (_indices[i] == _lengths[i] - 1) {
                _indices[i] = 0;
                if (i == 0) {
                    _hasNext = false;
                }
            } else {
                _indices[i]++;
                break;
            }
        }
        return result;
    }

    public Iterator<int[]> iterator() {
        return this;
    }

    public void remove() {
        throw new UnsupportedOperationException();
    }

    /**
     * Usage example. Prints out
     *
     * <pre>
     * [0, 0, 0] a, NANOSECONDS, 1
     * [0, 0, 1] a, NANOSECONDS, 2
     * [0, 0, 2] a, NANOSECONDS, 3
     * [0, 0, 3] a, NANOSECONDS, 4
     * [0, 1, 0] a, MICROSECONDS, 1
     * [0, 1, 1] a, MICROSECONDS, 2
     * [0, 1, 2] a, MICROSECONDS, 3
     * [0, 1, 3] a, MICROSECONDS, 4
     * [0, 2, 0] a, MILLISECONDS, 1
     * [0, 2, 1] a, MILLISECONDS, 2
     * [0, 2, 2] a, MILLISECONDS, 3
     * [0, 2, 3] a, MILLISECONDS, 4
     * [0, 3, 0] a, SECONDS, 1
     * [0, 3, 1] a, SECONDS, 2
     * [0, 3, 2] a, SECONDS, 3
     * [0, 3, 3] a, SECONDS, 4
     * [0, 4, 0] a, MINUTES, 1
     * [0, 4, 1] a, MINUTES, 2
     * ...
     * </pre>
     */
    public static void main(String[] args) {
        String[] list1 = {"a", "b", "c",};
        TimeUnit[] list2 = TimeUnit.values();
        int[] list3 = new int[]{1, 2, 3, 4};

        int[] lengths = new int[]{list1.length, list2.length, list3.length};
        for (int[] indices : new CartesianProduct(lengths)) {
            System.out.println(Arrays.toString(indices) //
                    + " " + list1[indices[0]] //
                    + ", " + list2[indices[1]] //
                    + ", " + list3[indices[2]]);
        }
    }
}
于 2012-06-08T10:45:59.640 に答える
0

これは正しいと思います。それは効率を求めているのではなく、再帰と抽象化によるクリーンなスタイルを求めています。

重要な抽象化は、単純なTupleクラスを導入することです。これは後でジェネリックに役立ちます：

class Tuple<T> {
    private List<T> list = new ArrayList<T>();

    public void add(T t) { list.add(t); }

    public void addAll(Tuple<T> subT) {
        for (T t : subT.list) {
            list.add(t);
        }
    }

    public String toString() {
        String result = "(";

        for (T t : list) { result += t + ", "; }

        result = result.substring(0, result.length() - 2);
        result += " )";

        return result;
    }
}

このクラスを使用すると、次のようなクラスを作成できます。

public class Example {
    public static <T> List<Tuple<T>> cartesianProduct(List<Set<T>> sets) {
        List<Tuple<T>> tuples = new ArrayList<Tuple<T>>();

        if (sets.size() == 1) {
            Set<T> set = sets.get(0);
            for (T t : set) {
                Tuple<T> tuple = new Tuple<T>();
                tuple.add(t);
                tuples.add(tuple);
            }
        } else {
            Set<T> set = sets.remove(0);
            List<Tuple<T>> subTuples = cartesianProduct(sets);
            System.out.println("TRACER size = " + tuples.size());
            for (Tuple<T> subTuple : subTuples) {
                for (T t : set) {
                    Tuple<T> tuple = new Tuple<T>();
                    tuple.addAll(subTuple);
                    tuple.add(t);
                    tuples.add(tuple);
                }
            }
        }
        return tuples;
    }
}

私はこの動作のまともな例を持っていますが、簡潔にするために省略されています。

于 2009-11-12T04:29:44.590 に答える
0

デカルト積に関する別の質問に興味があるかもしれません（編集：ハイパーリンクを保存するために削除され、タグデカルト積を検索します）。その答えには、改善するのが難しいと思われる再帰的な解決策があります。再帰的なソリューションではなく、反復的なソリューションが特に必要ですか？

perlのスタックオーバーフローに関する別の反復ソリューションと明確な説明を確認した後、別のソリューションを次に示します。

public static <T> List<Set<T>> uglyCartesianProduct(List<Set<T>> list) {
    List<Iterator<T>> iterators = new ArrayList<Iterator<T>>(list.size());
    List<T> elements = new ArrayList<T>(list.size());
    List<Set<T>> toRet = new ArrayList<Set<T>>();

    for (int i = 0; i < list.size(); i++) {
        iterators.add(list.get(i).iterator());
        elements.add(iterators.get(i).next());
    }

    for (int i = 0; i < numberOfTuples(list); i++) {
        toRet.add(new HashSet<T>());
    }

    int setIndex = 0;
    for (Set<T> set : list) {
        int index = 0;
        for (int i = 0; i < numberOfTuples(list); i++) {
            toRet.get(index).add((T) set.toArray()[index % set.size()]);
            index++;
        }
        setIndex++;
    }
    return toRet;
}

private static <T> int numberOfTuples(List<Set<T>> list) {
    int product = 1;
    for (Set<T> set : list) {
        product *= set.size();
    }
    return product;
}
于 2009-11-12T04:01:38.467 に答える
0

これは、関数を使用して適切な出力タイプを生成するレイジーイテレータアプローチです。

public static <T> Iterable<T> cartesianProduct(
        final Function<Object[], T> fn, Object[]... options) {
    final Object[][] opts = new Object[options.length][];
    for (int i = opts.length; --i >= 0; ) {
        // NPE on null input collections, and handle the empty output case here
        // since the iterator code below assumes that it is not exhausted the
        // first time through fetch.
        if (options[i].length == 0) {
            return Collections.emptySet();
        }
        opts[i] = options[i].clone();
    }
    return new Iterable<T>() {
        public Iterator<T> iterator() {
            return new Iterator<T>() {
                final int[] pos = new int[opts.length];
                boolean hasPending;
                T pending;
                boolean exhausted;

                public boolean hasNext() {
                    fetch();
                    return hasPending;
                }

                public T next() {
                    fetch();
                    if (!hasPending) {
                        throw new NoSuchElementException();
                    }
                    T out = pending;
                    pending = null;  // release for GC
                    hasPending = false;
                    return out;
                }

                public void remove() {
                    throw new UnsupportedOperationException();
                }

                private void fetch() {
                    if (hasPending || exhausted) {
                        return;
                    }
                    // Produce a result.
                    int n = pos.length;
                    Object[] args = new Object[n];
                    for (int j = n; --j >= 0; ) {
                        args[j] = opts[j][pos[j]];
                    }
                    pending = fn.apply(args);
                    hasPending = true;
                    // Increment to next.
                    for (int i = n; --i >= 0; ) {
                        if (++pos[i] < opts[i].length) {
                            for (int j = n; --j > i; ) {
                                pos[j] = 0;
                            }
                            return;
                        }
                    }
                    exhausted = true;
                }
            };
        }
    };
}
于 2010-06-09T20:46:14.697 に答える
0

文字列のテーブルの再帰デカルト積アルゴリズムを作成しました。セットをisteadにするように変更できます。以下はアルゴリズムです。それは私の記事でも説明されています

public class Main {
    public static void main(String[] args) {
        String[] A = new String[]{"a1", "a2", "a3"};
        String[] B = new String[]{"b1", "b2", "b3"};
        String[] C = new String[]{"c1"};

        String[] cp = CartesianProduct(0, A, B, C);

        for (String s : cp) {
            System.out.println(s);
        }
    }

    public static String[] CartesianProduct(int prodLevel, String[] res, String[]... s) {
        if (prodLevel < s.length) {
            int cProdLen = res.length * s[prodLevel].length;
            String[] tmpRes = new String[cProdLen];

            for (int i = 0; i < res.length; i++) {
                for (int j = 0; j < s[prodLevel].length; j++) {
                    tmpRes[i * res.length + j] = res[i] + s[prodLevel][j];
                }
            }
            res = Main.CartesianProduct(prodLevel + 1, tmpRes, s);
        }
        return res;
    }
}
于 2011-06-10T08:11:55.707 に答える
0

メソッドを使用できますStream.reduce。

追加のライブラリなしのJava9。

public static <U> List<Set<U>> cartesianProduct(List<Set<? extends U>> sets) {
    // incorrect incoming data
    if (sets == null) return Collections.emptyList();
    return sets.stream()
            // non-null and non-empty sets
            .filter(set -> set != null && set.size() > 0)
            // represent each set element as Set<U>
            .map(set -> set.stream().map(Set::<U>of)
                    // Stream<List<Set<U>>>
                    .collect(Collectors.toList()))
            // summation of pairs of inner sets
            .reduce((set1, set2) -> set1.stream()
                    // combinations of inner sets
                    .flatMap(inner1 -> set2.stream()
                            // merge two inner sets into one
                            .map(inner2 -> Stream.of(inner1, inner2)
                                    .flatMap(Set::stream)
                                    .collect(Collectors.toSet())))
                    // list of combinations
                    .collect(Collectors.toList()))
            // List<Set<U>>
            .orElse(Collections.emptyList());
}

public static void main(String[] args) {
    Set<Integer> set1 = Set.of(1, 2);
    Set<Double> set2 = Set.of(3.0, 4.0);
    Set<Long> set3 = Set.of(5L, 6L);

    List<Set<Number>> sets = cartesianProduct(List.of(set1, set2, set3));
    // output
    sets.forEach(System.out::println);
}

出力（要素の順序は異なる場合があります）：

[1, 3.0, 5]
[1, 3.0, 6]
[1, 4.0, 5]
[1, 4.0, 6]
[2, 3.0, 5]
[2, 3.0, 6]
[2, 4.0, 5]
[2, 4.0, 6]

参照：任意の数のセットのデカルト積

于 2021-04-20T16:47:46.027 に答える