Calcolando tutti i sottoinsiemi di un insieme di numeri

Question

Chi vorrei trovare i sottoinsiemi di un insieme di numeri interi. E 'il primo passo della "Somma di sottoinsiemi" algoritmo con backtracking. Ho scritto il seguente codice, ma non restituisce la risposta corretta:

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

Per esempio, se voglio calcolare i sottoinsiemi di set = {1, 3, 5} Il risultato del mio metodo è il seguente:

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

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

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

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

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

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

voglio che i prodotti:

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

Credo che il problema è dalla parte list.removeAll (lista); ma non so come correggerlo.

Answer 1

Quello che vuoi è chiamato un Powerset . Ecco un'implementazione semplice di esso:

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

io vi darò un esempio per spiegare come funziona l'algoritmo per la Powerset di {1, 2, 3}:

• Rimuovere {1}, ed eseguire Powerset per {2, 3};
  • Rimuovere {2}, ed eseguire Powerset per {3};
    • Rimuovere {3}, ed eseguire Powerset per {};
      • Powerset di {} è {{}};
    • Powerset di {3} è 3 combinato con {{}} = { {}, {3} };
  • Powerset di {2, 3} è {2} combinato con { {}, {3} } = { {}, {3}, {2}, {2, 3} };
• Powerset di {1, 2, 3} è {1} combinato con { {}, {3}, {2}, {2, 3} } = { {}, {3}, {2}, {2, 3}, {1}, {3, 1}, {2, 1}, {2, 3, 1} }.

Answer 2

Proprio un primer come potrebbero risolvere il problema:

Approccio 1

• Prendere il primo elemento della vostra lista numero
• generare tutti sottoinsiemi dalla lista numero rimanente (vale a dire l'elenco dei numeri, senza il prescelto) => ricorsione!
• per ogni sottoinsieme trovato nel passaggio precedente, aggiungere il sottoinsieme stesso e il sottoinsieme unito con l'elemento scelto nel passaggio 1 all'uscita.

Naturalmente, si controlla il caso base, vale a dire se la vostra lista numero è vuota.

Approccio 2

E 'un fatto ben noto che un insieme di elementi n ha sottoinsiemi 2^n. Così, si può contare in binario da 0 a 2^n e interpretare il numero binario come il sottoinsieme corrispondente. Si noti che questo approccio richiede un numero binario con una quantità sufficiente di cifre per rappresentare l'intera serie.

Dovrebbe essere un non troppo grande problema di convertire uno dei due approcci in codice.

Answer 3

Il codice è davvero confusa e non v'è alcuna spiegazione.

Si può fare in modo iterativo con una maschera di bit che determina quali numeri sono nel set. Ogni numero da 0 a 2 ^ n dà un sottoinsieme unico nella sua rappresentazione binaria, ad esempio

per n = 3:

i = 5 -> 101 in binario, scegliere primo e l'ultimo elemento I = 7 -> 111 in binario, selezionato prima 3 elementi

Supponiamo che ci sono n elementi (n <64, dopo tutto se n è maggiore di 64 si incorrerà per sempre).

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 4

Considerando un Noob visitatori (grazie a Google) a questa domanda - come me
Ecco una soluzione ricorsiva che funziona su principio molto semplice:

Set = {a, b, c, d, e}
allora possiamo rompere 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

     }
}

USCITA

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

Answer 5

E 'chiaro che il numero totale di sottoinsiemi di qualsiasi dato insieme è uguale a 2 ^ (numero di elementi nel set). Se set

  

A = {1, 2, 3}

poi sottoinsieme di A è:

  

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

Se osserviamo è come numeri binari.

  

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

Se prendiamo in considerazione di cui sopra:

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

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 7

In base a quello che ho imparato oggi, ecco la soluzione Java Si basa su 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;
    }
}

L'esecuzione darà risultati come

[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 8

I è stato effettivamente cercando di risolvere questo e ottenuto il @phimuemue algoritmo sul post precedente .Qui è quello che ho implementato. Spero che questo funziona.

/**
*@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 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

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

Answer 11

Se hai a che fare con una grande collezione di elementi, è possibile (anche se non probabile) incorrere in problemi con stack overflow. Ammetto è molto più probabile a corto di memoria prima di overflow dello stack, ma io metterò questo metodo non ricorsivo qui comunque.

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 se si preferisce trattare con gli array:

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

Answer 12

Ecco alcuni pseudocodice. È possibile tagliare stesse chiamate ricorsive memorizzando i valori per ogni chiamata, come si va e prima chiamata ricorsiva verificare se il valore di chiamata è già presente.

Il seguente algoritmo avrà tutti i sottoinsiemi escludendo l'insieme vuoto.

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 13

Ecco la logica per stampare tutti i sottoinsiemi di un dato insieme di numeri. Questo è anche chiamato Powerset di un set. Ho usato un semplice approccio ricorsivo per risolvere questo utilizzando Java, ma si può corrispondentemente il codice in altre lingue pure.

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
    }

}

Output del codice di cui sopra:

[123]
[12]
[13]
[1]
[23]
[2]
[3]
[]

Per ottenere il concetto è possibile guardare il seguente video di YouTube che spiega chiaramente cosa approccio viene utilizzato dietro il codice. https://www.youtube.com/watch?v=vEL15C3vbVE

Answer 14

semplice soluzione ricorsiva Java -

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

Per la ridondanza evitano possiamo semplicemente usare set al posto di List