Die Berechnung aller Teilmengen einer Menge von Zahlen

Question

Ich möchte die Teilmengen einer Menge von ganzen Zahlen zu finden. Es ist der erste Schritt der „Summe der Subsets“ Algorithmus mit Rückzieher. Ich habe den folgenden Code geschrieben, aber es ist nicht die richtige Antwort zurück:

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

Zum Beispiel, wenn ich will, um die Teilmengen von Satz berechnen = {1, 3, 5} Das Ergebnis meiner Methode ist:

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

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

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

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

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

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

Ich will es Produkte:

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

Ich denke, das Problem von dem Teil ist List.removeAll (Liste); aber ich weiß nicht, wie es zu korrigieren.

Answer 1

Was Sie wollen, ist eine Powerset . Hier ist eine einfache Implementierung davon:

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

Ich gebe Ihnen ein Beispiel zu erklären, wie der Algorithmus für die Powerset von {1, 2, 3} funktioniert:

• Remove {1} und führen Powerset für {2, 3};
  • Remove {2} und führen Powerset für {3};
    • Remove {3} und führen Powerset für {};
      • Powerset von {} ist {{}};
    • Powerset von {3} wird 3 kombiniert mit {{}} = { {}, {3} };
  • Powerset von {2, 3} wird {2} kombiniert mit { {}, {3} } = { {}, {3}, {2}, {2, 3} };
• Powerset von {1, 2, 3} ist {1} mit { {}, {3}, {2}, {2, 3} } kombiniert = { {}, {3}, {2}, {2, 3}, {1}, {3, 1}, {2, 1}, {2, 3, 1} }.

Answer 2

Nur ein Primer, wie Sie könnte das Problem lösen:

Ansatz 1

Nehmen Sie
• das erste Element Ihrer Nummernliste
• erzeugen alle Subsets aus der verbleibenden Nummernliste (das heißt die Anzahl Liste ohne die Auserwählte) => Rekursion!
• für jede Teilmenge in dem vorhergehenden Schritt gefunden wird, fügt die Teilmenge selbst und die Teilmenge mit dem in Schritt ausgewählten Elemente 1 verbunden ist mit dem Ausgang.

Natürlich haben Sie den Basisfall zu prüfen, das heißt, wenn Ihre Nummernliste leer ist.

Ansatz 2

Es ist eine wohlbekannte Tatsache, dass ein Satz mit n Elementen 2^n Untergruppen hat. So können Sie in binär von 0 zu 2^n zählen und die binären Zahl wie die entsprechenden Teilmenge interpretieren. Beachten Sie, dass dieser Ansatz mit einer ausreichenden Menge von Ziffern eine binäre Zahl erfordert den ganzen Satz darzustellen.

Es sollte ein nicht zu großes Problem sein, um einen der beiden Ansätze in Code zu umwandeln.

Answer 3

Der Code ist wirklich verwirrend und es gibt keine Erklärung.

Sie können mit einem bitmask iterativ tun, bestimmt, welche Zahlen in der Menge sind. Jede Zahl von 0 bis 2 ^ n gibt eine eindeutige Teilmenge in ihrer binären Darstellung, zum Beispiel

für n = 3:

i = 5 -> 101 binär, wählen ersten und letzten Elemente i = 7 -> 111 binär, wählen Sie zuerst 3 Elemente

Angenommen, es gibt n Elemente (n <64, schließlich, wenn n größer als 64 Sie werden feststellen, dass laufen für immer).

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

Unter Berücksichtigung eines Noob Visitor (dank Google) auf diese Frage - wie ich
Hier ist eine rekursive Lösung, die auf einfaches Prinzip funktioniert:

Soll = {a, b, c, d, e}
wir können es dann brechen + {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

     }
}

OUTPUT

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

Answer 5

Es ist klar, dass die Gesamtzahl der Teilsätze von irgendeinem gegebenen Satz auf 2 ^ (Anzahl der Elemente im Set) gleich ist. Wenn gesetzt

A = {1, 2, 3}

dann Teilmenge von A ist:

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

Wenn wir sehen, es ist wie Binärzahlen.

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

Wenn wir berücksichtigen, oben:

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

Nach dem, was ich heute gelernt, hier ist die Java-Lösung Es basiert auf 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;
    }
}

Beim Laufen wird es Ergebnisse geben als

[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

Ich habe versucht tatsächlich, diese zu lösen und den Algorithmus @phimuemue auf der früheren Post bekommt .Hier ist das, was ich implementiert. Hoffe, dass dies funktioniert.

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

Wenn Sie es zu tun mit einer großen Sammlung von Elementen, können Sie (wenn auch nicht wahrscheinlich) in Probleme mit Stapelüberlauf führen. Ich gebe zu du bist eher Speicher laufen, bevor Sie den Stack überlaufen, aber ich werde diese nicht-rekursive Methode setze hier sowieso.

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

Oder wenn Sie lieber mit Arrays umgehen würden:

@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

Hier ist ein Pseudo-Code. Sie können gleiche rekursive Aufrufe geschnitten, indem die Werte für jeden Anruf zu speichern, wie Sie gehen und vor dem rekursiven Aufruf zu überprüfen, ob der Wert Anruf bereits vorhanden ist.

Der folgende Algorithmus wird mit Ausnahme der leeren Menge alle die Teilmengen haben.

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

Hier ist die Logik, alle Teilmengen einer gegebenen Menge von Zahlen zu drucken. Dies wird auch Powerset eines Satzes genannt. Ich habe einen einfachen rekursive Ansatz verwendet, um dieses mit Hilfe von Java zu lösen, aber Sie kann entsprechend Code in anderen Sprachen.

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
    }

}

Ausgabe des obigen Codes:

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

Um das Konzept erhalten Sie das folgende YouTube-Video ansehen können, die eindeutig erklärt, was Ansatz hinter dem Code verwendet wird. https://www.youtube.com/watch?v=vEL15C3vbVE

Answer 14

Einfache Java rekursive Lösung -

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

Um Redundanz zu vermeiden wir können einfach Set verwenden anstelle von List