Comment vérifier si une liste est un sous-ensemble d'une autre liste en java?

L'approche pour résoudre ce problème est très similaire à la résolution d'un problème de correspondance de sous-chaînes.

Vous commencez par vérifier si le premier élément de la liste supposée des sous-ensembles (qui sera dorénavant référencé comme SSL).

Une fois que vous obtenez une correspondance, notez l'index (désormais désigné sous le nom de myGuy dans la liste principale où la correspondance est trouvée, vérifiez si les éléments suivants de SSL correspond à la liste principale.

Si votre correspondance est complète, retournez simplement. Sinon, vous pouvez faire l'une des deux. S'il reste des éléments dans la liste principale, incrémentez myGuy strong > puis il devient le nouvel index à partir duquel vous commencez à itérer dans la liste principale.
S'il ne reste aucun élément et qu'il n'y a toujours pas de correspondance complète, ce n'est pas un sous-ensemble.

Voici comment vous pouvez le faire en Java:

private static boolean checkSubList(int[] mainList, int[] subList) {
    int currentIteratingPointer;
    int matchCounter = 0;

    for (int i = 0; i < mainList.length; i++) {
        currentIteratingPointer = i;
        for (int j = 0; j < subList.length; j++) {
            if (mainList[currentIteratingPointer] == subList[j]) {
                System.out.println(mainList[currentIteratingPointer]);
                ++matchCounter;
                ++currentIteratingPointer;
            } else {
                --matchCounter;
                break;
            }
        }

        i = currentIteratingPointer;
    }

    return matchCounter == subList.length; // You can count the number of occurance of the sublist if you change
    // it to int and return the matchCounter a
}

Essayez cette source

public class ListTest {

    List small = new ArrayList<>();
    List big = new ArrayList<>();

    public static void main(String args[]) {
        ListTest g = new ListTest();

        g.populateList();
        boolean bFlag = g.checkIfSubset();
        System.out.println("====is subset====>" + bFlag);
    }

    private boolean checkIfSubset() {
        for (Object in : small) {
            if (!big.contains(in)) {
                return false;
            }
        }
        return true;
    }

    private void populateList() {
        small.add(11);
        small.add(23);

        big.add(11);
        big.add(2);
        big.add(23);
        big.add(24);
    }

}

Le problème est que contient pour Set serait bien (pour les nombres uniques), mais pour List un contient naïf nécessite deux boucles imbriquées , complexité quadratique O (N²): deux listes de 100 éléments nécessiteraient 10 000 pas. Par conséquent, il faut soit convertir la (les) liste (s) en ensembles, soit trier les listes.

Le tri des listes peut être O (N log N), mais pour une liste chaînée telle que vous semblez l'avoir reste le même:

public boolean contains(ItemsList ilist) {
    ItemsList sortedThis = this.sorted();
    ItemsList sortedOther = iList.sorted();
    ItemNode node = sortedThis.first;
    ItemNode other = otherList.first;
    while (node != null) {
        if (other == null) {
            break; // return true;
        }
        if (other.item < node.item) {
            break; // return false;
        }
        if (other.item == node.item) {
            other = other.next; // Match found.
        }
        node = node.next;
    }
    return other == null;
}

Mais après le tri, vous pouvez faire comme vous l'avez dit, avec une complexité linéaire O (N).

public ItemsList sort(ItemsList list) {
    ItemsList sortedList = new ItemsList();
    for (ItemNode node : list) {
        sortedList.insertSorted(node.item);
    }
    return sortedList;
}

Les listes pouvant contenir des doublons, optez pour le tri.

Donc, fondamentalement, vous voulez trouver des anagrammes d'une liste dans une autre.

voici mon implémentation pour les anagrammes de chaîne

abcde, dbc -> true

Vérifiez mon code et essayez de l'implémenter dans votre cas d'utilisation.

public boolean findStringAnagrams(String str, String pattern) {


        Map<Character, Integer> charMap = new HashMap<>();
        for (int i = 0; i < pattern.length(); i++) {
            charMap.put(pattern.charAt(i), charMap.getOrDefault(pattern.charAt(i), 0) + 1);
        }

        Integer windowStart = pattern.length() - 1;
        for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {

            Character c = str.charAt(windowEnd);
            charMap.computeIfPresent(c, (key, val) -> val - 1);
            if (charMap.containsKey(c) && charMap.get(c) == 0)
                charMap.remove(c);

            if (windowStart < windowEnd) {

                if (charMap.size() == 0) {
                    return true;
                }
                charMap.put(str.charAt(windowStart), charMap.getOrDefault(str.charAt(windowStart), 0) + 1);
                windowStart++;
            }

        }

        return false;
    }