التوافقية:بناء 10 مجموعات من 100 عناصر حين تبقى العناصر فرز

Question

لدي مشكلة بخصوص التوافقية.للأسف لا أستطيع وصف ذلك تجريدي لذلك أنا أحاول أن أشرح أنها قصة.:)

المشكلة:

1. هناك 100 طفل في المدرسة.
2. لديهم كل فريدة من نوعها مرتفعات ، على افتراض أن القيم هي 100-199cm.
3. كنت ترغب في بناء 10 مجموعات تتألف كل منها من 1-99 الأطفال.
4. كيف يمكنك بناء جميع المجموعات في حين أن الأطفال يجب أن تكون مرتبة حسب طولهم ؟
5. أنا في حاجة إلى كل الحلول الممكنة لهذه الجماعات منذ ذلك ليس من الصعب العثور على واحد كوكبة.

قصيرة و سهلة:

كل 100 طفل تقف جنبا إلى جنب.عليك فقط أن تقرر إلى أين تقسيمها إلى مجموعات تجد جميع الحلول من أجل هذا.

مثال (القيم مرتفعات):

[120 ... 190 ... 199] ... [126 ... 137 ... 144 ... 188] غير ممكن

[101] ... [104 ... 105 ... 112 ... 149] ... [169 ... 189] ممكن

آمل أن تتمكن من مساعدتي.شكرا جزيلا لك مقدما!

PS:فإنه ليس من الواجبات المنزلية.;) عادة ، أحتاج إلى وظيفة الذي يفعل هذا مع الأرقام.ولكن أنا لا يمكن أن تصف هذا تجريدي مثل "بناء k مجموعات من الأرقام في حين أن جميع أرقام فرز".أعتقد أنك لن تفهم الأمر على هذا النحو.:) الحل في PHP سيكون أفضل ولكن سأكون سعيدا لرؤية الحلول في اللغات الأخرى أيضا.:)

Answer 1

كما فهمت أنت فعال يسأل عن طرق تقسيم الفترة [100,199] في 10 أجزاء ، أيكنت تريد أن تجد أرقام x[0], ..., x[10] مثل:

x[0] = 100 < x[1] < x[2] < ... < x[9] < x[10] = 199

تحديد وظيفة العودية partition(intervalSize, pieces) والتي تهم عدد من الطرق لتقسيم فترة معينة.أنت بعد partition(100, 10).

التالية كود جافا التهم الأقسام (آسف لا أعرف PHP ذلك جيدا):

public class Partitions
{
    static long[][] partitions = new long[100][10];

    private static long partition(int intervalSize, int pieces)
    {
        if (partitions[intervalSize-1][pieces-1] != 0) {
            return partitions[intervalSize-1][pieces-1];
        }
        long partition = 0L;
        if (pieces == 1) {
            partition = 1L;
        } else {
            for (int i = 1; i <= intervalSize - 1; i++) {
                partition += partition(intervalSize - i, pieces - 1);
            }
        }
        partitions[intervalSize-1][pieces-1] = partition;
        return partition;
    }

    public static void main(String[] args)
    {
        System.out.println(partition(100, 10));     
    }

}

التالية كود جافا بطباعة الفعلية أقسام.لأن عدد من أقسام هي عالية جدا (100,10) أنا يوضح الجواب (5,3):

public class Partitions2
{
    private static void showPartitions(int sizeSet, int numPartitions)
    {
        showPartitions("", 0, sizeSet, numPartitions);
    }

    private static void showPartitions(String prefix, int start, int finish,
            int numLeft)
    {
        if (numLeft == 0 && start == finish) {
            System.out.println(prefix);
        } else {
            prefix += "|";
            for (int i = start + 1; i <= finish; i++) {
                prefix += i + ",";
                showPartitions(prefix, i, finish, numLeft - 1);
            }
        }
    }

    public static void main(String[] args)
    {
        showPartitions(5, 3);
    }
}

الناتج هو:

|1,|2,|3,4,5,
|1,|2,3,|4,5,
|1,|2,3,4,|5,
|1,2,|3,|4,5,
|1,2,|3,4,|5,
|1,2,3,|4,|5,

Answer 2

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

عادة, هناك 100!طرق بدل ترتيب كذا 100 البنود, ولكن بما أنك الحفاظ على النظام ، يمكنك تقليل حجم المشكلة إلى أسفل إلى حد كبير.ما تصفه هو صحيح التقسيم المشكلة.على سبيل المثال, دعونا نقول كنت التقسيم رقم 5 إلى عدد صحيح فرعية والتي تضيف ما يصل إلى 5 ستحصل على مجموعات {5}, {4, 1}, {3, 2}, {3, 1, 1,}, {2, 2, 1}, {2, 1, 1, 1}, {1, 1, 1, 1, 1}.

عدد صحيح أقسام ينمو باطراد مع حجم عدد صحيح ، ولكن النمو المتسارع بطيئة بما فيه الكفاية التي يمكن تعداد من خلال جميع أقسام n = 100, لأن هناك فقط 190,569,292 منهم.إضافية القيد هنا هو أنك تريد تصفية جميع أقسام مجموعات تحتوي بالضبط 10 البنود التي من السهل أن تعداد من خلال استخدام فيرير الرسم البياني.

أنا يمكن أن تظهر فيرير مخطط التقسيم رقم 20 في 3 الدلاء:تبدأ مع 20 col × 3 الصف الشبكة على النحو التالي:

 12345678901234567890
1******************
2*
3*

إذن القسم الأول هو {18, 1, 1}

الآن نقل عنصر من الجزء العلوي من كومة إلى فتحة المقبل:

 12345678901234567890
1*****************
2**
3*

لدينا قسم جديد هو {17, 2, 1}.يمكننا عنصر آخر من كومة واحدة إلى أخرى:

 12345678901234567890
1****************
2***
3*

الآن لدينا {16, 3, 1}.يمكنك الاستمرار في هذه الأزياء حتى لقد تعداد جميع التباديل (حتى يمكنك إذا {17, 1, 2} متميزة قسم من {17, 2, 1}).

من هذه النقطة, يجب أن تكون قادرة على تصور الخطوط العريضة العامة الخوارزمية تحتاج -- وهذا هو ، إذا كنت ترغب في تحدي كتابة هذه الدالة من الصفر.غيرها من الناس بالفعل كتب الكثير من كفاءة وظائف لحل المشكلة بسهولة.