java - propios - subconjuntos de abcd

Cálculo de todos los subconjuntos de un conjunto de números

Question

Quiero encontrar los subconjuntos de un conjunto de enteros. Es el primer paso del algoritmo "Suma de subconjuntos" con retroceso. He escrito el siguiente código, pero no devuelve la respuesta correcta:

BTSum(0, nums);
///**************
ArrayList<Integer> list = new ArrayList<Integer>();

public static ArrayList<Integer> BTSum(int n, ArrayList<Integer> numbers) {
    if (n == numbers.size()) {
        for (Integer integer : list) {
            System.out.print(integer+", ");
        }
        System.out.println("********************");
        list.removeAll(list);
        System.out.println();
    } else {
        for (int i = n; i < numbers.size(); i++) {
            if (i == numbers.size() - 1) {
                list.add(numbers.get(i));
                BTSum(i + 1, numbers);
            } else {
                list.add(numbers.get(i));
                for (int j = i+1; j < numbers.size(); j++)
                BTSum(j, numbers);
            }
        }
    }

    return null;
}

Por ejemplo, si quiero calcular los subconjuntos de set = {1, 3, 5} El resultado de mi método es:

 1, 3, 5, ********************

 5, ********************

 3, 5, ********************

 5, ********************

 3, 5, ********************

 5, ********************

Quiero que produzca:

1, 3, 5 
1, 5
3, 5
5

Creo que el problema es de la lista de partes.removeTodo (lista); pero no sé cómo corregirlo

Answer 1

Aquí hay un pseudocódigo. Puede cortar las mismas llamadas recursivas almacenando los valores de cada llamada sobre la marcha y antes de la comprobación recursiva de llamadas si el valor de la llamada ya está presente.

El siguiente algoritmo tendrá todos los subconjuntos excluyendo el conjunto vacío.

list * subsets(string s, list * v){
    if(s.length() == 1){
        list.add(s);    
        return v;
    }
    else
    {
        list * temp = subsets(s[1 to length-1], v);     
        int length = temp->size();

        for(int i=0;i<length;i++){
            temp.add(s[0]+temp[i]);
        }

        list.add(s[0]);
        return temp;
    }
}

Answer 2

Considerar a un visitante novato (gracias a google) a esta pregunta, como yo
Aquí hay una solución recursiva que funciona en principio simple:

Set = {a, b, c, d, e}
entonces podemos dividirlo en {a} + Subset of {b,c,d,e}

public class Powerset{
     String str = "abcd"; //our string
     public static void main(String []args){
        Powerset ps = new Powerset();
        for(int i = 0; i< ps.str.length();i++){ //traverse through all characters
            ps.subs("",i);
        }
     }

     void subs(String substr,int index)
     {
         String s = ""+str.charAt(index); //very important, create a variable on each stack
         s = substr+s; //append the subset so far
         System.out.println(s); //print

         for(int i=index+1;i<str.length();i++)
           subs(s,i); //call recursively

     }
}

SALIDA

a
ab
abc
abcd
abd
ac
acd
ad
b
bc
bcd
bd
c
cd
d

Answer 3

De acuerdo con lo que aprendí hoy, aquí está la solución de Java Se basa en la recursion

public class Powerset {

    public static void main(String[] args) {
        final List<List<String>> allSubsets = powerSet(Arrays.asList(1, 2, 3, 4), 0);
        for (List<String> subsets : allSubsets) {
            System.out.println(subsets);
        }
    }

    private static List<List<String>> powerSet(final List<Integer> values,
                                               int index) {
        if (index == values.size()) {
            return new ArrayList<>();
        }
        int val = values.get(index);
        List<List<String>> subset = powerSet(values, index + 1);
        List<List<String>> returnList = new ArrayList<>();
        returnList.add(Arrays.asList(String.valueOf(val)));
        returnList.addAll(subset);
        for (final List<String> subsetValues : subset) {
            for (final String subsetValue : subsetValues) {
                returnList.add(Arrays.asList(val + "," + subsetValue));
            }
        }
        return returnList;
    }
}

Ejecutarlo dará resultados como

[1]
[2]
[3]
[4]
[3,4]
[2,3]
[2,4]
[2,3,4]
[1,2]
[1,3]
[1,4]
[1,3,4]
[1,2,3]
[1,2,4]
[1,2,3,4]

Answer 4

En realidad, estaba tratando de resolver este problema y obtuve el algoritmo @phimuemue en la publicación anterior. Aquí es lo que implementé. Espero que esto funcione.

/**
*@Sherin Syriac
*
*/

import java.util.ArrayList;
import java.util.List;

public class SubSet {
    ArrayList<List<Integer>> allSubset = new ArrayList<List<Integer>>();

    /**
     * @param args
     */
    public static void main(String[] args) {
        SubSet subSet = new SubSet();
        ArrayList<Integer> set = new ArrayList<Integer>();
        set.add(1);
        set.add(2);
        set.add(3);
        set.add(4);
        subSet.getSubSet(set, 0);
        for (List<Integer> list : subSet.allSubset) {
            System.out.print("{");
            for (Integer element : list) {
                System.out.print(element);
            }
            System.out.println("}");
        }

    }

    public void getSubSet(ArrayList<Integer> set, int index) {
        if (set.size() == index) {
            ArrayList<Integer> temp = new ArrayList<Integer>();
            allSubset.add(temp);
        } else {
            getSubSet(set, index + 1);
            ArrayList<List<Integer>> tempAllSubsets = new ArrayList<List<Integer>>();
            for (List subset : allSubset) {
                ArrayList<Integer> newList = new ArrayList<Integer>();
                newList.addAll(subset);
                newList.add(set.get(index));
                tempAllSubsets.add(newList);
            }

            allSubset.addAll(tempAllSubsets);
        }

    }

}

Answer 5

Está claro que, el número total de subconjuntos de cualquier conjunto dado es igual a 2 ^ (número de elementos en el conjunto). Si se establece

A = {1, 2, 3}

entonces el subconjunto de A es:

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

Si lo vemos, es como números binarios.

{000}, {001}, {010}, {011}, {100}, {101}, {110}, {111}

Si tomamos en cuenta arriba:

static void subSet(char[] set) {
        int c = set.length;

        for (int i = 0; i < (1 << c); i++) {
            System.out.print("{");
            for (int j = 0; j < c; j++) {
                if ((i & (1 << j)) > 0) {
                    System.out.print(set[j] + " ");
                }
            }
            System.out.println("}");
        }
    }

    public static void main(String[] args) {
        char c[] = {''a'', ''b'', ''c''};
        subSet(c);
    }

Answer 6

Lo que quieres se llama Powerset . Aquí hay una implementación simple de esto:

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

Le daré un ejemplo para explicar cómo funciona el algoritmo para el conjunto de poder de {1, 2, 3} :

• Quite {1} y ejecute powerset para {2, 3} ;
  • Quite {2} y ejecute powerset para {3} ;
    • Quite {3} y ejecute powerset para {} ;
      • Powerset de {} es {{}} ;
    • Powerset de {3} es 3 combinado con {{}} = { {}, {3} } ;
  • Powerset de {2, 3} es {2} combinado con { {}, {3} } = { {}, {3}, {2}, {2, 3} } ;
• Powerset de {1, 2, 3} es {1} combinado con { {}, {3}, {2}, {2, 3} } = { {}, {3}, {2}, {2, 3}, {1}, {3, 1}, {2, 1}, {2, 3, 1} } .

Answer 7

Solo una introducción sobre cómo podrías resolver el problema:

Enfoque 1

• Tome el primer elemento de su lista de números
• generar todos los subconjuntos de la lista de números restantes (es decir, la lista de números sin la elegida) => Recursión!
• para cada subconjunto encontrado en el paso anterior, agregue el subconjunto mismo y el subconjunto unido con el elemento elegido en el paso 1 a la salida.

Por supuesto, debe verificar el caso base, es decir, si su lista de números está vacía.

Enfoque 2

Es un hecho bien conocido que un conjunto con n elementos tiene 2^n subconjuntos. Por lo tanto, puede contar en binario de 0 a 2^n e interpretar el número binario como el subconjunto correspondiente. Tenga en cuenta que este enfoque requiere un número binario con una cantidad suficiente de dígitos para representar todo el conjunto.

No debería ser un problema demasiado grande convertir uno de los dos enfoques en código.

Answer 8

Tu código es realmente confuso y no hay explicación.

Puedes hacer iterativamente con una máscara de bits que determina qué números están en el conjunto. Cada número de 0 a 2 ^ n da un subconjunto único en su representación binaria, por ejemplo

para n = 3:

i = 5 -> 101 en binario, elija el primer y último elemento i = 7 -> 111 en binario, elija los primeros 3 elementos

Supongamos que hay n elementos (n <64, después de todo, si n es mayor que 64, lo ejecutará para siempre).

for(long i = 0; i < (1<<n); i++){
    ArrayList<Integer> subset = new ArrayList<Integer>();
    for(int j = 0; j < n; j++){
        if((i>>j) & 1) == 1){ // bit j is on
            subset.add(numbers.get(j));
        }
    }
    // print subset
}

Answer 9

// subsets for the set of 5,9,8

import java.util.ArrayList;
import java.util.List;

public class Subset {
    public static void main(String[] args) {
    List<Integer> s = new ArrayList<Integer>();
    s.add(9);
    s.add(5);
    s.add(8);
    int setSize = s.size();
    int finalValue = (int) (Math.pow(2, setSize));
    String bValue = "";
    for (int i = 0; i < finalValue; i++) {
        bValue = Integer.toBinaryString(i);
        int bValueSize = bValue.length();
        for (int k = 0; k < (setSize - bValueSize); k++) {
            bValue = "0" + bValue;
        }
        System.out.print("{ ");
        for (int j = 0; j < setSize; j++) {
            if (bValue.charAt(j) == ''1'') {
                System.out.print((s.get(j)) + " ");
            }
        }
        System.out.print("} ");
    }
}
}


//Output : { } { 8 } { 5 } { 5 8 } { 9 } { 9 8 } { 9 5 } { 9 5 8 } 

Answer 10

private static void findSubsets(int array[])
{
  int numOfSubsets = 1 << array.length; 

  for(int i = 0; i < numOfSubsets; i++)
 {
    int pos = array.length - 1;
   int bitmask = i;

   System.out.print("{");
   while(bitmask > 0)
   {
    if((bitmask & 1) == 1)
     System.out.print(array[pos]+",");
    bitmask >>= 1;
    pos--;
   }
   System.out.print("}");
 }
}

Answer 11

public static ArrayList<ArrayList<Integer>> powerSet(List<Integer> intList) {

    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    result.add(new ArrayList<Integer>());

    for (int i : intList) {
        ArrayList<ArrayList<Integer>> temp = new ArrayList<ArrayList<Integer>>();

        for (ArrayList<Integer> innerList : result) {
            innerList = new ArrayList<Integer>(innerList);
            innerList.add(i);
            temp.add(innerList);
        }
        result.addAll(temp);
    }

    return result;
}