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

Question

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

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

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

Спасибо!:)

Answer 1

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

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

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

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

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

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

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

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

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