Un algorithme permettant de générer des sous-ensembles d'un ensemble satisfaisant les conditions certian

Question

Si je me donne une liste triée des éléments et je veux générer tous les sous-ensembles satisfaisant certaines conditions, de sorte que si un ensemble donné ne satisfait pas à la condition, un sous-ensemble plus grand satisfera pas non plus, et tous les ensembles d'un élément ne le satisfont.

Par exemple, étant donné une liste de tous les entiers positifs plus petits que 100, de déterminer des sous-ensembles dont la somme est inférieure à 130: (100,29) (0,1,40), (0), etc ...

Comment puis-je faire (de préférence en Python)?

Merci! :)

Answer 1

Vous pouvez générer tous les sous-ensembles en utilisant un technique Branch-and-bound : vous pouvez générer tous les sous-ensembles de façon incrémentale (générant surensemble de sous-ensembles déjà déterminés), en utilisant en tant que condition de prune « ne pas explorer cette branche de l'arbre si la racine ne satify pas la contrainte ».

Si vous voulez être générique en ce qui concerne la contrainte, je pense que c'est la meilleure stratégie.

Assurez-vous d'écrire d'une manière correcte le code qui génère les sous-ensembles, sinon vous générer beaucoup de temps les mêmes sous-ensembles: afin d'éviter memoization, ce qui peut prendre beaucoup de temps en raison de la carte lookups et introduire la mémoire au-dessus, vous pouvez générer les sous-ensembles de cette manière:

GetAllSubsets(List objects) {
    List generated = {};
    GetAllSubsets(generated, [], objects);
    return generated;
}

GetAllSubsets(List subsetGenerated, List objectFixed, List objectsToFix) {
    GetAllSubsets(subsetGenerated, objectFixed, objectsToFix.sublist(1, objectsToFix.length());
    if (satisfy(toCheck = objectsFixed.add(objectsToFix.get(0)))) {
        subsetGenerated.add(toCheck);
        GetAllSubsets(subsetGenerated, toCheck, objectsToFix.sublist(1, objectsToFix.length());
    }
}

En fait, les sous-ensembles ajoutés par le premier appel de GetAllSubsets n'a pas le premier élément de objectsToFix, où les sous-ensembles ajoutés par le deuxième appel (si la condition de la taille ne soit pas violé) ont cet élément, de sorte que l'intersection des deux ensembles de sous-ensembles générés est vide.

Answer 2

Vous pouvez construire vos jeux récursive, en commençant par l'ensemble vide et en essayant d'ajouter d'autres éléments, donnant sur une ligne récurrente d'exécution si l'un des sous-ensembles (et donc tous ses supersets) ne respecte pas la condition. Voici quelques pseudo-code, en supposant un ensemble S dont les sous-ensembles-vérifiant la condition que vous souhaitez à la liste. Pour plus de commodité, on suppose que les éléments de S peuvent être indexées en tant que x (0), x (1), x (2), ...

EnumerateQualifyingSets(Set T)
{
    foreach (x in S with an index larger than the index of any element in T)
    {
            U = T union {x}

            if (U satisfies condition)
            {
                print U
                EnumerateQualifyingSets(U)
            }
    }
}

Le premier appel serait avec T comme l'ensemble vide. Ensuite, tous les sous-ensembles de S correspondant à la condition seront imprimés. Cette stratégie repose fondamentalement sur le fait qu'un sous-ensemble de S qui ne répond pas à la condition ne peut être contenue dans celui qui le fait.

Answer 3

Il y a certainement des façons de le faire, mais à moins que vous pouvez limiter la condition d'une certaine manière, il va prendre O (2 ^ n) étapes. Si l'on considère, par exemple une condition sur 1-100 où tous les sous-ensembles seront sélectionnés (par exemple, <Σ i pour i 1- n ), alors vous finiriez tous les sous-ensembles énumérer.

Vous souhaitez regarderez

for i in the powerset of {1-n}
    if cond(i)
       note that set

Vous pouvez obtenir le powerset de l'ensemble en générant simplement tous les nombres binaires de 0 à s n -1 et élément i pour choisir le sous-ensemble lorsque le bit i est 1.

Answer 4

Je l'ai fait quelque chose de similaire pour un algorithme de génération de programmes de classe. Notre classe horaire avait 2 éléments -. Une liste des cours ajoutés au programme, et une liste des cours disponibles pour ajouter

pseudocode:

queue.add(new schedule(null, available_courses))
while( queue is not empty )
    sched = queue.next()
    foreach class in sched.available_courses
        temp_sched = sched.copy()
        temp_sched.add(class)
        if(temp_sched.is_valid())
            results.add(temp_sched)
            queue.add(temp_sched)

L'idée est de commencer avec un calendrier vide et la liste des classes disponibles, et pour rechercher dans l'arbre pour les horaires valides (sens valide correspond aux exigences données par l'utilisateur, ne dispose pas de conflits de temps, etc.). Si un programme est invalide, il est jeté - nous ne pouvons pas faire un programme invalide valide en ajoutant des classes (c.-à la taille de l'arbre)

.

Il devrait être assez facile de modifier cela fonctionne avec votre problème.

Answer 5

Voici un exemple concret de la réponse de akappa, en utilisant une fonction récursive pour générer les sous-ensembles:

def restofsubsets(goodsubset, remainingels, condition):
    answers = []
    for j in range(len(remainingels)):
        nextsubset = goodsubset + remainingels[j:j+1]
        if condition(nextsubset):
            answers.append(nextsubset)
            answers += restofsubsets(nextsubset, remainingels[j+1:], condition)
    return answers

 #runs slowly
 easieranswer = restofsubsets([], range(101), lambda l:sum(l)<40)

 #runs much faster due to eliminating big numbers first
 fasteranswer = restofsubsets([], range(100,-1,-1), lambda l:sum(l)<40)

 #runs extremely slow even with big-numbers-first strategy
 finalanswer = restofsubsets([], range(100,-1,-1), lambda l:sum(l)<130)

Answer 6

Je pense que dans le pire des cas, vous devez toujours générer tous les sous-ensembles et calculer la somme de chaque jeu pour déterminer si elle est admissible ou non. Asymptotiquement, il est le coût des sous-ensembles procédure de production.

Ce qui suit est la méthode que je javascript pour Mis en œuvre en la même idée.

//this is to generate an array to test
var numbers = (function(start, end){
    var result = [],
        i =  start; 
    for(; i <= end; i++){
        result.push(i);
    }
    return result; 
})(1, 12);

//this is the qualifying function to determine if the generated array is qualified
var fn = (function(maxSum){
    return function(set){
        var sum = 0;
        for(var i = 0 ; i< set.length; i++){
            sum += set[i];
            if( sum > maxSum ){
                return false;
            }
        }
        return true;
    }
})(30);

//main function
(function(input, qualifyingFn){
    var result, mask, total = Math.pow(2, input.length);
    for(mask = 0; mask < total; mask++){

        result = [];
        sum = 0;

        i = input.length - 1; 
        do{
            if( (mask & (1 << i)) !== 0){
                result.push(input[i]);
                sum += input[i];
                if( sum > 30 ){
                    break;
                }
            }
        }while(i--);
        if( qualifyingFn(result) ){
            console.log(JSON.stringify(result));
        }
    }

})(numbers, fn);