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

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

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

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

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

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

Конечно, есть способы сделать это, но если вы не можете каким-то образом ограничить условие, это займет 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.

Я сделал что-то подобное для алгоритма генерации расписания занятий. В нашем классе расписания было 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)

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

Это должно быть довольно легко изменить для работы с вашей проблемой.

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

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)

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

Ниже приведен метод, который я реализовал в 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);