दिलचस्प पोस्ट
फॉर्म पर जावास्क्रिप्ट पोस्ट सबमिट करें एक नई विंडो Windows पर एक बंदरगाह पर कौन सी प्रक्रिया सुन रही है आप यह कैसे पता लगा सकते हैं? एसक्यूएल: क्वेरी के द्वारा डिफ़ॉल्ट ऑर्डर क्या है? प्रिंट स्टेटमेंट के बाद मैं नई लाइन को कैसे दबा सकता हूं? जावास्क्रिप्ट के साथ ब्राउज़र में एंड्रॉइड फोन के रोटेशन का पता लगाएं CSS3 क्रॉस ब्राउज़र रैखिक ढाल एक रूट कंटेनर में एकाधिक ग्लासपेन को लेयर करना स्विंग में गतिशील जीयूआई कैसे कार्यान्वित करें अगर उपयोगकर्ता वर्तमान पृष्ठ पर सक्रिय है तो मैं जावास्क्रिप्ट / jQuery के साथ कैसे पता लगा सकता हूं? आइफ्रेम में सामग्री सम्मिलित करें Windows के तहत मेरे पासफ़्रेज़ को क्यों नहीं Git याद कर सकता है पायथन स्ट्रिंग और पूर्णांक सम्मिलन UIImagePickerController स्थिति बार उपस्थिति टूटता है शब्दकोशों की गहरी प्रतिलिपि Xcode 4.2 में विश्लेषण त्रुटि देता है 'उपयोगकर्ता परिभाषित प्रकार निर्धारित नहीं' त्रुटि

जावा में सेट के एक पावरसेट प्राप्त करना

{1, 2, 3} की शक्तियां इस प्रकार हैं:

{{}, {2}, {3}, {2, 3}, {1, 2}, {1, 3}, {1, 2, 3}, {1}}

मान लें कि मेरे पास जावा में एक Set है:

 Set<Integer> mySet = new HashSet<Integer>(); mySet.add(1); mySet.add(2); mySet.add(3); Set<Set<Integer>> powerSet = getPowerset(mySet); 

जटिलता के सर्वोत्तम संभव क्रम के साथ, मैं समारोह getPowerset कैसे लिख सकता हूं? (मुझे लगता है कि यह ओ (2 ^ एन) हो सकता है।)

वेब के समाधान से एकत्रित समाधान "जावा में सेट के एक पावरसेट प्राप्त करना"

हाँ, यह O(2^n) वास्तव में, क्योंकि आपको उत्पन्न करने की आवश्यकता है, ठीक है, 2^n संभव संयोजन। जेनेरिक और सेट्स का उपयोग करते हुए यहां एक कार्यान्वयन कार्यान्वयन है:

 public static <T> Set<Set<T>> powerSet(Set<T> originalSet) { Set<Set<T>> sets = new HashSet<Set<T>>(); if (originalSet.isEmpty()) { sets.add(new HashSet<T>()); return sets; } List<T> list = new ArrayList<T>(originalSet); T head = list.get(0); Set<T> rest = new HashSet<T>(list.subList(1, list.size())); for (Set<T> set : powerSet(rest)) { Set<T> newSet = new HashSet<T>(); newSet.add(head); newSet.addAll(set); sets.add(newSet); sets.add(set); } return sets; } 

और एक परीक्षण, आपके उदाहरण के इनपुट को दिया गया है:

  Set<Integer> mySet = new HashSet<Integer>(); mySet.add(1); mySet.add(2); mySet.add(3); for (Set<Integer> s : SetUtils.powerSet(mySet)) { System.out.println(s); } 

असल में, मैंने कोड लिखा है जो आप ओ (1) में पूछ रहे हैं। सवाल यह है कि आप अगले सेट के साथ क्या करने की योजना बना रहे हैं यदि आप बस उस पर size() कॉल करने जा रहे हैं, तो यह ओ (1) है, लेकिन यदि आप इसे पुनरावृति करने जा रहे हैं तो यह स्पष्ट रूप से O(2^n)

contains() O(n) , आदि होगा

क्या आपको वास्तव में इसकी ज़रूरत है?

संपादित करें:

यह कोड अब गवा में उपलब्ध है , जो विधि के माध्यम से सामने आ गया है। Sets.powerSet(set)

यहाँ एक समाधान है जहां मैं एक जनरेटर का उपयोग करता हूं, लाभ होने पर, पूरी शक्ति सेट कभी भी एक बार में संग्रहीत नहीं होता है … तो आप स्मृति को संग्रहीत किए बिना इसे एक-एक करके फिर से दोहरा सकते हैं। मुझे लगता है कि यह बेहतर विकल्प है … ध्यान दें, जटिलता एक ही है, ओ (2 ^ एन), लेकिन स्मृति आवश्यकताओं को कम कर रहे हैं (कचरा कलेक्टर के व्यवहार को संभालने!;))

 /** * */ package org.mechaevil.util.Algorithms; import java.util.BitSet; import java.util.Iterator; import java.util.Set; import java.util.TreeSet; /** * @author st0le * */ public class PowerSet<E> implements Iterator<Set<E>>,Iterable<Set<E>>{ private E[] arr = null; private BitSet bset = null; @SuppressWarnings("unchecked") public PowerSet(Set<E> set) { arr = (E[])set.toArray(); bset = new BitSet(arr.length + 1); } @Override public boolean hasNext() { return !bset.get(arr.length); } @Override public Set<E> next() { Set<E> returnSet = new TreeSet<E>(); for(int i = 0; i < arr.length; i++) { if(bset.get(i)) returnSet.add(arr[i]); } //increment bset for(int i = 0; i < bset.size(); i++) { if(!bset.get(i)) { bset.set(i); break; }else bset.clear(i); } return returnSet; } @Override public void remove() { throw new UnsupportedOperationException("Not Supported!"); } @Override public Iterator<Set<E>> iterator() { return this; } } 

इसे कॉल करने के लिए, इस पैटर्न का उपयोग करें:

  Set<Character> set = new TreeSet<Character> (); for(int i = 0; i < 5; i++) set.add((char) (i + 'A')); PowerSet<Character> pset = new PowerSet<Character>(set); for(Set<Character> s:pset) { System.out.println(s); } 

यह मेरे प्रोजेक्ट ऑलर लाइब्रेरी से है … 🙂

यहां एक ट्यूटोरियल है, जिसमें कोड शामिल है, ठीक उसी प्रकार आप क्या चाहते हैं। आप सही हैं कि जटिलता ओ (2 ^ एन) है

यदि एन <63, जो उचित धारणा है, क्योंकि आप मेमोरी से बाहर निकलते हैं (जब तक कि इटरेटर कार्यान्वयन का उपयोग नहीं करते हैं) वैसे भी बिजली सेट बनाने की कोशिश कर रहे हैं, ऐसा करने के लिए यह एक अधिक संक्षिप्त तरीका है। बाइनरी ऑपरेशन Math.pow() और मास्क के लिए सरणियों की तुलना में तेज़ तेज़ है, लेकिन किसी भी तरह जावा उपयोगकर्ता उनसे डरते हैं …

 List<T> list = new ArrayList<T>(originalSet); int n = list.size(); Set<Set<T>> powerSet = new HashSet<Set<T>>(); for( long i = 0; i < (1 << n); i++) { Set<T> element = new HashSet<T>(); for( int j = 0; j < n; j++ ) if( (i >> j) % 2 == 1 ) element.add(list.get(j)); powerSet.add(element); } return powerSet; 

मैं एक और हल के साथ आया जो कि हैरी के विचारों पर आधारित है। शायद सबसे खूबसूरत नहीं है, लेकिन यहां यह जाता है जैसे कि मैं इसे समझता हूं:

चलो एसपी (एस) = {{1}, {2}, {3}} का शास्त्रीय सरल उदाहरण पावरसेट लेते हैं। हम सबसेट की संख्या 2 ^ n (7 + खाली सेट) पाने के लिए फार्मूला जानते हैं। इस उदाहरण के लिए 2 ^ 3 = 8 सबसेट्स

प्रत्येक सबसेट को खोजने के लिए हमें नीचे रूपांतरण तालिका में दिखाए गए द्विआधारी प्रतिनिधित्व के 0-7 दशमलव में रूपांतरण की आवश्यकता है:

रूपांतरण तालिका

यदि हम तालिका पंक्ति को पंक्ति से पार करते हैं, तो प्रत्येक पंक्ति के परिणामस्वरूप एक सबसेट होता है और प्रत्येक सबसेट के मान सक्षम बिट्स से आएंगे।

बिन वैल्यू खंड में प्रत्येक कॉलम मूल इनपुट सेट में अनुक्रमणिका स्थिति से मेल खाती है।

यहां मेरा कोड:

 public class PowerSet { /** * @param args */ public static void main(String[] args) { PowerSet ps = new PowerSet(); Set<Integer> set = new HashSet<Integer>(); set.add(1); set.add(2); set.add(3); for (Set<Integer> s : ps.powerSet(set)) { System.out.println(s); } } public Set<Set<Integer>> powerSet(Set<Integer> originalSet) { // Original set size eg 3 int size = originalSet.size(); // Number of subsets 2^n, eg 2^3 = 8 int numberOfSubSets = (int) Math.pow(2, size); Set<Set<Integer>> sets = new HashSet<Set<Integer>>(); ArrayList<Integer> originalList = new ArrayList<Integer>(originalSet); for (int i = 0; i < numberOfSubSets; i++) { // Get binary representation of this index eg 010 = 2 for n = 3 String bin = getPaddedBinString(i, size); //Get sub-set Set<Integer> set = getSet(bin, originalList)); sets.add(set); } return sets; } //Gets a sub-set based on the binary representation. Eg for 010 where n = 3 it will bring a new Set with value 2 private Set<Integer> getSet(String bin, List<Integer> origValues){ Set<Integer> result = new HashSet<Integer>(); for(int i = bin.length()-1; i >= 0; i--){ //Only get sub-sets where bool flag is on if(bin.charAt(i) == '1'){ int val = origValues.get(i); result.add(val); } } return result; } //Converts an int to Bin and adds left padding to zero's based on size private String getPaddedBinString(int i, int size) { String bin = Integer.toBinaryString(i); bin = String.format("%0" + size + "d", Integer.parseInt(bin)); return bin; } } 

यदि आप एक्लिप्स कलेक्शंस (पहले जीएस कलेक्शंस ) का उपयोग कर रहे हैं, तो आप सभी सेटिटेबल्स पर powerSet() विधि का उपयोग कर सकते हैं।

 MutableSet<Integer> set = UnifiedSet.newSetWith(1, 2, 3); System.out.println("powerSet = " + set.powerSet()); // prints: powerSet = [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] 

नोट: मैं एक्लिप्स संग्रह के लिए एक कंपाइटर हूं।

मैं उन समाधानों की तलाश कर रहा था जो उतने भारी नहीं थे जितना यहां पोस्ट किए गए थे। यह जावा 7 को लक्षित करता है, इसलिए इसे संस्करण 5 और 6 के लिए पेस्ट की एक मुट्ठी भर की आवश्यकता होगी।

 Set<Set<Object>> powerSetofNodes(Set<Object> orig) { Set<Set<Object>> powerSet = new HashSet<>(), runSet = new HashSet<>(), thisSet = new HashSet<>(); while (powerSet.size() < (Math.pow(2, orig.size())-1)) { if (powerSet.isEmpty()) { for (Object o : orig) { Set<Object> s = new TreeSet<>(); s.add(o); runSet.add(s); powerSet.add(s); } continue; } for (Object o : orig) { for (Set<Object> s : runSet) { Set<Object> s2 = new TreeSet<>(); s2.addAll(s); s2.add(o); powerSet.add(s2); thisSet.add(s2); } } runSet.clear(); runSet.addAll(thisSet); thisSet.clear(); } powerSet.add(new TreeSet()); return powerSet; 

परीक्षण करने के लिए यहां कुछ उदाहरण कोड है:

 Set<Object> hs = new HashSet<>(); hs.add(1); hs.add(2); hs.add(3); hs.add(4); for(Set<Object> s : powerSetofNodes(hs)) { System.out.println(Arrays.toString(s.toArray())); } 

निम्नलिखित समाधान मेरी पुस्तक " कोडिंग साक्षात्कार: प्रश्न, विश्लेषण और समाधान " से लिया गया है:

एक सरणी में कुछ पूर्णांक चयनित होते हैं जो एक संयोजन का निर्माण करते हैं। बिट्स का एक सेट उपयोग किया जाता है, जहां प्रत्येक बिट सरणी में एक पूर्णांक के लिए खड़ा होता है। यदि i-th वर्ण को एक संयोजन के लिए चुना जाता है, तो i-th bit 1 है; अन्यथा, यह 0 है। उदाहरण के लिए, तीन बिट्स को सरणी के संयोजन के लिए उपयोग किया जाता है [1, 2, 3]। यदि पहले दो पूर्णांक 1 और 2 को संयोजन [1, 2] लिखने के लिए चुना जाता है, तो संबंधित बिट्स {1, 1, 0} हैं। इसी प्रकार, दूसरे संयोजन [1, 3] से संबंधित बिट्स {1, 0, 1} हैं। यदि हम n बिट्स के सभी संभव संयोजनों को प्राप्त कर सकते हैं, तो हम लंबाई के साथ एक सरणी के सभी संयोजनों को प्राप्त कर सकते हैं।

एक संख्या बिट्स के एक सेट से बना है एन बिट्स के सभी संभव संयोजन 1 से 2 ^ n -1 के नंबर के अनुरूप हैं। इसलिए, 1 और 2 के बीच की श्रेणी में प्रत्येक संख्या, एन -1, लंबाई एन के साथ एक सरणी के संयोजन से मेल खाती है उदाहरण के लिए, संख्या 6 बिट्स {1, 1, 0} से बना है, इसलिए संयोजन को उत्पन्न करने के लिए [1, 2, 3] सरणी में पहला और दूसरा अक्षर चुना जाता है [1, 2] इसी प्रकार, बीट्स {1, 0, 1} के साथ संख्या 5 संयोजन [1, 3] से मेल खाती है।

इस समाधान को लागू करने के लिए जावा कोड नीचे जैसा दिखता है:

 public static ArrayList<ArrayList<Integer>> powerSet(int[] numbers) { ArrayList<ArrayList<Integer>> combinations = new ArrayList<ArrayList<Integer>>(); BitSet bits = new BitSet(numbers.length); do{ combinations.add(getCombination(numbers, bits)); }while(increment(bits, numbers.length)); return combinations; } private static boolean increment(BitSet bits, int length) { int index = length - 1; while(index >= 0 && bits.get(index)) { bits.clear(index); --index; } if(index < 0) return false; bits.set(index); return true; } private static ArrayList<Integer> getCombination(int[] numbers, BitSet bits){ ArrayList<Integer> combination = new ArrayList<Integer>(); for(int i = 0; i < numbers.length; ++i) { if(bits.get(i)) combination.add(numbers[i]); } return combination; } 

विधि वेतन वृद्धि बिट्स के सेट में एक संख्या को दर्शाता है। एल्गोरिथ्म 1 बिट्स को बराबर से 1 बिट निकालता है जब तक कि 0 बिट नहीं मिल जाता। यह तब 1 के बराबर 0 सेट करता है। उदाहरण के लिए, बिट्स {1, 0, 1} के साथ संख्या 5 को बढ़ाने के लिए, यह दाईं ओर से 1 बिट को साफ करता है और सहीतम 0 बिट से 1 सेट करता है। बिट्स बन जाते हैं संख्या 1 के लिए {1, 1, 0}, जो 5 से 1 तक बढ़ने का परिणाम है

ऊपर दिए गए कुछ समाधान ग्रस्त हैं जब सेट का आकार बड़ा हो जाता है क्योंकि वे एकत्र किए जाने वाले ऑब्जेक्ट कचरा बना रहे हैं और डेटा की प्रतिलिपि बनाने की आवश्यकता है। हम इससे कैसे बच सकते हैं? हम इस तथ्य का लाभ उठा सकते हैं कि हम जानते हैं कि परिणाम कितना बड़ा आकार निर्धारित होगा (2 ^ n), उस सरणी को बड़ा करें, और उसके अंत में संलग्न करें, प्रतिलिपि न करें।

स्पीडअप एन के साथ जल्दी से बढ़ता है मैंने इसके तुलना ऊपर ज़ोआ सिल्वा के समाधान से की। मेरी मशीन पर (सभी माप अनुमानित), एन = 13 5x तेज है, एन = 14 है 7x, n = 15 है 12x, n = 16 25x, n = 17 है 75x, n = 18 140x है। इसलिए कचरा निर्माण / संग्रह और प्रतिलिपि हावी है जो अन्यथा समान बड़े-ओ समाधान होने लगते हैं।

शुरुआत में सरणी को आवंटित करना यह गतिशील रूप से बढ़ने की तुलना में एक जीत की तरह दिखाई देता है एन = 18 के साथ, गतिशील बढ़ते हुए कुल मिलाकर दो बार लंबे समय तक लेते हैं।

 public static <T> List<List<T>> powerSet(List<T> originalSet) { // result size will be 2^n, where n=size(originalset) // good to initialize the array size to avoid dynamic growing int resultSize = (int) Math.pow(2, originalSet.size()); // resultPowerSet is what we will return List<List<T>> resultPowerSet = new ArrayList<List<T>>(resultSize); // Initialize result with the empty set, which powersets contain by definition resultPowerSet.add(new ArrayList<T>(0)); // for every item in the original list for (T itemFromOriginalSet : originalSet) { // iterate through the existing powerset result // loop through subset and append to the resultPowerset as we go // must remember size at the beginning, before we append new elements int startingResultSize = resultPowerSet.size(); for (int i=0; i<startingResultSize; i++) { // start with an existing element of the powerset List<T> oldSubset = resultPowerSet.get(i); // create a new element by adding a new item from the original list List<T> newSubset = new ArrayList<T>(oldSubset); newSubset.add(itemFromOriginalSet); // add this element to the result powerset (past startingResultSize) resultPowerSet.add(newSubset); } } return resultPowerSet; } 

यहां एक आसान पुनरावृत्ति ओ (2 ^ एन) समाधान है:

 public static Set<Set<Integer>> powerSet(List<Integer> intList){ Set<Set<Integer>> result = new HashSet(); result.add(new HashSet()); for (Integer i : intList){ Set<Set<Integer>> temp = new HashSet(); for(Set<Integer> intSet : result){ intSet = new HashSet(intSet); intSet.add(i); temp.add(intSet); } result.addAll(temp); } return result; } 
 import java.util.Set; import com.google.common.collect.*; Set<Set<Integer>> sets = Sets.powerSet(ImmutableSet.of(1, 2, 3)); 

यदि एस N तत्वों के साथ एक परिमित सेट है, तो एस के पावर सेट में 2 ^ N तत्व होते हैं केवल शक्तियों के तत्वों की गणना करने का समय 2 ^ एन है, इसलिए O(2^N) पावरसेट के निर्माण की समय जटिलता (बेसब्री से) पर कम है।

बस रखो, कोई भी गणना जो शक्तियां बनाने में शामिल है N के बड़े मूल्यों के लिए पैमाने पर नहीं जा रहा है। कोई चालाक एल्गोरिथ्म आपकी मदद करेगा … शक्तियों को बनाने की आवश्यकता से बचने के अलावा!

रिकर्सन के बिना एक तरीका निम्न है: एक बाइनरी मुखौटा का उपयोग करें और सभी संभव संयोजन करें।

 public HashSet<HashSet> createPowerSet(Object[] array) { HashSet<HashSet> powerSet=new HashSet(); boolean[] mask= new boolean[array.length]; for(int i=0;i<Math.pow(2, array.length);i++) { HashSet set=new HashSet(); for(int j=0;j<mask.length;j++) { if(mask[i]) set.add(array[j]); } powerSet.add(set); increaseMask(mask); } return powerSet; } public void increaseMask(boolean[] mask) { boolean carry=false; if(mask[0]) { mask[0]=false; carry=true; } else mask[0]=true; for(int i=1;i<mask.length;i++) { if(mask[i]==true && carry==true) mask[i]=false; else if (mask[i]==false && carry==true) { mask[i]=true; carry=false; } else break; } } 

कलन विधि:

इनपुट: सेट [], सेट_आइज 1. पावर सेट का आकार पावर_सेट_आकार = पाउ (2, सेट_आइज़) 2 से 0 से पॉव_सेट_सिस के लिए लूप (ए) लूप i = 0 से set_size (i) अगर काउंटर में ith बिट है इस सबसेट के लिए सेट से प्रिंट आईथ एलीमेंट सेट करें (बी) सबसेट्स के लिए प्रिंट सेपरेटर यानी, न्यूलाइन

 #include <stdio.h> #include <math.h> void printPowerSet(char *set, int set_size) { /*set_size of power set of a set with set_size n is (2**n -1)*/ unsigned int pow_set_size = pow(2, set_size); int counter, j; /*Run from counter 000..0 to 111..1*/ for(counter = 0; counter < pow_set_size; counter++) { for(j = 0; j < set_size; j++) { /* Check if jth bit in the counter is set If set then pront jth element from set */ if(counter & (1<<j)) printf("%c", set[j]); } printf("\n"); } } /*Driver program to test printPowerSet*/ int main() { char set[] = {'a','b','c'}; printPowerSet(set, 3); getchar(); return 0; } 

यह मेरा पुनरावर्ती समाधान है जो जावा जेनेरिक्स का उपयोग करके किसी भी सेट की शक्ति सेट प्राप्त कर सकता है। इसका मुख्य विचार है इनपुट सरणी के सिर को शेष सरणी के सभी संभव समाधानों से जोड़ना।

 import java.util.LinkedHashSet; import java.util.Set; public class SetUtil { private static<T> Set<Set<T>> combine(T head, Set<Set<T>> set) { Set<Set<T>> all = new LinkedHashSet<>(); for (Set<T> currentSet : set) { Set<T> outputSet = new LinkedHashSet<>(); outputSet.add(head); outputSet.addAll(currentSet); all.add(outputSet); } all.addAll(set); return all; } //Assuming that T[] is an array with no repeated elements ... public static<T> Set<Set<T>> powerSet(T[] input) { if (input.length == 0) { Set <Set<T>>emptySet = new LinkedHashSet<>(); emptySet.add(new LinkedHashSet<T>()); return emptySet; } T head = input[0]; T[] newInputSet = (T[]) new Object[input.length - 1]; for (int i = 1; i < input.length; ++i) { newInputSet[i - 1] = input[i]; } Set<Set<T>> all = combine(head, powerSet(newInputSet)); return all; } public static void main(String[] args) { Set<Set<Integer>> set = SetUtil.powerSet(new Integer[] {1, 2, 3, 4, 5, 6}); System.out.println(set); } } 

यह आउटपुट होगा:

 [[1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5], [1, 2, 3, 4, 6], [1, 2, 3, 4], [1, 2, 3, 5, 6], [1, 2, 3, 5], [1, 2, 3, 6], [1, 2, 3], [1, 2, 4, 5, 6], [1, 2, 4, 5], [1, 2, 4, 6], [1, 2, 4], [1, 2, 5, 6], [1, 2, 5], [1, 2, 6], [1, 2], [1, 3, 4, 5, 6], [1, 3, 4, 5], [1, 3, 4, 6], [1, 3, 4], [1, 3, 5, 6], [1, 3, 5], [1, 3, 6], [1, 3], [1, 4, 5, 6], [1, 4, 5], [1, 4, 6], [1, 4], [1, 5, 6], [1, 5], [1, 6], [1], [2, 3, 4, 5, 6], [2, 3, 4, 5], [2, 3, 4, 6], [2, 3, 4], [2, 3, 5, 6], [2, 3, 5], [2, 3, 6], [2, 3], [2, 4, 5, 6], [2, 4, 5], [2, 4, 6], [2, 4], [2, 5, 6], [2, 5], [2, 6], [2], [3, 4, 5, 6], [3, 4, 5], [3, 4, 6], [3, 4], [3, 5, 6], [3, 5], [3, 6], [3], [4, 5, 6], [4, 5], [4, 6], [4], [5, 6], [5], [6], []] 

यह लम्ब्दास के साथ मेरा दृष्टिकोण है

 public static <T> Set<Set<T>> powerSet(T[] set) { return IntStream .range(0, (int) Math.pow(2, set.length)) .parallel() //performance improvement .mapToObj(e -> IntStream.range(0, set.length).filter(i -> (e & (0b1 << i)) != 0).mapToObj(i -> set[i]).collect(Collectors.toSet())) .map(Function.identity()) .collect(Collectors.toSet()); } 

या समानांतर में (समांतर () टिप्पणी देखें):

इनपुट सेट का आकार: 18

तार्किक प्रोसेसर: 8 ए 3.4GHz

प्रदर्शन सुधार: 30%

 // input: S // output: P // S = [1,2] // P = [], [1], [2], [1,2] public static void main(String[] args) { String input = args[0]; String[] S = input.split(","); String[] P = getPowerSet(S); if (P.length == Math.pow(2, S.length)) { for (String s : P) { System.out.print("[" + s + "],"); } } else { System.out.println("Results are incorrect"); } } private static String[] getPowerSet(String[] s) { if (s.length == 1) { return new String[] { "", s[0] }; } else { String[] subP1 = getPowerSet(Arrays.copyOfRange(s, 1, s.length)); String[] subP2 = new String[subP1.length]; for (int i = 0; i < subP1.length; i++) { subP2[i] = s[0] + subP1[i]; } String[] P = new String[subP1.length + subP2.length]; System.arraycopy(subP1, 0, P, 0, subP1.length); System.arraycopy(subP2, 0, P, subP1.length, subP2.length); return P; } } 

मुझे हाल ही में इस तरह से कुछ का उपयोग करना पड़ा, लेकिन सबसे छोटी उपब्बिलियों (1 तत्व के साथ, फिर 2 तत्व, …) पहले की आवश्यकता थी। मैं रिक्त न ही पूरी सूची को शामिल करना नहीं चाहता था इसके अलावा, मुझे सभी सुब्बिलिस्टों की सूची की ज़रूरत नहीं थी, मुझे प्रत्येक के साथ कुछ सामान बनाने की ज़रूरत थी

यह पुनरावर्ती किए बिना करना था, और निम्नलिखित के साथ आया ("कार्य करना" एक कार्यात्मक इंटरफ़ेस में समतल):

 @FunctionalInterface interface ListHandler<T> { void handle(List<T> list); } public static <T> void forAllSubLists(final List<T> list, ListHandler handler) { int ll = list.size(); // Length of original list int ci[] = new int[ll]; // Array for list indices List<T> sub = new ArrayList<>(ll); // The sublist List<T> uml = Collections.unmodifiableList(sub); // For passing to handler for (int gl = 1, gm; gl <= ll; gl++) { // Subgroup length 1 .. n-1 gm = 0; ci[0] = -1; sub.add(null); // Some inits, and ensure sublist is at least gl items long do { ci[gm]++; // Get the next item for this member if (ci[gm] > ll - gl + gm) { // Exhausted all possibilities for this position gm--; continue; // Continue with the next value for the previous member } sub.set(gm, list.get(ci[gm])); // Set the corresponding member in the sublist if (gm == gl - 1) { // Ok, a sublist with length gl handler.handle(uml); // Handle it } else { ci[gm + 1] = ci[gm]; // Starting value for next member is this gm++; // Continue with the next member } } while (gm >= 0); // Finished cycling through all possibilities } // Next subgroup length } 

इस तरह, विशिष्ट लंबाई के सुब्बिलिस्ट को इसे सीमित करना भी आसान है।

एक अन्य नमूना कार्यान्वयन:

  public static void main(String args[]) { int[] arr = new int[]{1,2,3,4}; // Assuming that number of sets are in integer range int totalSets = (int)Math.pow(2,arr.length); for(int i=0;i<totalSets;i++) { String binaryRep = Integer.toBinaryString(i); for(int j=0;j<binaryRep.length();j++) { int index=binaryRep.length()-1-j; if(binaryRep.charAt(index)=='1') System.out.print(arr[j] +" "); } System.out.println(); } } 
 public class PowerSet { public static List<HashSet<Integer>> powerset(int[] a) { LinkedList<HashSet<Integer>> sets = new LinkedList<HashSet<Integer>>(); int n = a.length; for (int i = 0; i < 1 << n; i++) { HashSet<Integer> set = new HashSet<Integer>(); for (int j = 0; j < n; j++) { if ((1 << j & i) > 0) set.add(a[j]); } sets.add(set); } return sets; } public static void main(String[] args) { List<HashSet<Integer>> sets = PowerSet.powerset(new int[]{ 1, 2, 3 }); for (HashSet<Integer> set : sets) { for (int i : set) System.out.print(i); System.out.println(); } } } 

अभी तक एक और हल – जावा 8 + स्ट्रीमिंग एपीआई के साथ यह आलसी है और आदेश दिया जाता है ताकि यह सही उपगट देता है जब इसे "सीमा ()" के साथ प्रयोग किया जाता है

  public long bitRangeMin(int size, int bitCount){ BitSet bs = new BitSet(size); bs.set(0, bitCount); return bs.toLongArray()[0]; } public long bitRangeMax(int size, int bitCount){ BitSet bs = BitSet.valueOf(new long[]{0}); bs.set(size - bitCount, size); return bs.toLongArray()[0]; } public <T> Stream<List<T>> powerSet(Collection<T> data) { List<T> list = new LinkedHashSet<>(data).stream().collect(Collectors.toList()); Stream<BitSet> head = LongStream.of(0).mapToObj( i -> BitSet.valueOf(new long[]{i})); Stream<BitSet> tail = IntStream.rangeClosed(1, list.size()) .boxed() .flatMap( v1 -> LongStream.rangeClosed( bitRangeMin(list.size(), v1), bitRangeMax(list.size(), v1)) .mapToObj(v2 -> BitSet.valueOf(new long[]{v2})) .filter( bs -> bs.cardinality() == v1)); return Stream.concat(head, tail) .map( bs -> bs .stream() .mapToObj(list::get) .collect(Collectors.toList())); } 

और क्लाइंट कोड है

 @Test public void testPowerSetOfGivenCollection(){ List<Character> data = new LinkedList<>(); for(char i = 'a'; i < 'a'+5; i++ ){ data.add(i); } powerSet(data) .limit(9) .forEach(System.out::print); } 

/ * प्रिंट्स: [] [ए] [बी] [सी] [डी] [ई] [ए, बी] [ए, सी] [बी, सी] * /

हम पावर सेट को रीरसन के उपयोग के साथ या बिना लिख ​​सकते हैं यहां पुनरावर्ती के बिना एक प्रयास है:

 public List<List<Integer>> getPowerSet(List<Integer> set) { List<List<Integer>> powerSet = new ArrayList<List<Integer>>(); int max = 1 << set.size(); for(int i=0; i < max; i++) { List<Integer> subSet = getSubSet(i, set); powerSet.add(subSet); } return powerSet; } private List<Integer> getSubSet(int p, List<Integer> set) { List<Integer> subSet = new ArrayList<Integer>(); int position = 0; for(int i=p; i > 0; i >>= 1) { if((i & 1) == 1) { subSet.add(set.get(position)); } position++; } return subSet; } 

टी का उप-सेट किसी भी सेट है जो कि टी के शून्य या अधिक तत्वों को निकालकर बनाया जा सकता है। बिना फॉर्चस्ट सबसेट उन सबसेट्स को जोड़ता है जो पहले तत्व को गुम कर रहे हैं और लूप के लिए पहले एलीमेंट्स के साथ सबसेट्स को जोड़ना होगा। उदाहरण के लिए, यदि टी में तत्वों ["1", "2", "3"] शामिल हैं, तो लापता पहले [[""], ["2"], ["3"], ["2", "3 "]] और लूप के लिए इन तत्वों के सामने" 1 "को छोडना होगा और इसे नएसेट में जोड़ देगा। इसलिए हम [[""], ["1"], ["2"], ["3"], ["1", "2"], ["1", "3"] के साथ समाप्त होंगे , ["2", "3"], ["1", "2", "3"]]

 public static Set<Set<String>> allSubsets(Set<String> t) { Set<Set<String>> powerSet = new TreeSet<>(); if(t.isEmpty()) { powerSet.add(new TreeSet<>()); return powerSet; } String first = t.get(0); Set<Set<String>> withoutFirst = allSubsets(t.subSet(1, t.size())); for (List<String> 1st : withoutFirst) { Set<String> newSet = new TreeSet<>(); newSet.add(first); newSet.addAll(lst); powerSet.add(newSet); } powerSet.addAll(withoutFirst); return powerSet; }