Zestaw uprawnień {1, 2, 3}to:
{{}, {2}, {3}, {2, 3}, {1, 2}, {1, 3}, {1, 2, 3}, {1}}
Powiedzmy, że mam Setw Javie:
Set<Integer> mySet = new HashSet<Integer>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
Set<Set<Integer>> powerSet = getPowerset(mySet);
Jak napisać funkcję getPowerset w możliwie najlepszej kolejności? (Myślę, że to może być O (2 ^ n).)
Odpowiedzi:
Tak, O(2^n)rzeczywiście, ponieważ musisz wygenerować, cóż, 2^nmożliwe kombinacje. Oto działająca implementacja, korzystająca z typów ogólnych i zestawów:
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;
}
I test, biorąc pod uwagę przykładowe dane wejściowe:
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);
}
O(2^n)? To liczba zestawów w zestawie potęgowym, ale każdy zestaw musi być utworzony w pamięci, co zajmuje czas proporcjonalny co najmniej do rozmiaru zestawu. Według wolfram alpha, jest w O(n * 2^n): wolfram alpha query
Właściwie to napisałem kod, który robi to, o co prosisz w O (1). Pytanie brzmi, co planujesz zrobić z zestawem w następnej kolejności. Jeśli zamierzasz to wywołać size(), to jest O (1), ale jeśli zamierzasz to powtórzyć, to oczywiście O(2^n).
contains()byłoby O(n)itp.
Czy naprawdę tego potrzebujesz?
EDYTOWAĆ:
Ten kod jest teraz dostępny w Guava , ujawniony za pomocą metody Sets.powerSet(set).
Oto rozwiązanie, w którym używam generatora, a zaletą jest to, że cały zestaw mocy nigdy nie jest przechowywany na raz ... Więc możesz iterować go jeden po drugim, bez konieczności przechowywania go w pamięci. Chciałbym pomyśleć, że to lepsza opcja ... Zauważ, że złożoność jest taka sama, O (2 ^ n), ale wymagania dotyczące pamięci są zmniejszone (zakładając, że zbieracz śmieci zachowuje się!;))
/**
*
*/
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;
}
}
Aby to nazwać, użyj tego wzoru:
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);
}
To z mojej biblioteki projektu Euler ... :)
Jeśli n <63, co jest rozsądnym założeniem, ponieważ zabraknie Ci pamięci (chyba że użyjesz implementacji iteratora), próbując mimo wszystko skonstruować zestaw potęg, jest to bardziej zwięzły sposób zrobienia tego. Operacje binarne są znacznie szybsze niż Math.pow()tablice masek, ale jakoś użytkownicy Javy się ich boją ...
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;
i < (1 << n)który jest odpowiednikiem.
((i >> j) &1) == 1zamiast tego (i >> j) % 2 == 1 można użyć. Są również longpodpisane, więc czy uważasz, że sprawdzenie przepełnienia ma sens?
Oto samouczek opisujący dokładnie to, czego chcesz, w tym kod. Masz rację w tym, że złożoność wynosi O (2 ^ n).
Wymyśliłem inne rozwiązanie oparte na pomysłach @Harry He's. Chyba nie najbardziej eleganckie, ale tak jest, jak rozumiem:
Weźmy klasyczny, prosty przykład PowerSet z SP (S) = {{1}, {2}, {3}}. Znamy wzór na liczbę podzbiorów 2 ^ n (7 + pusty zbiór). W tym przykładzie 2 ^ 3 = 8 podzbiorów.
Aby znaleźć każdy podzbiór, musimy przekonwertować liczbę dziesiętną 0-7 na reprezentację binarną przedstawioną w poniższej tabeli konwersji:
Jeśli przejdziemy przez tabelę wiersz po wierszu, każdy wiersz da w wyniku podzbiór, a wartości każdego podzbioru będą pochodzić z włączonych bitów.
Każda kolumna w sekcji Bin Value odpowiada pozycji indeksu w oryginalnym zestawie wejściowym.
Tutaj mój kod:
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 e.g. 3
int size = originalSet.size();
// Number of subsets 2^n, e.g 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 e.g. 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. E.g. 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;
}
}
Jeśli używasz kolekcji Eclipse (dawniej kolekcji GS ), możesz użyć tej powerSet()metody na wszystkich SetIterables.
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]]
Uwaga: jestem promotorem Eclipse Collections.
Szukałem rozwiązania, które nie byłoby tak duże, jak te zamieszczone tutaj. Jest to przeznaczone dla Java 7, więc będzie wymagać kilku past dla wersji 5 i 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;
Oto przykładowy kod do przetestowania:
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()));
}
Niektóre z powyższych rozwiązań cierpią, gdy rozmiar zestawu jest duży, ponieważ tworzą one wiele śmieci obiektów do zebrania i wymagają kopiowania danych. Jak możemy tego uniknąć? Możemy wykorzystać fakt, że wiemy, jak duży będzie rozmiar zestawu wynikowego (2 ^ n), wstępnie przydzielić tak dużą tablicę i po prostu dołączyć do jej końca, nigdy nie kopiując.
Przyspieszenie rośnie szybko z n. Porównałem to z powyższym rozwiązaniem João Silvy. Na moim komputerze (wszystkie pomiary są przybliżone), n = 13 jest 5x szybsze, n = 14 to 7x, n = 15 to 12x, n = 16 to 25x, n = 17 to 75x, n = 18 to 140x. Tak więc tworzenie / zbieranie i kopiowanie śmieci dominuje w czymś, co w innym przypadku wydaje się być podobnymi rozwiązaniami typu big-O.
Wstępne przydzielenie tablicy na początku wydaje się być wygraną w porównaniu z pozwoleniem na jej dynamiczny wzrost. Przy n = 18 dynamiczny wzrost ogólnie trwa około dwa razy dłużej.
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;
}
Następujące rozwiązanie jest zapożyczone z mojej książki „ Wywiady z kodowaniem: pytania, analiza i rozwiązania ”:
Wybrane są niektóre liczby całkowite w tablicy, które tworzą kombinację. Wykorzystywany jest zestaw bitów, gdzie każdy bit oznacza liczbę całkowitą w tablicy. Jeśli i-ty znak zostanie wybrany jako kombinacja, i-ty bit ma wartość 1; w przeciwnym razie jest to 0. Na przykład trzy bity są używane do kombinacji tablicy [1, 2, 3]. Jeśli pierwsze dwie liczby całkowite 1 i 2 zostaną wybrane w celu utworzenia kombinacji [1, 2], odpowiadające im bity to {1, 1, 0}. Podobnie bity odpowiadające innej kombinacji [1, 3] to {1, 0, 1}. Jesteśmy w stanie uzyskać wszystkie kombinacje tablicy o długości n, jeśli możemy uzyskać wszystkie możliwe kombinacje n bitów.
Liczba składa się z zestawu bitów. Wszystkie możliwe kombinacje n bitów odpowiadają liczbom od 1 do 2 ^ n -1. Dlatego każda liczba z zakresu od 1 do 2 ^ n -1 odpowiada kombinacji tablicy o długości n . Na przykład liczba 6 składa się z bitów {1, 1, 0}, więc pierwszy i drugi znak są wybierane w tablicy [1, 2, 3], aby wygenerować kombinację [1, 2]. Podobnie liczba 5 z bitami {1, 0, 1} odpowiada kombinacji [1, 3].
Kod Java do implementacji tego rozwiązania wygląda następująco:
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;
}
Inkrementacja metody zwiększa liczbę reprezentowaną w zbiorze bitów. Algorytm czyści 1 bit z prawego aż do znalezienia bitu 0. Następnie ustawia skrajny prawy 0 bit na 1. Na przykład, aby zwiększyć liczbę 5 za pomocą bitów {1, 0, 1}, czyści 1 bit z prawej strony i ustawia skrajny prawy 0 bit na 1. Bity stają się {1, 1, 0} dla liczby 6, która jest wynikiem zwiększenia 5 o 1.
Oto proste iteracyjne rozwiązanie O (2 ^ n):
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;
}
Jeśli S jest zbiorem skończonym z N elementami, to zbiór potęgowy S zawiera 2 ^ N elementów. Czas na proste wyliczenie elementów zestawu mocy wynosi 2 ^ N, więc O(2^N)jest to dolna granica złożoności czasowej (chętnie) konstruowania zestawu mocy.
Mówiąc prościej, żadne obliczenia, które obejmują tworzenie zestawów mocy, nie będą skalowane dla dużych wartości N. Żaden sprytny algorytm Ci nie pomoże ... poza unikaniem konieczności tworzenia zestawów mocy!
Jeden sposób bez rekursji jest następujący: użyj maski binarnej i wykonaj wszystkie możliwe kombinacje.
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;
}
}
Algorytm:
Wejście: Set [], set_size 1. Uzyskaj rozmiar zestawu mocy powet_set_size = pow (2, set_size) 2 Pętla licznika od 0 do pow_set_size (a) Pętla dla i = 0 do set_size (i) Jeśli i-ty bit w liczniku to set Drukuj i-ty element ze zbioru dla tego podzbioru (b) Drukuj separator dla podzbiorów, tj. znak nowej linii
#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;
}To jest moje rozwiązanie rekurencyjne, które może uzyskać zestaw mocy dowolnego zestawu za pomocą generics Java. Jego głównym zamysłem jest połączenie nagłówka tablicy wejściowej ze wszystkimi możliwymi rozwiązaniami pozostałej części tablicy w następujący sposób.
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);
}
}
Spowoduje to wyświetlenie:
[[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], []]
Kolejna przykładowa realizacja:
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();
}
}
To jest moje podejście do lambd.
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());
}
Lub równolegle (patrz komentarz parallel ()):
Rozmiar zestawu wejściowego: 18
Procesory logiczne: od 8 do 3,4 GHz
Poprawa wydajności: 30%
Podzbiór t to dowolny zbiór, który można utworzyć, usuwając zero lub więcej elementów t. Podzbiór withoutFirst dodaje podzbiory t, w których brakuje pierwszego elementu, a pętla for zajmie się dodawaniem podzbiorów z pierwszym elementem. Na przykład, jeśli t zawiera elementy ["1", "2", "3"], missingFirst doda [[""], ["2"], ["3"], ["2", "3" „]], a pętla for umieści„ 1 ”przed tymi elementami i doda je do nowego zestawu. W rezultacie otrzymamy [[""], ["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;
}
Setnie ma getmetody z indeksem ani subSetmetody; 1stnie jest prawidłowym identyfikatorem (przypuszczam, że lstmiał na myśli). Zmień wszystkie zestawy na listy i prawie się kompiluje ...
// 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;
}
}
Ostatnio musiałem użyć czegoś takiego, ale najpierw potrzebowałem najmniejszych podlist (z 1 elementem, potem 2 elementami, ...). Nie chciałem zawierać pustej ani całej listy. Nie potrzebowałem też zwracanej listy wszystkich podlist, po prostu musiałem z każdą z nich zrobić kilka rzeczy.
Chciałem to zrobić bez rekurencji i wymyśliłem co następuje (z "robieniem rzeczy" wyabstrahowanym do funkcjonalnego interfejsu):
@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
}
W ten sposób łatwo jest ograniczyć ją do podlist o określonej długości.
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();
}
}
}
Jeszcze inne rozwiązanie - z interfejsem API strumieniowania java8 + Jest leniwy i uporządkowany, więc zwraca poprawne podzbiory, gdy jest używany z "limit ()".
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()));
}
A kod klienta to
@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);
}
/ * Wydruki: [] [a] [b] [c] [d] [e] [a, b] [a, c] [b, c] * /
Moglibyśmy napisać zestaw potęg z wykorzystaniem rekurencji lub bez. Oto próba bez rekurencji:
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;
}
Tutaj jest do wygenerowania zestawu mocy. Pomysł jest pierwszy = S[0]i mniejsze zestawy S[1,...n].
Oblicz wszystkie podzbiory mniejszeSet i umieść je we wszystkich podzbiorach.
Dla każdego podzbioru we wszystkich podzbiorach sklonuj go i dodaj jako pierwszy do podzbioru.
ArrayList<ArrayList<Integer>> getSubsets(ArrayList<Integer> set, int index){
ArrayList<ArrayList<Integer>> allsubsets;
if(set.size() == index){
allsubsets = new ArrayList<ArrayList<Integer>>();
allsubsets.add(new ArrayList<Integer>()); // the empty set
}else{
allsubsets = getSubsets(set, index+1);
int item = set.get(index);
ArrayList<ArrayList<Integer>> moresubsets = new ArrayList<ArrayList<Integer>>();
for(ArrayList<Integer> subset: allsubsets){
ArrayList<Integer> newsubset = new ArrayList<Integer>();
newsubset.addAll(subset);
newsubset.add(item);
moresubsets.add(newsubset);
}
moresubsets.addAll(moresubsets);
}
return allsubsets;
}
package problems;
import java.util.ArrayList;
import java.util.List;
public class SubsetFinderRecursive {
public static void main(String[] args) {
//input
int[] input = new int[3];
for(int i=0; i<input.length; i++) {
input[i] = i+1;
}
// root node of the tree
Node root = new Node();
// insert values into tree
for(int i=0; i<input.length; i++) {
insertIntoTree(root, input[i]);
}
// print leaf nodes for subsets
printLeafNodes(root);
}
static void printLeafNodes(Node root) {
if(root == null) {
return;
}
// Its a leaf node
if(root.left == null && root.right == null) {
System.out.println(root.values);
return;
}
// if we are not at a leaf node, then explore left and right
if(root.left !=null) {
printLeafNodes(root.left);
}
if(root.right != null) {
printLeafNodes(root.right);
}
}
static void insertIntoTree(Node root, int value) {
// Error handling
if(root == null) {
return;
}
// if there is a sub tree then go down
if(root.left !=null && root.right != null) {
insertIntoTree(root.left, value);
insertIntoTree(root.right, value);
}
// if we are at the leaf node, then we have 2 choices
// Either exclude or include
if(root.left == null && root.right == null) {
// exclude
root.left = new Node();
root.left.values.addAll(root.values);
// include
root.right = new Node();
root.right.values.addAll(root.values);
root.right.values.add(value);
return;
}
}
}
class Node {
Node left;
Node right;
List<Integer> values = new ArrayList<Integer>();
}