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}