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

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

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

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

Answer 3

Вот конкретный пример ответа 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 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

Конечно, есть способы сделать это, но если вы не можете каким-то образом ограничить условие, оно будет делать O (2 ^ n) шагов. Например, если рассмотреть условие 1–100, в котором будут выбраны все подмножества (например, <& Sigma; <em>i для i в 1- n ), тогда вы в конечном итоге перечислите все подмножества.

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

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

Вы можете получить powerset набора, просто сгенерировав все двоичные числа от 0 до s n -1 и выбрав элемент i для подмножества, когда бит i равен 1.

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