كيف يجب أن أذهب حول توليد كل خريطة ممكنة مزيج من الخريطة >؟

Question

أنا أتطلع إلى أخذ map<char, vector<char> > وتوليد كل ممكن map<char, char> منه.

أنا أفهم أن هذا قد يستخدم كمية كبيرة من الذاكرة واتخاذ القليل من الوقت.

كل map<char, char> يحتاج إلى احتواء كل حرف AZ، ويتم تعيينه إلى شخصية فريدة من الأيل عشر. بمعنى آخر. AK BJ CP DY EV FH GA HB IR JQ KN Li MX NC OO PZ QS RL SD TE UW VF WG XM YU ZT

هنا هو ما خلصت لنفسي حتى الآن:

لخفض عدد السخرية من المجموعات المحتملة إلى كمية أقل، إذا أ vector<char> يحتوي على أكثر من 5 عناصر، سأحل محلها ببساطة vector<char> تحتوي على سحر واحد من "سيد" / "الأصلي" map<char, char>.

ليس كل الشخصيات ستكون موجودة على كل من vector<char>s في الخريطة. يجب إيجاد هذه الشخصيات ووضعها في بعض ناقلات "الآخرين".

يجب أن يحتوي هذا أيضا على أحرف حيث حرف واحد هو الحرف الوحيد الممكن لأكثر من مفتاح حرف واحد (أي MW في المثال، أنا أعمل من - أنا غير متأكد من كيفية الذهاب حول هذا الأمر).

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

إليك مثال على ما لدي حتى الآن.

سأكون أخذ map<char, vector<char> >, ، مثل:

a: gjkpqvxz.
ب: gjkpqvxz.
ج: gjkpqvxyz.
D: MW.
E: GJKPQVXZ.
F: NR.
G: في
ح: راجع
أنا: له
J: GJKPQVXZ.
K: R.
L: H.
م: gjkpqvxz.
n: gjkpquvxyz.
o: هو
P: GJKPQVXZ.
س: هو
R: DL.
S: L.
T: E.
ش: dgkpuvy.
الخامس: راجع
W: BCF.
X: DGUY.
Y: F.
z: at.

هذه هي خريطة البداية. بعد قطع ناقلات الشخصيات الكبيرة من أكثر من 5 واستبدالها بأفضل تخمين. حيث هو vector<char> من الحجم 1، أن رسم الخرائط ذات الطابع يحتوي فقط على مجموعة واحدة، ولا يمكن استخدام هذه الشخصية في أي رسم خرائط أخرى لأنها ستجعلها فريدة من نوعها. لقد قلصت ذلك إلى:

ج: ك
ب: J.
ج: P.
D: MW.
E: V.
و: N.
G: في
ح: C.
أنا: هو
J: س
K: R.
L: H.
م: X.
n: guy.
o: هو
P: Z.
س: هو
بحث وتطوير
S: L.
T: E.
ش: dguy.
الخامس: جيم
W: BC.
X: DGUY.
Y: F.
z: at.

يحتوي ناقل "الآخرين" على "O '(أعتقد أنه من المهم ملاحظة أنني أعتقد أن هذا يجب أن يحتوي على حالات مثل ميغاواط من المثال أعلاه. كما D هو المكان الوحيد MW يمكن استخدامه، ولكن من الواضح بالحاجة إلى كل رسالة لا يمكن استخدامها مرة واحدة فقط، واحد منهم فقط يمكن استخدامها، وترك الآخر أن تضيع في مكان ما. لست متأكدا من كيفية الذهاب حول برمجة حالة عامة لإضافة هذه إلى ناقلات الآخرين.)

أنا أبحث عن المساعدة والمؤشرات مع توليد كل ممكن map<char, char> من map<char, vector<char> >s مثل هذا وفي هذا التنسيق. سيتم استخدامها كحجة في مكالمة وظيفة. لست متأكدا حقا من أين أبدأ في كتابة شيء سيعمل بمعنى عام. من المحتمل أن أسترحب بها بمبلغ كبير من الحلقات التي تبحث من خلال كل عنصر مقابل كل عنصر آخر ضد كل عنصر آخر ... إلخ، الذي أفترض أنه سيكون غير فعال للغاية وهناك طرق أكثر أناقة لحل هذه المشكلة وبعد

آسف إذا كان هذا جدار نصي جدا أو يبدو مائلا أو سيئا مكتوبا / سيئا.

أنا أقدر أي وجميع المساعدة.

Answer 1

أعتقد أنني آمل أن لا أحتاج إليهم جميعا موجودين في وقت واحد. ثم يمكنني:

1) قم بإنشاء أول خريطة من خلال تعيين أول عنصر محتمل لكل حرف:

for (char c = 'a'; c <= 'z'; ++c) {  // yes, I assume ASCII
   new_map[c] = old_map[c][0];
}
int indexes[26] = {0};

2) قم بإنشاء الخرائط المتبقية بدوره عن طريق تعديل الخريطة الموجودة، مرارا وتكرارا:

++indexes[0];
if (indexes[0] < old_map['a'].size()) {
    new_map['a'] = old_map['a'][indexes[0]];
} else {
    indexes[0] = 0;
    new_map['a'] = old_map['a'][0];
    // "carry the 1" by applying the same increment process to indexes[1]
}
do_something_with(new_map);

do_something_with يمكن إعادة إنشاء ناقلات "الآخرين" في كل مرة من الخريطة، وإلا يمكنك تحديثه في كل مرة تقوم فيها بتغيير حرف. يستبدل:

    new_map['a'] = something;

مع:

    char removed = new_map['a'];
    --counts[removed];
    if (counts[removed] == 0) others.add(removed);
    ++counts[something];
    if (counts[something] == 1) others.remove(something);
    new_map['a'] = something;

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

راجع للشغل، هل فكرت في أن الخريطة مبالغة قليلا مقابل 26 مفاتيح محتملة فقط، كل منها مطلوب أن يكون حاضرا في كل خريطة؟ ناقلات أو صفيف سيكون أرخص بكثير للاستخدام ونسخ.

Answer 2

أنا أفهم أن هذا قد يستخدم كمية كبيرة من الذاكرة واتخاذ القليل من الوقت.

نعم، يبلغ عدد المجموعات حوالي 403،291،461،000،000،000،000،000،000.000،000 :-)