Obliczanie wszystkich podzbiorów zbioru liczb

Tylko podkład, jak można rozwiązać problem:

Podejście 1

• weź pierwszy element listy liczb
• Wygeneruj Wszystkie podzbiory z pozostałej listy liczb (tzn. lista liczb bez wybranej) => Rekurencja!
• dla każdego podzbioru znalezionego w poprzednim kroku dodaj do wyjścia sam podzbiór i podzbiór połączony z elementem wybranym w kroku 1.

Oczywiście trzeba sprawdzić przypadek podstawowy, czyli jeśli Twoja lista numerów jest pusta.

Podejście 2

Jest dobrze znanym faktem, że zbiór z n elementami ma 2^n podzbiory. W ten sposób można liczyć w postaci binarnej od 0 do 2^n i interpretować liczbę binarną jako odpowiadający jej podzbiór. Zauważ, że to podejście wymaga liczby binarnej z wystarczającą ilością cyfr, aby reprezentować cały zestaw.

Nie powinno być zbyt dużym problemem przekształcenie jednego z dwóch podejść w kod.

Twój kod jest naprawdę mylący i nie ma żadnego wyjaśnienia.

Można zrobić iteracyjnie z maską bitową, która określa, które liczby są w zbiorze. Każda liczba od 0 do 2^N daje unikalny podzbiór w swojej reprezentacji binarnej, na przykład

Dla n = 3:

I = 5 - > 101 w systemie binarnym wybierz pierwszy i ostatni element i = 7 - > 111 w systemie binarnym wybierz pierwsze 3 elementy

Załóżmy, że jest n elementów (n

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
}

Biorąc pod uwagę odwiedzającego nooba (dzięki google) na to pytanie - Jak ja
Oto rozwiązanie rekurencyjne, które działa na prostej zasadzie:

Set = {a, b, c,d, e}
wtedy możemy go złamać do {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

     }
}

Wyjście

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

Jest jasne, że całkowita liczba podzbiorów dowolnego zbioru jest równa 2^(Liczba elementów w zbiorze). If set

A = {1, 2, 3}

Wtedy podzbiór A jest:

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

Jeśli spojrzymy to jest jak liczby binarne.

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

Jeśli weźmiemy pod uwagę powyżej:

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

Bazując na tym, czego się dzisiaj nauczyłem, oto rozwiązanie Java Opiera się na 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;
    }
}

Uruchomienie go Da wyniki jako

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

Właśnie próbowałem rozwiązać ten i dostałem algorytm @ phimuemue w poprzednim poście .Oto, co zaimplementowałem. Mam nadzieję, że to zadziała.

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

Tu jest jakiś pseudokod. Możesz wyciąć te same wywołania rekurencyjne, przechowując wartości dla każdego wywołania, a przed wywołaniem rekurencyjnym sprawdzając, czy wartość wywołania jest już obecna.

Poniższy algorytm będzie miał wszystkie podzbiory z wyłączeniem zbioru pustego.

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

Jeśli masz do czynienia z dużą kolekcją elementów, możesz (choć nie jest to prawdopodobne) napotkać problemy z przepełnieniem stosu. Przyznaję, że bardziej prawdopodobne jest, że zabraknie Ci pamięci, zanim przepełnisz stos, ale i tak umieszczę tę metodę rekurencyjną tutaj.

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

Lub jeśli wolisz radzić sobie z tablicami:

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