Un algoritmo para generar subconjuntos de un conjunto que satisface ciertas condiciones.

Question

Supongamos que me dan una lista ordenada de elementos y quiero generar todos los subconjuntos que satisfagan alguna condición, de modo que si un conjunto dado no satisface la condición, entonces un subconjunto más grande tampoco la satisfará, y todos los conjuntos de un elemento sí la satisfacen. él.

Por ejemplo, dada una lista de todos los números enteros positivos menores que 100, determine los subconjuntos cuya suma sea menor que 130:(100,29) (0,1,40), (0), etc...

¿Cómo puedo hacer eso (preferiblemente en Python)?

¡Gracias!:)

Answer 1

Puede generar todos los subconjuntos utilizando un técnica Branch-and-bound : se puede generar todos los subconjuntos en forma incremental (generando superconjunto de subconjuntos ya determinados), utilizando como condición de ciruela "no explora esta rama del árbol si la raíz no satify la restricción".

Si quieres ser genérica respecto de la restricción, creo que esta es la mejor estrategia.

Asegúrese de escribir de manera correcta el código que genera los subconjuntos, de lo contrario se genera muchas veces los mismos subconjuntos: a fin de evitar memoization, lo que puede llevar mucho tiempo, debido a mapear las búsquedas e introducir sobrecarga de la memoria, se puede generar los subconjuntos de esa manera:

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

De hecho, los subconjuntos añadidas por la primera invocación de GetAllSubsets no tiene el primer elemento de objectsToFix, donde los subconjuntos añadida por la segunda llamada (si la condición poda no se viola) tienen ese elemento, por lo que la intersección de los dos conjuntos de subconjuntos generados es vacía.

Answer 2

Se podría construir su conjunto de forma recursiva, comenzando con el conjunto vacío y tratando de añadir más elementos, renunciar a una línea recursiva de ejecución si uno de los subconjuntos (y por lo tanto todas sus superseries) no cumple la condición. Aquí hay algo de pseudocódigo, asumiendo un conjunto S cuya condición satisface subconjuntos que le gustaría a la lista. Por conveniencia, se supone que los elementos de S se pueden indexar como 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)
            }
    }
}

La primera llamada sería con T como el conjunto vacío. Entonces, todos los subconjuntos de S búsqueda de la condición se pueden imprimir. Esta estrategia se basa fundamentalmente en el hecho de que un subconjunto de S que no cumple la condición no puede estar contenido en uno que lo haga.

Answer 3

Es cierto que hay maneras de hacerlo, pero a menos que pueda limitar la condición de alguna manera, va a tomar O (2 ^ n) pasos. Si se tiene en cuenta, por ejemplo, una condición de 1-100, donde se seleccionarán todos los subconjuntos (por ejemplo, <Σ i i en 1- n ), entonces usted podría terminar la enumeración de todos los subconjuntos.

Se podrían buscar a

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

Usted puede obtener el powerset del conjunto simplemente generar todos los números binarios de 0 a s n -1, y el elemento i elegir para el subconjunto cuando el bit i es 1.

Answer 4

Hice algo similar para un algoritmo de generación de horarios de clases.Nuestro cronograma de clases tenía 2 elementos: una lista de cursos agregados al cronograma y una lista de cursos disponibles para agregar.

Pseudocódigo:

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)

La idea es comenzar con un horario vacío y la lista de clases disponibles, y buscar en el árbol horarios válidos (el significado válido se ajusta a los requisitos dados por el usuario, no tiene conflictos de tiempo, etc.).Si una programación no es válida, se descarta; no podemos hacer que una programación no válida sea válida agregando clases (es decir, podando el árbol).

Debería ser bastante fácil modificar esto para que funcione con su problema.

Answer 5

Aquí hay un ejemplo concreto de la respuesta de akappa, utilizando una función recursiva para generar los subconjuntos:

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

Creo que en el peor de los casos, usted todavía tiene que generar todos los subconjuntos y calcular la suma de cada conjunto para determinar si es o no pasa. Asintóticamente, es el costo de subconjuntos de generación de procedimiento.

El siguiente es el método que he implementado en javascript para la misma idea.

//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);