001/*
002 *                    BioJava development code
003 *
004 * This code may be freely distributed and modified under the
005 * terms of the GNU Lesser General Public Licence.  This should
006 * be distributed with the code.  If you do not have a copy,
007 * see:
008 *
009 *      http://www.gnu.org/copyleft/lesser.html
010 *
011 * Copyright for this code is held jointly by the individual
012 * authors.  These should be listed in @author doc comments.
013 *
014 * For more information on the BioJava project and its aims,
015 * or to join the biojava-l mailing list, visit the home page
016 * at:
017 *
018 *      http://www.biojava.org/
019 *
020 */
021package org.biojava.nbio.structure.symmetry.utils;
022
023import java.util.ArrayList;
024import java.util.LinkedHashSet;
025import java.util.List;
026import java.util.Set;
027
028import org.biojava.nbio.structure.symmetry.core.QuatSymmetryDetector;
029
030/**
031 * In mathematics, the power set (or powerset) of any set S, written P(S), is
032 * the set of all subsets of S, including the empty set and S itself.
033 * <p>
034 * Code taken from StackOverflow best answer in:
035 * http://stackoverflow.com/questions/4640034/calculating-all-of-the-subsets
036 * -of-a-set-of-numbers. HashSet changed to LinkedHashSet for the consistent order
037 * of the subsets and easier testing.
038 * <p>
039 * Currently used to calculate the possible LOCAL symmetries in
040 * {@link QuatSymmetryDetector}.
041 *
042 * @author Aleix Lafita
043 * @since 5.0.0
044 *
045 */
046public class PowerSet<T> {
047
048        public PowerSet() {
049        }
050
051        /**
052         * @return the set of power Sets of the original Set
053         */
054        public Set<Set<T>> powerSet(Set<T> originalSet) {
055                Set<Set<T>> sets = new LinkedHashSet<Set<T>>();
056                if (originalSet.isEmpty()) {
057                        sets.add(new LinkedHashSet<T>());
058                        return sets;
059                }
060                List<T> list = new ArrayList<T>(originalSet);
061                T head = list.get(0);
062                Set<T> rest = new LinkedHashSet<T>(list.subList(1, list.size()));
063                for (Set<T> set : powerSet(rest)) {
064                        Set<T> newSet = new LinkedHashSet<T>();
065                        newSet.add(head);
066                        newSet.addAll(set);
067                        sets.add(newSet);
068                        sets.add(set);
069                }
070                return sets;
071        }
072}