هل هناك خوارزمية لتوليد جميع التباديل الدائري الفريد لمجموعة متعددة؟

Question

واجهت هذه المشكلة عند القيام ببعض البرمجة المتحمسة. يمكن التعبير عن المشكلة على النحو التالي:

بالنسبة إلى Multiset A ، دع P (A) يشير إلى مجموعة من جميع التباديل الممكنة لـ A. p (a) يتم تقسيمها بشكل طبيعي إلى مجموعات فرعية مفككة هي فئات التكافؤ ، مع وجود علاقة معادلة "يمكن أن تكون مرتبطة بتحولات دائرية". تعداد كل فئات التكافؤ هذه عن طريق توليد عضو واحد من كل منهم بالضبط.

على سبيل المثال ، ضع في اعتبارك multiset {0 ، 1 ، 1 ، 2}. تعد التباديل "0112" و "1201" من التباديل الفريدة ، ولكن يمكن العثور على الأخير عن طريق تغيير الدائرة الأولى والعكس بالعكس. يجب ألا تولد الخوارزمية المطلوبة على حد سواء.

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

أي نظرة ثاقبة في هذه المشكلة هو موضع تقدير عميق.

Answer 1

خوارزمية ساادا

Answer 2

من الأسهل قليلاً الذهاب لهذا القاع إلى الأعلى:

إذا كان A فقط يحتوي على عنصر واحد ، فإن P (A) يحتوي أيضًا على تقليب واحد. من السهل رؤية نفس الأعمال إذا كان A فقط يحتوي على عنصرين.

الآن ، لنفترض أن لديك بالفعل كل p (a) لعناصر n ، وتضيف عنصرًا واحدًا. يمكن أن تذهب في أي من المواقع n في أي من التباديل في p (a).

أعتقد أن هذه الفكرة تترجم مباشرة إلى خوارزمية عودية بلغتك المفضلة ، وآمل أن يكون توضيحي واضحًا بما فيه الكفاية.

تحرير: أعلم أنني تجاهلت حقيقة أن A قد تحتوي على عناصر مكررة ، ولكن ما زلت أفكر في هذا الجزء :)

مثلما - إذا قمت بفرز A قبل البدء في خوارزمية التقليب ، فأعتقد أن هذا قد يلغي التكرارات. (ما زلت أفكر في ذلك أيضًا)

Answer 3

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

ثم كل فئة معادلة هي مجرد مهمة لعنصر A إلى وضع على مدار الساعة.

بمجرد تعيين تقليب آخر من نفس فئة التكافؤ يمكن إنشاء ببساطة عن طريق تدوير الساعة على الحائط.

لتوليد تقليب آخر غير ذي صلة من A تحتاج إلى أن يكون هناك عنصر تخطي عنصرًا آخر على الأقل.

الآن الخوارزمية كما أرى أنها ستكون للبدء بمهمة على سبيل المثال ، تقول أن لدينا أربعة عناصر في أوضان A = {A ، B ، C ، D} وقمنا بتعيينها في المواقف 12 و 3 و 6 و 9 على التوالي للبصرية وضوح. عندها ستكون عمليةنا الأولى هي تبديل A و B. ثم A و C ، ثم A و D ، ثم نذهب إلى B وتبديله بالعنصر في الموضع الثلاثة الذي هو الآن ج.

القيام بذلك حتى وصلنا إلى D سيؤدي إلى توليد ممثل من جميع فئات التكافؤ.

هذا لا يهتم بالتكرارات ولكن يجب أن يكون أكثر كفاءة من توليد جميع التباديل لـ A.

Answer 4

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

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

تحرير لمزيد من الأفكار:

يحدث لي أن هذا المبدأ يمكن أن يمتد إلى الموقف الذي تكرر فيه إلى حد ما.

إذا أخذت عنصرًا واحدًا (الذي نفترضه الآن متكرر) ، فيمكنك إلقاء نظرة على التباديل فقط وأي منها سيسمح بتكرار التحول في الدورة ، كما كان من قبل ، يمكنك "قفل" واحد في مكانه دون فقدان عمومية. على سبيل المثال ، إذا كان لديك ما مجموعه 6 عناصر ويظهر مرتين في هذه المجموعة ، فيمكنك الحصول على:

AAXXXX ، AXAXXX ، AXXAXX ، AXXXAX ، AXXXXA

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

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

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

Answer 5

أقترح هنا حلًا تم تنفيذه في بيثون

import itertools as it

L = ['a','b','c','d']
B = it.combinations(L,2)
swaplist = [e for e in B]
print 'List of elements to permute:' 
print swaplist
print
unique_necklaces = []
unique_necklaces.append(L)
for pair in swaplist:
    necklace = list(L)
    e1 = pair[0]
    e2 = pair[1]
    indexe1 = L.index(e1)
    indexe2 = L.index(e2)
    #swap
    necklace[indexe1],necklace[indexe2] = necklace[indexe2], necklace[indexe1]
    unique_necklaces.append(necklace)

for n in unique_necklaces:
    # Commented code display the rotation of the elements in each necklace
    print 'Necklaces'
    print n#, [n[-r:]+n[:-r]for r in (1,2,3)]   

والفكرة هي بناء قلادات مختلفة عن طريق التباديل لعنامين. للحصول على قائمة بأربعة عناصر A ، B ، C ، D العائد على:

['a', 'b', 'c', 'd']
['b', 'a', 'c', 'd']
['c', 'b', 'a', 'd']
['d', 'b', 'c', 'a']
['a', 'c', 'b', 'd']
['a', 'd', 'c', 'b']
['a', 'b', 'd', 'c']