ما هو وسيلة جيدة لتنظيم حلقات متداخلة متغير؟

Question

لنفترض انك كنت تعمل في لغة مع صفائف طول متغير (على سبيل المثال مع A[i] لجميع i في 1..A.length) ولديك لكتابة روتين التي تأخذ n (n : 1..8) صفائف طول متغير من العناصر في مجموعة طول متغير طول n ، ويحتاج إلى استدعاء إجراء مع كل طول الممكنة n مجموعة من العناصر حيث تم اختيار الأول من مجموعة الأولى، يتم اختيار الثانية من مجموعة الثانية، وهكذا دواليك.

إذا كنت تريد شيئا ملموسا لتصور، تخيل أن روتينك أن يأخذ البيانات مثل:

[ [ 'top hat', 'bowler', 'derby' ], [ 'bow tie', 'cravat', 'ascot', 'bolo'] ... ['jackboots','galoshes','sneakers','slippers']]

ووإجراء المكالمات الإجراء التالي (في أي ترتيب):

try_on ['top hat', 'bow tie', ... 'jackboots']
try_on ['top hat', 'bow tie', ... 'galoshes']
 :
try_on ['derby','bolo',...'slippers']

وهذا ما يسمى في بعض الأحيان مشكلة القائمة الصينية، وn ثابتة يمكن أن تكون مشفرة بكل بساطة (على سبيل المثال لn = 3، في رمز زائف)

procedure register_combination( items : array [1..3] of vararray of An_item)
    for each i1 from items[1]
        for each i2 from items[2]
            for each i3 from items[3]
                register( [ii,i2,i3] )

ولكن ماذا لو n يمكن أن تختلف، وإعطاء توقيع مثل:

procedure register_combination( items : vararray of vararray of An_item)

والرمز كما هو مكتوب يتضمن بيان حالة القبيح، وأنا استبدال حل أبسط من ذلك بكثير. ولكن لست متأكدا من أنه أفضل (وهذا بالتأكيد لم يكن الوحيد) وسيلة لريفاكتور هذا.

وكيف ستفعل ذلك؟ ذكية ومثيرة للدهشة هي جيدة، ولكن واضحة وللصيانة هي الأفضل - وأنا مجرد مرور من خلال هذا الرمز ولا ترغب في الحصول على استدعائه. موجزة، واضحة <م> و ذكي سيكون امرا مثاليا.

وتحرير: أنا ما بعد حل بي في وقت لاحق اليوم، بعد أن كان آخرون فرصة للرد

ودعابة: حاولت أن تبيع حل العودية، لكنها لن يذهب لذلك، لذلك اضطررت إلى التمسك كتابة فورتران في HLL

.

والجواب ذهبت مع، نشر أدناه.

Answer 1

وبما أنهم كانوا يعارضون العودية (لا تسأل) وأنا يعارض فوضوي بيانات حالة (الذي، كما اتضح فيما بعد، كانوا يختبئون <لأ href = "https://stackoverflow.com/questions/666820/ ماذا يكون خاطئا-مع-هذا خوارزمية "> علة ) ذهبت مع هذا:

procedure register_combination( items : vararray of vararray of An_item)
    possible_combinations = 1
    for each item_list in items
        possible_combinations = possible_combinations * item_list.length
    for i from 0 to possible_combinations-1
        index = i
        this_combination = []
        for each item_list in items
            item_from_this_list = index mod item_list.length
            this_combination << item_list[item_from_this_list]
            index = index div item_list.length
        register_combination(this_combination)

وفي الأساس، يمكنني معرفة كم عدد المجموعات هناك، تعيين كل واحد عددا، ثم حلقة من خلال إنتاج مجموعة المقابل الرقم. ليس خدعة جديدة، وأظن، ولكن واحدا يستحق أن يعرف.

وانها أقصر، ويعمل لأي مزيج العملي لأطوال القائمة (إذا كان هناك أكثر من 2 ^ 60 مجموعات، لديهم مشاكل أخرى)، ليست متكررة، وليس لديها <لأ href = "HTTPS: // ستاكوفيرفلوو كوم / الأسئلة / 666820 / ماذا يكون-خطأ-مع-هذا خوارزمية "> علة .

Answer 2

وإما أن خوارزمية العودية

procedure register_combination( items )
        register_combination2( [], items [1:] )

procedure register_combination2( head, items)
    if items == []
        print head
    else
       for i in items[0]
           register_combination2( head ++ i, items [1:] )

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

Answer 3

والعودية.

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

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