توليد مجموعات تطلبها سمة

Question

أبحث عن طريقة لإنشاء مجموعات من الكائنات التي تم طلبها بواسطة سمة واحدة. لا أعتقد أن الأمر المعجم هو ما أبحث عنه ... سأحاول إعطاء مثال. دعنا نقول أن لدي قائمة بالكائنات A ، B ، C ، D مع قيم السمة التي أريد طلبها من خلال 3،3،2،1. هذا يعطي كائنات A3 ، B3 ، C2 ، D1. الآن أريد إنشاء مجموعات من كائنين ، لكن يجب طلبها بطريقة تنازلية:

• A3 B3
• A3 C2
• B3 C2
• A3 D1
• B3 D1
• C2 D1

إن توليد جميع المجموعات وفرزها غير مقبول لأن سيناريو العالم الحقيقي يتضمن مجموعات كبيرة وملايين المجموعات. (مجموعة من 40 ، ترتيب 8) ، وأنا بحاجة فقط إلى مجموعات أعلى من حد معين.

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

تحرير - سؤالي الأصلي لم يكن دقيقًا جدًا ... لا أحتاج فعليًا إلى طلب هذه المجموعات ، فقط أعتقد أنه سيساعد على عزل المجموعات فوق العتبة. لكي أكون أكثر دقة ، في المثال أعلاه ، مع إعطاء عتبة 5 ، أبحث عن معلومات تنتجها المجموعة المحددة مزيجًا واحدًا بمبلغ 6 (A3 B3) و 2 بمبلغ 5 (A3 C2 ، B3 C2). أنا في الواقع لا أحتاج إلى المجموعات نفسها.

كنت أبحث في مشكلة مجموعة فرعية ، لكن إذا فهمت حلًا ديناميكيًا بشكل صحيح ، فلن يعطيك سوى المعلومات هل هناك مبلغ معين أو لا ، وليس حساب المبالغ.

شكرًا

Answer 1

في الواقع ، أعتقد أنك فعل تريد ترتيب المعجم ، ولكن الهبوط بدلا من الصعود. بالإضافة الى:

• ليس من الواضح لي من وصفك أن A ، B ، ... D تلعب أي دور في إجابتك (باستثناء ربما كحاوية للقيم).
• أعتقد أن مثال سؤالك هو ببساطة "لكل عدد صحيح على الأقل 5 ، يصل إلى الحد الأقصى لإجمالي قيمتين ، كم عدد الأزواج المتميزة من المجموعة {3 ، 3 ، 2 ، 1} لها مبالغ من هذا عدد صحيح؟"
• الجزء المثير للاهتمام هو الإنقاذ المبكر ، بمجرد عدم الوصول إلى حل ممكن (المبالغ المتبقية قابلة للتحقيق صغيرة جدًا).

سأقوم بنشر نموذج رمز لاحقًا.

إليك رمز العينة الذي وعدت به ، ببعض الملاحظات التالية:

public class Combos {

    /* permanent state for instance */
    private int values[];
    private int length;

    /* transient state during single "count" computation */
    private int n;
    private int limit;
    private Tally<Integer> tally;
    private int best[][];  // used for early-bail-out

    private void initializeForCount(int n, int limit) {
        this.n = n;
        this.limit = limit;
        best = new int[n+1][length+1];
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= length - i; ++j) {
                best[i][j] = values[j] + best[i-1][j+1];
            }
        }
    }

    private void countAt(int left, int start, int sum) {
        if (left == 0) {
            tally.inc(sum);
        } else {
            for (
                int i = start;
                i <= length - left
                && limit <= sum + best[left][i];  // bail-out-check
                ++i
            ) {
                countAt(left - 1, i + 1, sum + values[i]);
            }
        }
    }

    public Tally<Integer> count(int n, int limit) {
        tally = new Tally<Integer>();
        if (n <= length) {
            initializeForCount(n, limit);
            countAt(n, 0, 0);
        }
        return tally;
    }

    public Combos(int[] values) {
        this.values = values;
        this.length = values.length;
    }

}

ملاحظات المقدمة:

يستخدم هذا فئة مساعدة صغيرة تسمى Tally ، والتي تعزل الجدولة (بما في ذلك التهيئة لمفاتيح لم يسبق لها مثيل). سأضعه في النهاية.

للحفاظ على هذا موجز ، أخذت بعض الاختصارات التي ليست ممارسة جيدة للرمز "الحقيقي":

• هذا لا يتحقق من صفيف قيمة فارغ ، إلخ.
• أفترض أن صفيف القيمة يتم فرزه بالفعل في ترتيب تنازلي ، المطلوب لتقنية الخروج في وقت مبكر. (سيشمل رمز الإنتاج الجيد الفرز.)
• أضع بيانات عابرة في متغيرات الأمثلة بدلاً من تمريرها كوسائط بين الأساليب الخاصة التي تدعم count. وهذا يجعل هذه الفئة غير آمنة.

تفسير:

مثال Combos يتم إنشاؤه باستخدام مجموعة من الأعداد الصحيحة (المطلوبة) للجمع. ال value تم إعداد Array مرة واحدة لكل مثيل ، ولكن مكالمات متعددة إلى count يمكن أن تصنع بأحجام وحدود السكان المختلفة.

ال count الطريقة تؤدي إلى (في الغالب) اجتيازًا متكررًا قياسيًا لمجموعات فريدة من n الأعداد الصحيحة من values. ال limit الحجة تعطي الحد الأدنى على مبالغ الاهتمام.

ال countAt الطريقة تفحص مجموعات الأعداد الصحيحة من values. ال left الحجة هي عدد الأعداد الصحيحة التي تبقى للتعويض n الأعداد الصحيحة في مبلغ ، start هو الموقف في values من أي للبحث ، و sum هو المبلغ الجزئي.

تعتمد آلية التغلب المبكر على الحوسبة best, ، صفيف ثنائي الأبعاد يحدد المبلغ "الأفضل" الذي يمكن الوصول إليه من دولة معينة. القيمة في best[n][p] هو أكبر مبلغ من n القيم التي تبدأ في الموقف p من الأصل values.

عودة countAt القيعان عندما تم تجميع السكان الصحيحين ؛ هذا يضيف التيار sum (من n القيم) إلى tally. إذا countAt لم يتجه إلى أسفل ، فهو يكتسح values من start-موقف لزيادة الجزئي الحالي sum, ، طالما:

• ما يكفي من المواقف في values لتحقيق السكان المحددين ، و
• ال best (أكبر) المتبقية الفرعية كبيرة بما يكفي لجعل limit.

نموذج تشغيل مع بيانات سؤالك:

    int[] values = {3, 3, 2, 1};
    Combos mine = new Combos(values);
    Tally<Integer> tally = mine.count(2, 5);
    for (int i = 5; i < 9; ++i) {
        int n = tally.get(i);
        if (0 < n) {
            System.out.println("found " + tally.get(i) + " sums of " + i);
        }
    }

تنتج النتائج التي حددتها:

found 2 sums of 5
found 1 sums of 6

هذا هو رمز العهد:

public static class Tally<T> {
    private Map<T,Integer> tally = new HashMap<T,Integer>();
    public Tally() {/* nothing */}
    public void inc(T key) {
        Integer value = tally.get(key);
        if (value == null) {
            value = Integer.valueOf(0);
        }
        tally.put(key, (value + 1));
    }
    public int get(T key) {
        Integer result = tally.get(key);
        return result == null ? 0 : result;
    }
    public Collection<T> keys() {
        return tally.keySet();
    }
}

Answer 2

لقد كتبت فئة للتعامل مع الوظائف الشائعة للعمل مع معامل ذي الحدين ، وهو نوع المشكلة التي تندرج فيها مشكلتك. ينفذ المهام التالية:

1. يخرج جميع المؤشرات K بتنسيق لطيف لأي n اختر K إلى ملف. يمكن استبدال المؤشرات K بسلاسل أو حروف أكثر وصفية. هذه الطريقة تجعل حل هذا النوع من المشكلات تافهة للغاية.

2. يحول المؤشرات K إلى الفهرس الصحيح للإدخال في جدول معامل الحدين المصنفة. هذه التقنية أسرع بكثير من التقنيات المنشورة القديمة التي تعتمد على التكرار. يفعل هذا باستخدام خاصية رياضية متأصلة في مثلث باسكال. ورقتي تتحدث عن هذا. أعتقد أنني أول من اكتشف ونشر هذه التقنية ، لكنني قد أكون مخطئًا.

3. يحول الفهرس في جدول معامل ذي الحدين المصنفة إلى المؤشرات K المقابلة.

4. الاستخدامات مارك دومينوس طريقة لحساب معامل الحدين ، والذي من غير المرجح أن يفيض ويعمل بأعداد أكبر.

5. يتم كتابة الفصل في .NET C# ويوفر وسيلة لإدارة الكائنات المتعلقة بالمشكلة (إن وجدت) باستخدام قائمة عامة. يأخذ مُنشئ هذه الفئة قيمة منطقية تسمى inittable أنه عندما يقوم TRUE بإنشاء قائمة عامة لإمساك الكائنات المراد إدارة. إذا كانت هذه القيمة خاطئة ، فلن تنشئ الجدول. لا يلزم إنشاء الجدول من أجل تنفيذ الطرق الأربعة أعلاه. يتم توفير أساليب الملحق للوصول إلى الجدول.

6. هناك فئة اختبار مرتبطة توضح كيفية استخدام الفصل وطرقه. لقد تم اختباره على نطاق واسع مع حالتين وليس هناك حشرات معروفة.

لقراءة عن هذه الفئة وتنزيل الكود ، انظر تقديم المعامل ذو الحدين.

Answer 3

تحقق من هذا السؤال في Stackoverflow: خوارزمية لإرجاع كل التركيبةس

لقد استخدمت أيضًا رمز Java أدناه لإنشاء جميع التباديل ، ولكن يمكن استخدامه بسهولة لإنشاء فهرس فريد من نوعه.

public static <E> E[] permutation(E[] s, int num) {//s is the input elements array and num is the number which represents the permutation

    int factorial = 1;

    for(int i = 2; i < s.length; i++)
        factorial *= i;//calculates the factorial of (s.length - 1)

    if (num/s.length >= factorial)// Optional. if the number is not in the range of [0, s.length! - 1] 
        return null;

    for(int i = 0; i < s.length - 1; i++){//go over the array

        int tempi = (num / factorial) % (s.length - i);//calculates the next cell from the cells left (the cells in the range [i, s.length - 1])
        E temp = s[i + tempi];//Temporarily saves the value of the cell needed to add to the permutation this time 

        for(int j = i + tempi; j > i; j--)//shift all elements to "cover" the "missing" cell
            s[j] = s[j-1];

        s[i] = temp;//put the chosen cell in the correct spot

        factorial /= (s.length - (i + 1));//updates the factorial

    }

    return s;
}

Answer 4

أنا آسف للغاية (بعد كل هذه التوضيحات في التعليقات) لأقول إنه لا يمكنني العثور على حل فعال لهذه المشكلة. حاولت على مدار الساعة الماضية دون نتائج.

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

يبدو أن هناك خدعة ذكية يمكنها حل هذه الفئة من المشاكل.

لا يزال هناك العديد من التحسينات التي يمكنك القيام بها للرمز الفعلي.

حاول فرز البيانات وفقًا للسمات. قد تكون قادرًا على تجنب معالجة بعض القيم من القائمة عندما تجد أن القيمة الأعلى لا يمكن أن تلبي العتبة (بحيث يمكن القضاء على جميع القيم المنخفضة).

Answer 5

إذا كنت تستخدم C# ، فهناك مكتبة عامة جيدة إلى حد ما هنا. لاحظ على الرغم من أن توليد بعض التباديل ليس في ترتيب معجمي

Answer 6

إليك نهج عودية عدد عدد هذه المجموعات الفرعية: نحدد وظيفة count(minIndex,numElements,minSum) الذي يعيد عدد المجموعات الفرعية من الحجم numElements من هو على الأقل minSum, ، تحتوي على عناصر مع المؤشرات minIndex أو أكبر.

كما هو الحال في بيان المشكلة ، نقوم بفرز عناصرنا في ترتيب تنازلي ، على سبيل المثال [3،3،2،1] ، ونقوم بالاتصال بالفهرس الأول صفر ، والعدد الإجمالي للعناصر N. نفترض أن جميع العناصر غير سالبة. للعثور على جميع الأتباع 2 التي لا يقل عن مجموعها 5 ، نسميها count(0,2,5).

عينة من الرموز (جافا):

int count(int minIndex, int numElements, int minSum)
{
    int total = 0;

    if (numElements == 1)
    {
        // just count number of elements >= minSum
        for (int i = minIndex; i <= N-1; i++)
            if (a[i] >= minSum) total++; else break;
    }
    else
    {
        if (minSum <= 0)
        {
            // any subset will do (n-choose-k of them)
            if (numElements <= (N-minIndex))
                total = nchoosek(N-minIndex, numElements);
        }
        else
        {
            // add element a[i] to the set, and then consider the count
            // for all elements to its right
            for (int i = minIndex; i <= (N-numElements); i++)
                total += count(i+1, numElements-1, minSum-a[i]);
        }
    }

    return total;
}

راجع للشغل ، لقد قمت بتشغيل ما سبق مع مجموعة من 40 عنصرًا ، وحجم 8 مجموعات فرعية وعادت باستمرار نتائج أقل من ثانية.