El cálculo de todos los subconjuntos de un conjunto de números
https://stackoverflow.com/questions/4640034
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Quiero encontrar los subconjuntos de un conjunto de números enteros. Es el primer paso de "Suma de subconjuntos" algoritmo de 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 los productos:
1, 3, 5
1, 5
3, 5
5
Creo que el problema es de la parte List.removeAll (lista); pero no sé cómo corregirlo.
Solución
Lo que usted quiere que se llama un Powerset . Aquí es una implementación sencilla de él:
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;
}
Yo le dará un ejemplo para explicar cómo funciona el algoritmo para el powerset de {1, 2, 3}:
- Quitar
{1}, y ejecutar powerset para{2, 3};- Quitar
{2}, y ejecutar powerset para{3};- Quitar
{3}, y ejecutar powerset para{};- Powerset de
{}es{{}};
- Powerset de
- Powerset de
{3}se3combina con{{}}={ {}, {3} };
- Quitar
- Powerset de
{2, 3}se{2}combina con{ {}, {3} }={ {}, {3}, {2}, {2, 3} };
- Quitar
- Powerset de
{1, 2, 3}se{1}combina con{ {}, {3}, {2}, {2, 3} }={ {}, {3}, {2}, {2, 3}, {1}, {3, 1}, {2, 1}, {2, 3, 1} }.
Otros consejos
Sólo una imprimación cómo podría resolver el problema:
Enfoque 1
- Tome el primer elemento de la lista de números
- generar todos subconjuntos de la lista número restante (es decir, la lista de números sin la elegida) => recursión!
- para cada subgrupo se encontró en el paso anterior, agregue el subconjunto propio y el subconjunto unido con el elemento elegido en el paso 1 a la salida.
Por supuesto, usted tiene que comprobar la hipótesis de base, es decir, si su lista de números está vacía.
Enfoque 2
Es un hecho bien conocido que un conjunto de elementos n tiene subconjuntos 2^n. 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 que representan todo el conjunto.
Debe ser un problema no es demasiado grande para convertir uno de los dos enfoques en código.
Su código es muy confuso y no hay explicación.
Se puede hacer de forma iterativa 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, elegir elementos primero y último i = 7 -> 111 en binario, seleccione primero 3 elementos
Supongamos que hay n elementos (n <64, después de todo, si n es mayor que 64 se encontrará con que 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
}
En vista de un Noob de Visitantes (gracias a Google) a esta pregunta - como yo
Aquí es una solución recursiva que trabaja en principio simple:
Set = {a, b, c, d, e}
entonces podemos romperlo a {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
Es evidente que, el número total de subconjuntos de un conjunto dado es igual a 2 ^ (número de elementos en el conjunto). Si conjunto
A = {1, 2, 3}
entonces subconjunto de A es:
{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}
Si observamos es como números binarios.
{000}, {001}, {010}, {011}, {100}, {101}, {110}, {111}
Si tenemos en cuenta anteriormente:
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);
}
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("}");
}
}
Sobre la base de lo que he aprendido hoy, aquí está la solución de Java
Se basa en 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;
}
}
Running 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]
Yo estaba tratando de resolver éste y consiguió el @phimuemue algoritmo en el post anterior .Aquí es lo que he implementado. 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);
}
}
}
// 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 }
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;
}
Si usted está tratando con una gran colección de elementos, es posible (aunque no probable) que tenga problemas con el desbordamiento de pila. Admito que es más probable que se quede sin memoria antes de desbordar la pila, pero voy a poner este método no recursivo aquí de todos modos.
public static final <T> Set<Set<T>> powerSet(final Iterable<T> original) {
Set<Set<T>> sets = new HashSet<>();
sets.add(new HashSet<>());
for (final T value : original) {
final Set<Set<T>> newSets = new HashSet<>(sets);
for (final Set<T> set : sets) {
final Set<T> newSet = new HashSet<>(set);
newSet.add(value);
newSets.add(newSet);
}
sets = newSets;
}
return sets;
}
O si lo prefiere tratar con matrices:
@SuppressWarnings("unchecked")
public static final <T> T[][] powerSet(final T... original) {
T[][] sets = (T[][]) Array.newInstance(original.getClass(), 1);
sets[0] = Arrays.copyOf(original, 0);
for (final T value : original) {
final int oldLength = sets.length;
sets = Arrays.copyOf(sets, oldLength * 2);
for (int i = 0; i < oldLength; i++) {
final T[] oldArray = sets[i];
final T[] newArray = Arrays.copyOf(oldArray, oldArray.length + 1);
newArray[oldArray.length] = value;
sets[i + oldLength] = newArray;
}
}
return sets;
}
Aquí hay algo de pseudocódigo. Puede cortar mismas llamadas recursivas mediante el almacenamiento de los valores para cada llamada sobre la marcha y antes de la llamada recursiva de comprobar si el valor de 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;
}
}
Aquí está la lógica para imprimir todos los subconjuntos de un conjunto dado de números. Esto también se llama powerset de un conjunto. He utilizado un enfoque recursivo simple de resolver esto utilizando Java, pero que pueda correspondiente código en otros idiomas.
import java.util.Scanner;
public class PowerSubset {
public static void main(String[] args) {
// HardCoded Input
int arr[] = { 1, 2, 3 };//original array whose subset is to be found
int n=3; //size of array
// Dynamic Input
/*Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[] = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}*/
int data[] = new int[arr.length]; // temporary array
printSubset(arr, data, n, 0, 0);
}
public static void printSubset(int arr[], int data[], int n, int dataIndex, int arrIndex) {
if (arrIndex == n) { //comparing with n since now you are at the leaf node
System.out.print("[");//watch pictorial chart in the below video link
for (int j = 0; j < n; j++) {
System.out.print(data[j] == 0 ? "" : data[j]);
}
System.out.print("]");
System.out.println();
return;
}
data[dataIndex] = arr[arrIndex];
printSubset(arr, data, n, dataIndex + 1, arrIndex + 1);//recursive call 1
data[dataIndex] = 0;
printSubset(arr, data, n, dataIndex, arrIndex + 1);//recursive call 2
}
}
salida del código anterior:
[123]
[12]
[13]
[1]
[23]
[2]
[3]
[]
Para obtener el concepto se puede ver el siguiente video de youtube que explica claramente qué método se utiliza detrás del código. https://www.youtube.com/watch?v=vEL15C3vbVE
solución recursiva de Java simple -
private static List<List<Integer>> allsubSet(List<Integer> integers, int start, int end) {
//Base case if there is only one element so there would be two subset
// empty list and that element
if(start == end) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> emptyList = new ArrayList<>();
result.add(emptyList);
List<Integer> element = new ArrayList<>();
element.add(integers.get(start));
result.add(element );
return result;
}
//I know if by recursion we can expect that we'll get the n-1 correct result
List<List<Integer>> lists = allsubSet(integers, start, end-1);
//here i copy all the n-1 results and just added the nth element in expected results
List<List<Integer>> copyList = new ArrayList<>(lists);
for (List<Integer> list : lists) {
List<Integer> copy= new ArrayList<>(list);
copy.add(integers.get(end));
copyList.add(copy);
}
return copyList;
}
Para evitar la redundancia simplemente podemos utilizar situado en el lugar de la lista
