Le calcul de tous les sous-ensembles d'un ensemble de nombres

Question

Je veux trouver les sous-ensembles d'un ensemble de nombres entiers. Il est la première étape de l'algorithme « Somme des sous-ensembles » avec retours en arrière. J'ai écrit le code suivant, mais il ne retourne pas la bonne réponse:

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

Par exemple, si je veux calculer les sous-ensembles de jeu = {1, 3, 5} Le résultat de ma méthode est:

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

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

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

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

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

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

Je veux qu'il produit:

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

Je pense que le problème est de la partie list.removeAll (liste); mais je ne sais pas comment la corriger.

Answer 1

Qu'est-ce que vous voulez que l'on appelle un Powerset . Voici une implémentation simple de celui-ci:

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

Je vais vous donner un exemple pour expliquer comment l'algorithme fonctionne pour le powerset de {1, 2, 3}:

• Supprimer {1} et exécuter powerset pour {2, 3};
  • Supprimer {2} et exécuter powerset pour {3};
    • Supprimer {3} et exécuter powerset pour {};
      • Powerset de {} est {{}};
    • Powerset de {3} est combiné avec 3 {{}} = { {}, {3} };
  • Powerset de {2, 3} est combiné avec {2} { {}, {3} } = { {}, {3}, {2}, {2, 3} };
• Powerset de {1, 2, 3} est combiné avec {1} { {}, {3}, {2}, {2, 3} } = { {}, {3}, {2}, {2, 3}, {1}, {3, 1}, {2, 1}, {2, 3, 1} }.

Answer 2

Juste une couche de fond la façon dont vous pourrait résoudre le problème:

Approche 1

• Prenez le premier élément de votre liste de numéros
• générer tous sous-ensembles de la liste des numéros restants (à savoir la liste des numéros sans celui choisi) => Recursion!
• pour chaque sous-ensemble trouvé dans l'étape précédente, ajouter le sous-ensemble lui-même et le sous-ensemble joint à l'élément choisi à l'étape 1 à la sortie.

Bien sûr, vous devez vérifier le cas de base, à savoir si votre liste de numéros est vide.

Approche 2

Il est un fait bien connu qu'un ensemble d'éléments n a des sous-ensembles de 2^n. Ainsi, vous pouvez compter en binaire de 0 à 2^n et interpréter le nombre binaire comme le sous-ensemble correspondant. Notez que cette approche nécessite un nombre binaire avec une quantité suffisante de chiffres pour représenter l'ensemble.

Il devrait être un problème pas trop grand pour convertir l'une des deux approches dans le code.

Answer 3

Votre code est vraiment déroutant et il n'y a pas d'explication.

Vous pouvez faire itérativement avec un masque de bits qui détermine les chiffres sont dans l'ensemble. Chaque nombre de 0 à 2 ^ n donne un sous-ensemble unique dans sa représentation binaire, par exemple

pour n = 3:

i = 5 -> 101 en binaire, choisissez premier et dernier éléments i = 7 -> 111 en binaire, pour choisir les 3 premiers éléments

Supposons qu'il y ait des éléments n (n <64, après tout, si n est plus grand que 64 vous tomberez que jamais).

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

Considérant un visiteur Noob (merci Google) à cette question - comme moi
Voici une solution récursif qui fonctionne sur le principal simple:

Set = {a, b, c, d, e}
alors nous pouvons briser à {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

     }
}

SORTIE

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

Answer 5

Il est clair que, le nombre total de sous-ensembles d'un ensemble donné est égal à 2 ^ (nombre d'éléments dans l'ensemble). Si ensemble

  

A = {1, 2, 3}

puis sous-ensemble de A est:

  

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

Si l'on regarde comme il est des nombres binaires.

  

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

Si l'on tient compte ci-dessus:

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

D'après ce que j'ai appris aujourd'hui, voici la solution Java Il est basé sur 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 il donnera des résultats que

[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

je suis en train d'essayer de résoudre celui-ci et a obtenu le @phimuemue algorithme sur le post précédent .Ici est ce que je mis en œuvre. Espérons que cela fonctionne.

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

Si vous avez affaire à une grande collection d'éléments, vous pouvez (mais peu probable) rencontrer des problèmes avec débordement de pile. Je reconnais que vous êtes plus susceptible de manquer de mémoire avant de débordement de la pile, mais je vais mettre cette méthode non récursive ici de toute façon.

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

Ou si vous préférez gérer des tableaux:

@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

Voici quelques pseudo-code. Vous pouvez couper mêmes appels récursifs en stockant les valeurs pour chaque appel que vous allez et avant l'appel récursif vérifier si la valeur d'appel est déjà présent.

L'algorithme suivant aura toutes les sous-ensembles à l'exception de l'ensemble vide.

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

Voici la logique d'imprimer tous les sous-ensembles d'un ensemble de nombres. Il est également appelé powerset d'un ensemble. Je l'ai utilisé une approche récursive simple pour résoudre ce en utilisant Java, mais vous pouvez coder en conséquence dans d'autres langues.

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
    }

}

Sortie du code ci-dessus:

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

Pour le concept, vous pouvez regarder la vidéo sur YouTube suivante qui explique clairement quelle approche est utilisée derrière le code. https://www.youtube.com/watch?v=vEL15C3vbVE

Answer 14

Simple Java solution récursive -

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

Pour éviter la redondance, nous pouvons simplement utiliser mise en place de la liste