خوارزمية لتوليد مجموعات فرعية من شروط شهادات مرضية

Question

لنفترض أنني أعطيت قائمة عناصر مرتبة وأريد توليد جميع المجموعات الفرعية مرضية بعض الشرط، بحيث إذا لم تلبي مجموعة معينة الشرط، فإن مجموعة فرعية أكبر لن ترضيها أيضا، وتلبي جميع مجموعات عنصر واحد هو - هي.

على سبيل المثال، بالنظر إلى قائمة جميع الأعداد الصحيحة الإيجابية أصغر من 100، حدد مجموعات فرعية من مجموعها أصغر من 130: (100،29) (0،1،40)، (0)، إلخ ...

كيف يمكنني أن أفعل ذلك (يفضل أن يكون في بيثون)؟

شكرا! :)

Answer 1

يمكنك توليد جميع المجموعات الفرعية باستخدام فرع تقنية: يمكنك توليد جميع المجموعات الفرعية في الأزياء الإضافية (توليد استبدال مجموعات فرعية تحدد بالفعل بالفعل)، باستخدام كشرط PRUNE "لا يستكشف هذا الفرع من الشجرة إذا كان الجذر لا يضع القيد".

إذا كنت تريد أن تكون عام فيما يتعلق بالقيد، أعتقد أن هذه هي أفضل استراتيجية.

تأكد من الكتابة بالطريقة الصحيحة التي ينشئها الكود الفرعي الذي ينشئ الفرع الفرعي، وإلا فإنك تولد الكثير من الوقت تقريبا: من أجل تجنب التذكرة، والتي يمكن أن تكون تستغرق وقتا طويلا بسبب عمليات البحث في الخريطة وإدخال النفقات العامة للذاكرة، يمكنك إنشاء مجموعة فرعية بهذه الطريقة:

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

يمكنك إنشاء مجموعاتك بشكل متكرر، بدءا من المجموعة الفارغة ومحاولة إضافة المزيد من العناصر، والتخلي عن خط التنفيذ العسكري إذا فشل أحد المجموعات الفرعية (وبالتالي كل ما من كبديلها) في تلبية الحالة. إليك بعض Pseudoodocode، على افتراض مجموعة صفحات مجموعتها التي تلبي حالتها التي ترغب في سردها. للراحة، افترض أن عناصر 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 التي لا تلبي الشرط لا يمكن تضمينها في واحدة تفعل ذلك.

Answer 3

هناك بالتأكيد طرق للقيام بذلك، ولكن ما لم تتمكن من تقييد الحالة بطريقة أو بأخرى، فإنها ستأخذ خطوات O (2 ^ n). إذا كنت تعتبر، على سبيل المثال شرطا في 1-100 حيث سيتم اختيار جميع المجموعات الفرعية (على سبيل المثال، <σ أنا بالنسبة أنا في 1-ن)، ثم ينتهي بك المطاف تعداد جميع المجموعات الفرعية.

كنت تبحث في

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

يمكنك الحصول على Powerset of the set بواسطة ببساطة توليد جميع الأرقام الثنائية من 0 إلى Sن-1، واختيار العنصر الأول من أجل المجموعة الفرعية عندما يكون قليلا 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

أفكر في أسوأ الحالات، لا يزال يتعين عليك توليد جميع مجموعات فرعية وحساب مجموع كل مجموعة لتحديد ما إذا كان مؤهلا أم لا. مقاربة، إنها تكلفة إجراءات توليد فرعية.

فيما يلي الطريقة التي قمت بتنفيذها في جافا سكريبت لنفس الفكرة.

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