كيف يمكنني الحصول على جميع التباديل لـ xPy؟

Question

أرغب في حساب جميع التباديل في الحجم Y لمجموعة الحجم X.هذا يعني أنه إذا كان لدي (1,2,3) وأريد جميع التباديل بالحجم 2، 3P2، فسيكون (1,2) (1,3) (2,1) (2,3) (3,1) (3،2).

يوفر كل من GSL وC++ STL فقط xPx الذي يمكنني رؤيته.هل يمكن لأي شخص أن يوجهني إلى مكتبة C/C++ التي يمكنها القيام بذلك أو توضيح خوارزمية سريعة وفعالة في الذاكرة؟

أحاول حل تشفير قصير جدًا.لقد اكتشفت رسالتين وقررت القيام بهجوم القوة الغاشمة.لدي "ouuglg ouyakl" وأقوم بفحص كل تبديل مقابل قاموس جيد جدًا.لقد قمت بحذف حرفين، لذا فإن احتمال 24P7 أو 1,744,364,160 ليس سيئًا للغاية.لدي برنامج Perl قيد التشغيل الآن، لذلك سيكون هذا اختبارًا مثيرًا للاهتمام للكفاءة الإجمالية لوقت البرمجة + وقت التشغيل.:)

(لا، ​​لا أريد فقط الإجابة على التشفير).

Answer 1

لقد استخدمت هذا Library من قبل (لاحظ أنها C++) في الكود الذي يحتاج إلى القيام بشيء مماثل.وله التباديل والتركيبات، مع التكرار وبدونه.بالنسبة لمشكلتك، يجب أن يكون هذا كافيًا (لم يتم اختباره...):

std::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);

std::vector<int>::iterator first = v.begin(), middle = v.begin() + 2, last = v.end();

do {
    // do stuff with elements in range first...middle (but dont change them)
} while(next_partial_permutation(first, middle, last));

Answer 2

يمكنك الحصول على المجموعات باستخدام std::next_permutation() على vector<bool> من الأعلام.أخذ مثالك لاختيار عنصرين من (1,2,3), ، ابدأ المتجه الخاص بك كـ (false, true, true).تكرار next_permutation() على هذا سوف أعطيك (true, false, true) ثم (true, true, false), ، قبل البدء من جديد.

نظرًا لأنك تريد التباديل وليس المجموعات، قم بتعيين كل مجموعة إلى مجموعة العناصر الفعلية (على سبيل المثال: (true, false, true) يصبح (1، 3)) ثم قم بإنشاء كافة التباديل باستخدام هذه next_permutation() مرة أخرى.

Answer 3

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

1. إنشاء قناع نقطي لكلمتك.ربما يمكنك استخدام العمليات الحسابية 64 بت حتى تتمكن من احتواء ما يقرب من 3 أبجديات بالداخل.

أ-> الجزء الأول، ب-> الجزء الثاني وهكذا.إذا كان لديك كلمة في حالتك "ouuglg ouyakl" فهذا يعني

 abcdefghijklmnopqrstuvxyzabcdefghijklmnopqrstuvxyzabcdefghijklmnop
 100000100011001000001001000000010000100100000100000000000000000000

(آمل أن أكون لم تفوت شيئًا) الآن تقوم بإنشاء نفس bitmass لمفرداتك.

وعندما تقوم بالتحقق من المفردات، ما عليك سوى القيام بذلك

 vocabulary & ( ouglg_ouyakl ^ vocabulary)

وهذا يعطي 0 إذا كانت كلمة المفردات الخاصة بك من ouglg_ouyakl.

حول التباديل

for each permutation of numbers fom  1-n // that is 1,2 and 2,1
  for(i=0;i<end;i++)
    for(j=i+1;j<end;j++)
      SET[permutation[i]],SET[permutation[j]]

يحرر:كان الحل السابق غير مناسب لـ 24P7.