Um algoritmo para gerar subconjuntos de um conjunto satisfazer as condições certian
Pergunta
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! :)
Solução
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: 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. 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());
}
}
Outras dicas
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.
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.
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.
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)
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);