conjuntos - interseccion de dos arreglos en java

Obteniendo un conjunto de poder de un conjunto en Java

Question

El conjunto de poder de {1, 2, 3} es:

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

Digamos que tengo un Set en Java:

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

¿Cómo escribo la función getPowerset, con el mejor orden posible de complejidad? (Creo que podría ser O (2 ^ n).)

Answer 1

Algoritmo:

Entrada: Set [], set_size 1. Obtenga el tamaño de la potencia set powet_set_size = pow (2, set_size) 2 Loop para contador de 0 a pow_set_size (a) Loop para i = 0 a set_size (i) Si ith bit in counter es establecer el elemento de impresión ith del conjunto para este subconjunto (b) Separador de impresión para subconjuntos, es decir, nueva línea

#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;
}

Answer 2

Algunas de las soluciones anteriores sufren cuando el tamaño del conjunto es grande porque están creando una gran cantidad de basura de objetos para ser recolectados y requieren copiar datos. ¿Cómo podemos evitar eso? Podemos aprovechar el hecho de que sabemos cuán grande será el tamaño del conjunto de resultados (2 ^ n), preasignar un conjunto tan grande y solo anexar al final del mismo, sin copiar nunca.

La aceleración crece rápidamente con n. Lo comparé con la solución anterior de João Silva. En mi máquina (todas las medidas son aproximadas), n = 13 es 5 veces más rápido, n = 14 es 7x, n = 15 es 12x, n = 16 es 25x, n = 17 es 75x, n = 18 es 140x. De modo que la creación / recolección y copia de basura está dominando en lo que de otro modo parecerían ser soluciones de gran O similares.

La asignación previa de la matriz al comienzo parece ser una victoria en comparación con dejarla crecer dinámicamente. Con n = 18, el crecimiento dinámico lleva aproximadamente el doble de tiempo en general.

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;
}

Answer 3

Aquí está para generar un conjunto de potencia. La idea es primero = S[0] y los conjuntos más pequeños son S[1,...n] .

Calcule todos los subconjuntos de smallerSet y colóquelos en allsubsets.

Para cada subconjunto en todos los subconjuntos, clonar y agregar primero al subconjunto.

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;
}

Answer 4

Aquí hay una solución donde uso un generador, la ventaja es que el conjunto de potencia completo nunca se almacena a la vez ... De modo que puede iterar uno por uno sin necesidad de almacenarlo en la memoria. Me gustaría pensar que es una mejor opción ... Tenga en cuenta que la complejidad es la misma, O (2 ^ n), pero los requisitos de memoria se reducen (¡suponiendo que el recolector de basura se comporte!;))

/**
 *
 */
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;
    }

}

Para llamarlo, usa este patrón:

        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);
        }

Es de mi Biblioteca Project Euler ... :)

Answer 5

Aquí hay una solución iterativa fácil 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;
}

Answer 6

De hecho, he escrito un código que hace lo que estás pidiendo en O (1). La pregunta es qué piensas hacer con el Set siguiente. Si va a llamar a size() , es O (1), pero si va a iterar, obviamente es O(2^n) .

contains() sería O(n) , etc.

¿Realmente necesitas esto?

EDITAR:

Este código ahora está disponible en Guava , expuesto a través del método Sets.powerSet(set) .

Answer 7

Esta es mi solución recursiva que puede obtener el poder de cualquier conjunto utilizando Java Generics. Su idea principal es combinar el cabezal de la matriz de entrada con todas las soluciones posibles del resto de la matriz de la siguiente manera.

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);
    }
}

Esto dará como resultado:

[[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], []]

Answer 8

Estaba buscando una solución que no fuera tan grande como las que se publican aquí. Esto se dirige a Java 7, por lo que requerirá un puñado de pastas para las versiones 5 y 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;

Aquí hay un código de ejemplo para probar:

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()));
}

Answer 9

Este es mi enfoque con lambdas.

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());
        }

O en paralelo (ver el comentario paralelo ()):

Tamaño del conjunto de entrada: 18

Procesadores lógicos: 8 a 3.4GHz

Mejora del rendimiento: 30%

Answer 10

La siguiente solución está tomada de mi libro " Entrevistas de codificación: preguntas, análisis y soluciones ":

Se seleccionan algunos enteros en una matriz que componen una combinación. Se utiliza un conjunto de bits, donde cada bit representa un número entero en la matriz. Si el carácter i-ésimo se selecciona para una combinación, el bit i-ésimo es 1; de lo contrario, es 0. Por ejemplo, se usan tres bits para combinaciones de la matriz [1, 2, 3]. Si los dos primeros enteros 1 y 2 se seleccionan para componer una combinación [1, 2], los bits correspondientes son {1, 1, 0}. De manera similar, los bits correspondientes a otra combinación [1, 3] son ​​{1, 0, 1}. Podemos obtener todas las combinaciones de una matriz con longitud n si podemos obtener todas las combinaciones posibles de n bits.

Un número se compone de un conjunto de bits. Todas las combinaciones posibles de n bits corresponden a números de 1 a 2 ^ n -1. Por lo tanto, cada número en el rango entre 1 y 2 ^ n -1 corresponde a una combinación de una matriz con longitud n . Por ejemplo, el número 6 está compuesto por los bits {1, 1, 0}, por lo que los caracteres primero y segundo se seleccionan en el conjunto [1, 2, 3] para generar la combinación [1, 2]. De manera similar, el número 5 con los bits {1, 0, 1} corresponde a la combinación [1, 3].

El código de Java para implementar esta solución se ve a continuación:

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;
}

El incremento del método aumenta un número representado en un conjunto de bits. El algoritmo borra 1 bit del bit del extremo derecho hasta que se encuentra un bit 0. A continuación, establece el bit 0 más a la derecha en 1. Por ejemplo, para aumentar el número 5 con los bits {1, 0, 1}, borra 1 bit del lado derecho y establece el bit 0 más a la derecha en 1. Los bits se convierten {1, 1, 0} para el número 6, que es el resultado de aumentar 5 por 1.

Answer 11

Otra implementación de muestra:

 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();
        }
    }

Answer 12

Otra solución más: con java8 + streaming api. Es floja y ordenada, por lo que devuelve los subconjuntos correctos cuando se usa con "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()));
}

Y el código del cliente es

@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);

}

/ * Imprime: [] [a] [b] [c] [d] [e] [a, b] [a, c] [b, c] * /

Answer 13

Podríamos escribir la potencia establecida con o sin el uso de la recursión. Aquí hay un intento sin recurrencia:

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;
}

Answer 14

Recientemente tuve que usar algo como esto, pero necesitaba las sublistas más pequeñas (con 1 elemento, luego 2 elementos, ...) primero. No quería incluir la lista vacía ni toda la lista. Además, no necesitaba una lista de todas las sublistas devueltas, solo necesitaba hacer algunas cosas con cada una.

Quería hacer esto sin recurrencia, y se le ocurrió lo siguiente (con el "hacer cosas" abstraído en una interfaz funcional):

@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
}

De esta forma, también es fácil limitarlo a sublistas de longitudes específicas.

Answer 15

Sí, es O(2^n) hecho, ya que necesita generar, bueno, 2^n combinaciones posibles. Aquí hay una implementación en funcionamiento, usando genéricos y conjuntos:

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;
}  

Y una prueba, dada su entrada de ejemplo:

 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);
 }

Answer 16

Se me ocurrió otra solución basada en las ideas de @Harry He. Probablemente no sea el más elegante, pero aquí va según lo entiendo:

Tomemos el clásico ejemplo simple PowerSet de SP (S) = {{1}, {2}, {3}}. Sabemos que la fórmula para obtener el número de subconjuntos es 2 ^ n (7 + conjunto vacío). Para este ejemplo 2 ^ 3 = 8 subconjuntos.

Para encontrar cada subconjunto necesitamos convertir 0-7 decimal a representación binaria que se muestra en la siguiente tabla de conversión:

Si recorremos la tabla fila por fila, cada fila dará como resultado un subconjunto y los valores de cada subconjunto provendrán de los bits habilitados.

Cada columna en la sección Valor del contenedor corresponde a la posición del índice en el conjunto de entrada original.

Aquí mi código:

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;
}

}

Answer 17

Si S es un conjunto finito con N elementos, entonces el conjunto de potencia de S contiene 2 ^ N elementos. El tiempo para simplemente enumerar los elementos del conjunto de poder es 2 ^ N, entonces O(2^N) es un límite inferior en la complejidad de tiempo (con entusiasmo) construyendo el conjunto de poder.

En pocas palabras, cualquier cálculo que implique la creación de grupos electrógenos no va a escalar para valores grandes de N. Ningún algoritmo inteligente lo ayudará ... ¡además de evitar la necesidad de crear conjuntos de potencia!

Answer 18

Si está utilizando colecciones Eclipse (anteriormente colecciones GS ), puede usar el método powerSet() en todos los 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]]

Nota: soy un committer para las colecciones de Eclipse.

Answer 19

Si n <63, que es una suposición razonable ya que se quedaría sin memoria (a menos que se use una implementación de iterador) intentando construir el conjunto de poder de todos modos, esta es una forma más concisa de hacerlo. Las operaciones binarias son mucho más rápidas que Math.pow() y las matrices para máscaras, pero de alguna manera los usuarios de Java les tienen miedo ...

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;

Answer 20

Un subconjunto de t es cualquier conjunto que se puede hacer eliminando cero o más elementos de t. El subconjunto sin primer agrega los subconjuntos de t que faltan al primer elemento y el ciclo for se ocupará de agregar subconjuntos con el primer elemento. Por ejemplo, si t contenía los elementos ["1", "2", "3"], missingFirst agregará [[""], ["2"], ["3"], ["2", "3 "]] y el bucle for pegará el" 1 "al frente de estos elementos y lo agregará al newSet. Así que terminaremos con [[""], ["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;
    }

Answer 21

Una forma sin recurrencia es la siguiente: use una máscara binaria y haga todas las combinaciones posibles.

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;

    }

}

Answer 22

Here hay un tutorial que describe exactamente lo que quiere, incluido el código. Tiene razón en que la complejidad es O (2 ^ n).

Answer 23

// 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;
    }

}

Answer 24

import java.util.Set;
import com.google.common.collect.*;

Set<Set<Integer>> sets = Sets.powerSet(ImmutableSet.of(1, 2, 3));

Answer 25

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();
        } 
    }
}