Um algoritmo para gerar subconjuntos de um conjunto satisfazer as condições certian

Question

Suponha que eu sou dado uma lista ordenada de elementos e eu quero gerar todos os subconjuntos satisfazer algumas condições, de modo que se um determinado conjunto não satisfaz a condição, então um subconjunto maior também não vai satisfazê-lo, e todos os conjuntos de um elemento fazer satisfazê-lo.

Por exemplo, dada uma lista de todos os inteiros positivos menores que 100, determinar subconjuntos cuja soma é menor do que 130: (100,29) (0,1,40), (0), etc ...

Como posso fazer isso (de preferência em Python)?

Obrigado! :)

Answer 1

Você pode gerar todos os subconjuntos usando um href="http://en.wikipedia.org/wiki/Branch_and_bound" rel="nofollow noreferrer"> Branch-and-bound técnica

Se você quer ser genérico sobre a restrição, acho que esta é a melhor estratégia.

Certifique-se de escrever de forma correta o código que gera os subconjuntos, caso contrário, você gera muitos tempo os mesmos subconjuntos: a fim de memoization evitar, o que pode ser demorado devido a mapear as pesquisas e introduzir sobrecarga de memória, você pode gerar os subconjuntos em que maneira:

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

Na verdade, os subconjuntos adicionados pela primeira invocação de GetAllSubsets não tem o primeiro elemento de objectsToFix, onde os subconjuntos adicionado pela segunda chamada (se a condição poda não é violada) têm esse elemento, então a interseção dos dois conjuntos de subconjuntos gerados está vazio.

Answer 2

Você pode construir seus conjuntos recursivamente, iniciando com o conjunto vazio e tentar adicionar mais elementos, desistindo de uma linha recursiva de execução se um dos subconjuntos (e, portanto, todos os seus superconjuntos) não cumprir a condição. Aqui está um pseudocódigo, assumindo uma S conjunto cuja condição satisfazer subconjuntos você gostaria de lista. Por conveniência, assumimos que os elementos de S pode ser indexado 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)
            }
    }
}

A primeira chamada seria com T como o conjunto vazio. Em seguida, todos os subconjuntos de S correspondentes a condição seria impresso. Esta estratégia baseia-se fundamentalmente no fato de que um subconjunto de S que não satisfazem a condição não pode ser contido em um que faz.

Answer 3

Há certamente maneiras de fazer isso, mas a menos que você pode restringir a condição de alguma forma, ele vai levar O (2 ^ n) passos. Se você considerar, por exemplo, uma condição de 1-100 onde todos os subconjuntos seriam selecionados (por exemplo, i para i em 1- n ), então você iria acabar enumerar todos os subconjuntos.

Você estaria olhando

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

Você pode obter o powerset do conjunto, basta gerar todos os números binários de 0 a s n -1, e escolhendo elemento i para o subconjunto quando mordeu i é 1.

Answer 4

Eu fiz algo semelhante para um algoritmo de geração de horário de aula. Nossa classe cronograma teve 2 elementos -. Uma lista de cursos adicionados ao calendário, e uma lista de cursos disponíveis para adicionar

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)

A idéia é começar com uma agenda vazia e a lista de classes disponíveis, e para procurar para baixo da árvore para horários válidos (significado válido se encaixa nos requisitos apresentados pelo usuário, não tem conflitos de tempo, etc). Se uma agenda é inválido, ele é jogado fora - não podemos fazer um agendamento inválido válido pela adição de aulas (ou seja, a poda da árvore)

.

Deve ser muito fácil de modificar este trabalho com o seu problema.

Answer 5

Aqui está um exemplo concreto de resposta das akappa, usando uma função recursiva para gerar os 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

Eu acho que na pior das hipóteses, você ainda tem que gerar todos os subconjuntos e calcular a soma de cada conjunto para determinar se ele é qualificar ou não. Assintoticamente, é o custo de subconjuntos gerando procedimento.

A seguir está o método que eu implementado em javascript para a mesma idéia.

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