Java obtient des détails sur tous les sous-ensembles d'une collection

Cet article présente principalement la méthode permettant d'obtenir tous les sous-ensembles d'un ensemble en Java. Il a une très bonne valeur de référence. Jetons un coup d'œil avec l'éditeur ci-dessous

Il y a une question de test écrite dans l'entretien. La signification générale est la suivante :

Saisissez un ensemble et. afficher tous les sous-ensembles de cet ensemble. Par exemple, saisissez : 1, 2, 4. Le résultat de sortie est le suivant :

[1]
[2]
[4]
[1, 2]
[1, 4]
[2, 4]
[1, 2, 4]

Ce que vous devez savoir : L'ensemble vide est un sous-ensemble de n'importe quel ensemble a ; le sous-ensemble approprié est celui qui ne contient pas de sous-ensemble ; un vrai sous-ensemble non vide ne contient pas de sous-ensembles ni d'ensembles vides

Idées de solutions :

Cette question peut être calculé à l'aide de la "méthode de correspondance bit à bit"

Par exemple, dans l'ensemble A={a,b,c}, pour tout élément, dans chaque sous-ensemble, il existe ou n'existe pas. Mappage à un sous-ensemble :

(a,b,c)
(1,1,1)->(a,b,c)
(1,1,0)->(a,b)
(1,0,1)->(a,c)
(1,0,0)->(a)
(0,1,1)->(b,c)
(0,1,0)->(b)
(0,0,1)->(c)
(0,0,0)->@(@表示空集)

Observez les règles ci-dessus, qui sont similaires à la méthode de stockage des données dans les ordinateurs, afin que vous puissiez mapper un entier à un ensemble...000 ~ 111...111 ( ce qui signifie qu'il y en a, signifie aucun, et vice versa), en augmentant progressivement le nombre entier, tous les nombres peuvent être parcourus, c'est-à-dire que le sous-ensemble correspondant de l'ensemble peut être obtenu.

Le test principal est l'opération de déplacement et la capacité de réflexion logique. Le code spécifique est le suivant (authentifié par cette machine et absolument fiable) :

import java.util.ArrayList;
import java.util.Scanner;
import org.apache.commons.collections.CollectionUtils;
/**
 * 输入一个集合，输出这个集合的所有子集
 * @author liangyongxing
 * @time 2017-02-06
 */
public class SubListExport {
 public static void main(String[] args) {
  ArrayList<Integer> list = new ArrayList<Integer>();
  System.out.println("请输入一串整数并在输入时用英文逗号隔开：");
  String inputString = new Scanner(System.in).next().toString();
  if (inputString != null && !inputString.isEmpty()) {
   String[] strArray = inputString.split(",");
   for (String str : strArray) {
    list.add(Integer.parseInt(str));
   }
   ArrayList<ArrayList<Integer>> allsubsets = getSubsets(list); 
   for(ArrayList<Integer> subList : allsubsets) {
    System.out.println(subList);
   }
  }
 }
 public static ArrayList<ArrayList<Integer>> getSubsets(ArrayList<Integer> subList) {
  ArrayList<ArrayList<Integer>> allsubsets = new ArrayList<ArrayList<Integer>>();
  int max = 1 << subList.size();
  for(int loop = 0; loop < max; loop++) {
   int index = 0;
   int temp = loop;
   ArrayList<Integer> currentCharList = new ArrayList<Integer>();
   while(temp > 0) {
    if((temp & 1) > 0) {
     currentCharList.add(subList.get(index));
    }
    temp>>=1;
    index++;
   }42    allsubsets.add(currentCharList);44   }
  return allsubsets;
 }
}

Remarque : 2017-02-08 10:01:32 Le code ci-dessus présente certaines failles, c'est-à-dire que lorsque l'entrée contient des nombres répétés, le résultat aura une sortie de sous-ensembles répétés, ce qui ne répond pas aux exigences de la question. et doit être calculé lorsque les sous-ensembles sont calculés. Ajoutez HashSet pour la déduplication, et le résultat d'impression final peut être obtenu à partir des ensembles. Les détails de modification spécifiques sont comme indiqué dans la figure ci-dessous :

1. Modifiez la valeur de retour acceptée là où la fonction principale s'imprime : Type HashSet

2. vous devez modifier la liste d'encapsulation et changer la liste pour définir

La modification est maintenant terminée et les résultats du test en cours d'exécution sont les suivants :

L'analyse du code peut être obtenue Sa complexité temporelle est : O(n*log2n)

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!