在 Java 中获取唯一的集合元素对的习惯用法

Question

是否有一个标准的习惯用法来获取给定集合中每个唯一元素对的集合？

就我们的目的而言，(a,b) 的集合相当于 (b,a)，因此结果集中应该只有一个出现。

我可以看到如何使用基于配对元素实现 hashCode 和 equals() 的 Pair 类来构造这样的集合，但我想知道是否还没有更标准的方法来生成这样的集合。

Answer 1

就像你说的，一个带有 hashcode 的 Pair 类equals 实施并放置在 HashSet 中将实现您正在寻找的内容。我不知道 JDK 数据结构本身可以执行此操作。

如果你想进一步概括它，你可以创建一个 Tuple，Tuple 并基于该 Tuple 声明一个 HashSet，HashSet> ;。然后为元组类型创建更通用的 Equals/Hashcode 方法。

这是一个示例实现：

final class Pair<A, B> {
    private final A _first;
    private final B _second;

    public Pair(A first, B second) {
        _first = first;
        _second = second;
    }

    @Override
    public int hashCode() {
        int hashFirst = _first != null ? _first.hashCode() : 0;
        int hashSecond = _second != null ? _second.hashCode() : 0;
        return (hashFirst + hashSecond) * hashSecond + hashFirst;
    }

    @Override
    @SuppressWarnings("unchecked")
    public boolean equals(Object other) {
        if (other instanceof Pair) {
            Pair otherPair = (Pair) other;
            return this._first == otherPair._first //
                    || (this._first != null //
                            && otherPair._first != null && this._first.equals(otherPair._first)) //

                    && this._second == otherPair._second //
                    || (this._second != null //
                            && otherPair._second != null && this._second.equals(otherPair._second));
        }
        return false;
    }

    @Override
    public String toString() {
        return "(" + _first + ", " + _second + ")"; 
    }

    public A getFirst() {
        return _first;
    }

    public B getSecond() {
        return _second;
    }

Answer 2

我为您创建了一个“惰性”实现，更通用一些（即可以列出任何大小的子集）。

它是懒惰的，因为不需要同时在内存中存储原始集合（或所有子集）的所有元素，但它并不是真正高效：在迭代器上调用 next() 仍然可以意味着迭代原始集合k-1次（如果k是想要的子集大小） - 幸运的是不是每次，大多数时候我们只需要一个一个迭代器上的 next()（至少当 k 与基集的大小 n 相比较小时）。当然，我们仍然需要在内存中保留子集的 k 个元素。

我们还必须假设所有迭代器都使用相同的顺序，只要底层集合不改变（并且我们不希望它在迭代之一正在进行时发生改变）。如果 Iterator 接口允许克隆迭代器，即在第一个迭代器当前所在的位置启动第二个迭代器，那么这会容易得多。 （我们现在使用 scrollTo 方法实现这一点。）对于排序的地图，这应该更容易（等待那里的更新）。

package de.fencing_game.paul.examples;

import java.util.*;

/**
 * An unmodifiable set of all subsets of a given size of a given (finite) set.
 *
 * Inspired by http://stackoverflow.com/questions/5428417/idiom-for-getting-unique-pairs-of-collection-elements-in-java
 */
public class FiniteSubSets<X>
    extends AbstractSet<Set<X>> {

    private final Set<X> baseSet;
    private final int subSize;

    /**
     * creates a set of all subsets of a given size of a given set.
     * 
     * @param baseSet the set whose subsets should be in this set.
     * For this to work properly, the baseSet's iterators should iterate
     * every time in the same order, as long as one iteration of this set
     * is in progress.
     *
     * The baseSet does not need to be immutable, but it should not change
     * while an iteration of this set is in progress.
     * @param subSetSize
     */
    public FiniteSubSets(Set<X> baseSet, int subSetSize) {
        this.baseSet = baseSet;
        this.subSize = subSetSize;
    }

    /**
     * calculates the size of this set.
     *
     * This is the binomial coefficient.
     */
    public int size() {
        int baseSize = baseSet.size();
        long size = binomialCoefficient(baseSize, subSize);
        return (int)Math.min(size, Integer.MAX_VALUE);
    }

    public Iterator<Set<X>> iterator() {
        if(subSize == 0) {
            // our IteratorImpl does not work for k == 0.
            return Collections.singleton(Collections.<X>emptySet()).iterator();
        }
        return new IteratorImpl();
    }

    /**
     * checks if some object is in this set.
     *
     * This implementation is optimized compared to 
     * the implementation from AbstractSet.
     */
    public boolean contains(Object o) {
        return o instanceof Set && 
            ((Set)o).size() == subSize &&
            baseSet.containsAll((Set)o);
    }


    /**
     * The implementation of our iterator.
     */
    private class IteratorImpl implements Iterator<Set<X>> {

        /**
         * A stack of iterators over the base set.
         * We only ever manipulate the top one, the ones below only
         * after the top one came to its end.
         * The stack should be always full, except in the constructor or
         * inside the {@link #step} method.
         */
        private Deque<Iterator<X>> stack = new ArrayDeque<Iterator<X>>(subSize);
        /**
         * a linked list maintaining the current state of the iteration, i.e.
         * the next subset. It is null when there is no next subset, but
         * otherwise it should have always full length subSize (except when
         * inside step method or constructor).
         */
        private Node current;

        /**
         * constructor to create the stack of iterators and initial
         * node.
         */
        IteratorImpl() {
            try {
                for(int i = 0; i < subSize; i++) {
                    initOneIterator();
                }
            }
            catch(NoSuchElementException ex) {
                current = null;
            }
            //      System.err.println("IteratorImpl() End, current: " + current);
        }

        /**
         * initializes one level of iterator and node.
         * Only called from the constructor.
         */
        private void initOneIterator() {
            Iterator<X> it = baseSet.iterator();
            if(current != null) {
                scrollTo(it, current.element);
            }

            X element = it.next();
            current = new Node(current, element);
            stack.push(it);
        }

        /**
         * gets the next element from the set (i.e. the next
         * subset of the base set).
         */
        public Set<X> next() {
            if(current == null) {
                throw new NoSuchElementException();
            }
            Set<X> result = new SubSetImpl(current);
            step();
            return result;
        }

        /**
         * returns true if there are more elements.
         */
        public boolean hasNext() {
            return current != null;
        }

        /** throws an exception. */
        public void remove() {
            throw new UnsupportedOperationException();
        }


        /**
         * Steps the iterator on the top of the stack to the
         * next element, and store this in {@link #current}.
         *
         * If this iterator is already the end, we recursively
         * step the iterator to the next element.
         *
         * If there are no more subsets at all, we set {@link #current}
         * to null.
         */
        void step() {
            Iterator<X> lastIt = stack.peek();
            current = current.next;
            while(!lastIt.hasNext()) {
                if(current == null) {
                    // no more elements in the first level iterator
                    // ==> no more subsets at all.
                    return;
                }

                // last iterator has no more elements
                // step iterator before and recreate last iterator.
                stack.pop();
                assert current != null;
                step();
                if(current == null) {
                    // after recursive call ==> at end of iteration.
                    return;
                }
                assert current != null;

                // new iterator at the top level
                lastIt = baseSet.iterator();
                if(!scrollTo(lastIt, current.element)) {
                    // Element not available anymore => some problem occured
                    current = null;
                    throw new ConcurrentModificationException
                        ("Element " + current.element + " not found!");
                }
                stack.push(lastIt);
            }
            // now we know the top iterator has more elements
            // ==> put the next one in `current`.

            X lastElement = lastIt.next();
            current = new Node(current, lastElement);

        }  // step()

    }

    /**
     * helper method which scrolls an iterator to some element.
     * @return true if the element was found, false if we came
     *    to the end of the iterator without finding the element.
     */
    private static <Y> boolean scrollTo(Iterator<? extends Y> it, Y element) {
        while(it.hasNext()) {
            Y itEl = it.next();
            if(itEl.equals(element)) {
                return true;
            }
        }
        return false;
    }

    /**
     * implementation of our subsets.
     * These sets are really immutable (not only unmodifiable).
     *
     * We implement them with a simple linked list of nodes.
     */
    private class SubSetImpl extends AbstractSet<X>
    {
        private final Node node;

        SubSetImpl(Node n) {
            this.node = n;
        }

        /**
         * the size of this set.
         */
        public int size() {
            return subSize;
        }

        /**
         * an iterator over our linked list.
         */
        public Iterator<X> iterator() {
            return new Iterator<X>() {
                private Node current = SubSetImpl.this.node;
                public X next() {
                    if(current == null) {
                        throw new NoSuchElementException();
                    }
                    X result = current.element;
                    current = current.next;
                    return result;
                }
                public boolean hasNext() {
                    return current != null;
                }
                public void remove() {
                    throw new UnsupportedOperationException();
                }
            };
        }
    }

    /**
     * A simple immutable node class, used to implement our iterator and
     * the sets created by them.
     *
     * Two "neighbouring" subsets (i.e. which
     * only differ by the first element) share most of the linked list,
     * differing only in the first node.
     */
    private class Node {
        Node(Node n, X e) {
            this.next = n;
            this.element = e;
        }

        final X element;
        final Node next;

        public String toString() {
            return "[" + element + "]==>" + next;
        }
    }

    /**
     * Calculates the binomial coefficient B(n,k), i.e.
     * the number of subsets of size k in a set of size n.
     *
     * The algorithm is taken from the <a href="http://de.wikipedia.org/wiki/Binomialkoeffizient#Algorithmus_zur_effizienten_Berechnung">german wikipedia article</a>.
     */
    private static long binomialCoefficient(int n, int k) {
        if(k < 0 || n < k ) {
            return 0;
        }
        final int n_minus_k = n - k;
        if (k > n/2) {
            return binomialCoefficient(n, n_minus_k);
        }
        long prod = 1;
        for(int i = 1; i <= k; i++) {
            prod = prod * (n_minus_k + i) / i;
        }
        return prod;
    }


    /**
     * Demonstrating test method. We print all subsets (sorted by size) of
     * a set created from the command line parameters, or an example set, if
     * there are no parameters.
     */
    public static void main(String[] params) {
        Set<String> baseSet =
            new HashSet<String>(params.length == 0 ?
                                Arrays.asList("Hello", "World", "this",
                                              "is", "a", "Test"):
                                Arrays.asList(params));


        System.out.println("baseSet: " + baseSet);

        for(int i = 0; i <= baseSet.size()+1; i++) {
            Set<Set<String>> pSet = new FiniteSubSets<String>(baseSet, i);
            System.out.println("------");
            System.out.println("subsets of size "+i+":");
            int count = 0;
            for(Set<String> ss : pSet) {
                System.out.println("    " +  ss);
                count++;
            }
            System.out.println("in total: " + count + ", " + pSet.size());
        }
    }


}

与往常一样，对于我在这里的更大的代码示例，这个 在我的 github 存储库 stackoverflow-examples 中也可以找到。