Алгоритм генерации подмножеств множества, удовлетворяющих условиям certian

Question

Предположим, что мне задан отсортированный список элементов, и я хочу сгенерировать все подмножества, удовлетворяющие некоторому условию, так что если заданное множество не удовлетворяет условию, то большее подмножество также не удовлетворяет этому, и все множества одного элемента удовлетворяют этому.

Например, если список всех целых положительных чисел меньше 100, определите подмножества, сумма которых меньше 130: (100,29) (0,1,40), (0) и т. Д.

Как я могу это сделать (желательно на Python)?

Спасибо! :)

Answer 1

Вы можете сгенерировать все подмножества с использованием метода Branch-and-bound: вы можете генерировать все подмножества поэтапно (генерируя надмножество уже определенных подмножеств), используя в качестве условия чернослива «не исследует эту ветвь дерево, если корень не удовлетворяет ограничению ".

Если вы хотите быть общим в отношении ограничения, я думаю, что это лучшая стратегия.

Обязательно введите код, который генерирует подмножества, в противном случае вы создадите много времени для одних и тех же подмножеств: во избежание заметок, которые могут потребовать много времени из-за поиска карт и из-за нехватки памяти, вы может генерировать подмножества в этой манере:

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

В самом деле, подмножество, добавленное в первом вызове GetAllSubsets не имеет первый элемент objectsToFix, где подмножество добавленного второго вызова (если условие обрезки не нарушается) имеют этот элемент, поэтому пересечение двух наборов подмножеств порождено.

Answer 2

Есть, конечно, способы сделать это, но если вы не можете каким-либо образом ограничить условие, он будет принимать шаги O (2^n). Если рассматривать, например, условие 1-100, где будут выбраны все подмножества (например, < Σ я для я в 1- п), то вы бы в конечном итоге перечисления всех подмножеств.

Вы смотрели бы на

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

Вы можете получить Powerset Декорационных просто генерации всех двоичных чисел от 0 до с п -1, и выбирая элемент I для подмножества, когда бит i is 1.

Answer 3

Вы можете построить свои множества рекурсивно, начиная с пустого набора и пытаясь добавить больше элементов, отказываясь от рекурсивной строки выполнения, если одно из подмножеств (и, следовательно, все его надмножества) не удовлетворяет условию. Вот какой-то псевдокод, предполагающий набор S, удовлетворяющий условиям, который вы хотите перечислить. Для удобства будем считать, что элементы S могут быть проиндексированы в качестве х (0), х (1), х (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) 
      } 
    } 
} 

Первый вызов будет с Т как пустое множество. Затем будут напечатаны все подмножества S, соответствующие условию. Эта стратегия в решающей степени зависит от того, что подмножество S, которое не удовлетворяет условию, не может содержаться в том, что делает.

Answer 4

Я сделал что-то подобное для алгоритма генерации расписания классов.В нашем классе расписания было 2 элемента - список курсов, добавленных в расписание, и список курсов, которые можно добавить.

псевдокод:

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) 

Идея заключается в том, чтобы начать с пустой график и список доступных классов, а также для поиска по дереву для действительных графиков (действительный смысл соответствует требованиям, указанным пользователем, Безразлично конфликты времени и т. д.). Если расписание недействительно, оно выбрасывается - мы не можем сделать недопустимое расписание действительным, добавляя классы (т. Е. Обрезая дерево).

Должно быть довольно легко изменить это, чтобы работать с вашей проблемой.

Answer 5

Вот конкретный пример ответа akappa, используя рекурсивную функцию для генерации подмножеств:

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

Я думаю, что в самом худшем случае, вы должны создать все подмножества и рассчитать сумму каждого набора в определить, является ли оно подходящим или нет. Асимптотически, это процедура генерации подмножеств.

Ниже приведен метод, который я реализовал в javascript для той же идеи.

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