كيفية حل مشكلة التقليب باستخدام سلسلة جافا سكريبت

تنويه: هذا ليس هو الحل لهذه المشكلة. هناك مليون طريقة لحلها.

مستعجل

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

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

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

أمثلة

إذا أخذنا السلسلة "cat" ، فيجب أن تعود الوظيفة

['الفعل' ، 'atc' ، 'القط' ، 'cta' ، 'tac' ، 'tca']

** بالنسبة لبقية هذا المنشور ، سنستخدم "القط" كعينتنا.

إذا كانت السلسلة تحتوي على حرف مكرر ، مثل "pop" ، فيجب أن تعود الوظيفة

['opp' و 'pop' و 'ppo']

مقاربة

إذا كيف يمكننا حل هذا؟ حسنًا ، يمكنك أن تفكر في كل حرف على أنه لديه مواضع محتملة في السلسلة ، حيث n هو طول السلسلة المحددة. عندما نبدأ التكرار من خلال السلسلة ، يمكننا إدراج كل حرف في صفيف في كل موقف متاح. على سبيل المثال ، إذا بدأنا بمصفوفة فارغة وأدرجت "c" في ذلك (الحرف الأول) ، فلا يوجد سوى مكان واحد محتمل يمكن أن يذهب إليه (الفهرس 0).

[ 'ج']

عندما تضيف الحرف الثاني ("أ") ، يمكن أن تذهب في مكانين: arr [0] أو arr [1]

"a" يمكن أن تذهب على جانبي "c"
['_c'] أو ['c_']
إدخال "a"
['ac'، 'ca']

وهلم جرا

يمكن أن تذهب 't' في 3 أماكن في كل عنصر في الصفيف
['_ac'، 'a_c'، 'ac_'، '_ca'، 'c_a'، 'ca_']
إدراج "ر"
['tac' ، 'atc' ، 'act' ، 'tca' ، 'cta' ، 'cat']

الحل دون تكرار

فيما يلي حل دون استخدام العودية:

سلسلة الوظائفالشروط (str) {
    دع الحروف = str.split ('')
      ، النتائج = [[letters.shift ()]]
    بينما (letters.length) {
        const currLetter = letters.shift ()
        دع tmpResults = []
        النتائج. لكل (نتيجة => {
            دع rIdx = 0
            بينما (rIdx <= result.length) {
                const tmp = [... النتيجة]
                tmp.splice (rIdx، 0، currLetter)
                tmpResults.push (تمة)
                rIdx ++
            }
        })
        النتائج = tmpResults
    }
    عودة النتائج
      .map (letterArray => letterArray.join (''))
      .filter ((el، idx، self) => (self.indexOf (el) === idx))
      .فرز()
}

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

دع الحروف = str.split ('') // letters = ['c'، 'a'، 't']

وسيحتفظ متغير النتائج بمصفوفة. في الجولة الأولى ، ستتضمن النتائج فقط الحرف الأول من السلسلة (في حالتنا "c" من "cat").

النتائج = [[letters.shift ()]] // النتائج = [['c']]
// والحروف = ['a'، 't']

الآن علينا أن نكرر من خلال بقية مجموعة الحروف. أولاً ، سوف نأخذ الرسالة التالية من مجموعة الحروف.

const currLetter = letters.shift () // currLetter = 'a'
// الحروف = ['t']

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

بينما (rIdx <= result.length) {
    // يخلق نسخة من مجموعة النتائج
    const tmp = [... النتيجة] // tmp = ['c']
    // إدراج الحرف الحالي في الموضع rIdx
    tmp.splice (rIdx، 0، currLetter) // tmp = ['a'، 'c']
    tmpResults.push (تمة)
    rIdx ++
}

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

// النتائج قبل الخريطة
[
  ['t' ، 'a' ، 'c'] ،
  ['أ' ، 'ر' ، 'ج'] ،
  [ 'فعل' ]،
  ['t' ، 'c' ، 'a'] ،
  ['c' ، 't' ، 'a'] ،
  [ 'قط' ]
]
// النتائج بعد الخريطة
['tac' ، 'atc' ، 'act' ، 'tca' ، 'cta' ، 'cat']

الآن بعد أن أصبح لدينا كل التباديل ، يجب علينا التأكد من أنها كلها فريدة من نوعها. هذا هو السبب في أننا نستخدم طريقة Array.prototype.filter. في هذه الحالة لم تكن هناك تكرارات ، لذلك تبقى النتائج كما هي.

أخيرًا ، يتعين علينا التأكد من فرز مجموعة النتائج.

// النتيجة النهائية
['الفعل' ، 'atc' ، 'القط' ، 'cta' ، 'tac' ، 'tca']

الزمان والمكان

التعقيد الزمني العام لهذا الحل هو O (n!) ، حيث n هو عدد الأحرف الفريدة في السلسلة.