تقليل التقليب

Question

أحتاج خوارزمية يمكن أن خريطة يعمل في التقليب إلى رقم واحد ، ولكن أيضا تقليل اللاحقة الأرقام.

حتى على المدى متتابعة مجموعة من الأرقام في التقليب التي تم فرزها في النظام.في القائمة, 1;2;3;5;6;4 هناك نوعان من أشواط ، 1;2;3 و 5 و 6.أريد أن استبدال هذه مع رقم واحد, الحد الأدنى, حتى إذا كان بعد إزالة يعمل لدينا التقليب من 4 عناصر ، التقليب يستخدم الأرقام من 1 ...4.في ما سبق ، يجب أن تقلل من اثنان أشواط.الجولة الأولى سوف تكون 1 ، 4 يحول إلى 2 ، [5;6] تحول إلى 3 ، عقد معايير الثانية.إذا كنت نوع انخفاض التقليب ثم قم بتوسيع العناصر داخل من تعيين النوع الأصلي التقليب سوف تحصل على نفس النتيجة.الناتجة التقليب لا ينبغي أن يكون أي يعمل في ذلك.

على سبيل المثال (لقد أبرزت يعمل):

(1;2;3;4;5;6) => 1 //Mappings: 1->1;2;3;4;5;6
(2;3;4);1;(5;6) => 2 1 3 // Mappings: 2->2;3;4, and 3->5;6
(3;4);(1;2);(5;6) => 2 1 3 // Mappings: 2->3;4, and 1->1;2 and 3->5;6

الآن أنا تمر فوق القائمة ووضع قائمة من قوائم التجمع أشواط.حقا الجزء الثاني هو الجزء الصعب لجعل تنظيف الحل.لقد فكرت من السذاجة النهج الغريب إذا كان أي شخص لديه بعض حيلة ذكية يمكن أن تفعل ذلك أفضل لي, أنا في مثل O( 2n + n log n) ،

• استبدال يعمل مع عنصر رأس تشغيل وإدراج هذه البيانات في hashtable (على استرداد)
• الفرز لإنشاء خريطة المفقودين الأرقام مع انها فرز مؤشر.[1;6;5;4] سيكون الناتج [(1,1);(4,2);(5,3);(6,4)]
• استبدال قائمة في step1 مع الخريطة التي تم إنشاؤها في step2 وتحديث hashtable للترجمة.

تشغيل من خلال مثال ، مرة أخرى:

step 1: replace runs with the head element of the run and inserting data into a hash table  
    [1;3;4;2;5;6;] -> [1;3;2;5]  
step 2: sort array to create map  
    [1235], so we know that, in the previous array, 1 maps to 1, 2 to 2, 3 to 3, 4 to 5.  
step 3: do above translation on array from step one. 
    [1;3;2;4]

إذا كنت نوع هذا التقليب وإعادة بناء:[1;2;3;4], 3->3;4 4>5;6 أحصل على, 1;2;3;4;5;6.أيضا فرز.

أنا باستخدام قوائم لذا نهج وظيفي سيكون من المفضل.لا البرمجية اللازمة.كل الأفكار موضع ترحيب.

تحرير:

mweerden:

انها ليست واضحة بالنسبة لي ما شروط دقيقة على الخرائط هي.لماذا لا يسمح فقط تنتج التقليب [1,2,...,N] عن التقليب مع ن أشواط ؟ يبدو أنك تفضل خريطة تشغيل عدد من الهرب ولكن (وهذا ليس من الممكن دائما) يبدو أنك تسمح بعض الحرية.–

لا يفضلون خريطة تشغيل إلى رقم ضمن هذا المدى (أنظر أعلاه!), ولكن أنا بحاجة للحفاظ على يأمر.التقليب [1;2;3...N] هو شوط ، وبالتالي يمكن تخفيض إضافي.هذا هو السبب في أنه غير صالح.ما يهم في مزيد من العمليات في خوارزمية أخرى ، ولكن العناصر الفردية يمكن توسيعها في النهاية إلى إنقاذ الأصلي التقليب.

Answer 1

التدوين:

• العد يبدأ في 1
• l.i هو عنصر i من القائمة l
• l+m هو سلسلة من القوائم l و m
• تشغيل هو القصوى sublist هذا هو قائمة [n,n+1,n+2,...,m] بعض n و m مع n <= m

لذا يتم إعطاء التقليب p من القائمة [1,2,...,N].نقسم p إلى أشواط r_1,r_2,...,r_M مثل أن p = r_1+r_2+...+r_M.نحن ثم نبحث عن التقليب q من [1,2,...,M] مثل أن r_(q.1)+r_(q.2)+...+r_(q.M) = [1,2,...,N].

على سبيل المثال ، إذا p = [1,3,4,2,5,6], لدينا N=6, M=4, r_1 = [1], r_2 = [3,4], r_3 = [2] و r_4 = [5,6].في هذه الحالة نحن بحاجة q أن يكون [1,3,2,4] كما r_1+r_3+r_2+r_4 = [1]+[2]+[3,4]+[5,6] = [1,2,3,4,5,6].

علما بأن q لا يمكن أن تحتوي يعمل من طول أكبر من واحد في التعريف ؛ إذا كان, ثم هناك i < M مع q.i + 1 = q.(i+1) وبالتالي sublist r_(q.i)+r_(q.(i+1)) = r_(q.i)+r_(q.i + 1) من [1,2,...,N], ولكن r_(q.i)+r_(q.i + 1) هو أيضا من sublist p التي تتناقض مع هذا r_(q.i) و r_(q.i + 1) هل يعمل.

الآن تجد q نظرا p, نحن نفترض توفر البيانات ورسم الخرائط هيكل مع O(1) إدراج عمليات البحث من أرقام القوائم مع O(1) بإلحاق و إلى الأمام اجتياز.ثم نقوم التالية.

• علينا أولا إنشاء قائمة runheads = [r_1.1,r_2.1,...,r_M.1].هذا يمكن القيام به بسهولة شديدة عن طريق عبور p مع الحفاظ على المدى الحالي.خلال هذه الخطوة كما تذكر اقصى عدد واجه للحصول على N في النهاية وبناء الخرائط heads مع عناصر من runheads كما مفاتيح.هذه الخطوة هو واضح O(n).علما أنها ليست ذات الصلة ما قيم heads لذلك يمكننا استخدام تشغيل r_i كما قيمة المفتاح r_i.1.

• القادمة ونحن تكرار من 1 إلى (بما في ذلك) N الحفاظ على قيمة k مع القيمة الأولية 1.لكل قيمة i ونحن تحقق لمعرفة ما إذا كان i هو في heads.إذا كان هذا هو الحال نضيف i -> k إلى رسم الخرائط f وزيادة k.هذه الخطوة أيضا بوضوح O(n).أن تكون قادرة على الحصول على العودة من q إلى p نحن يمكن أيضا تخزين إضافية الخرائط rev مع k -> i أو حتى k -> runheads(i) في أي كبيرة اضافية-س التكلفة.

• واخيرا تطبيق الخرائط f إلى عناصر runheads للحصول على q.مرة أخرى O(n).

لتوضيح مع مثال ننظر إلى حال p = [1,3,4,2,5,6].

• في الخطوة الأولى نحصل على runheads = [1,3,2,5], N=6 و heads = { 1 -> [1], 3 -> [3,4], 2 -> [2], 5 -> [5,6] }.

• الثاني خطوات ونحن أربع حالات علينا أن نفعل شيئا: 1, 2, 3 و 5.هذه الحالات لدينا قيم k التي هي 1, 2, 3 و 4, ، على التوالي.وهذا يعني أن f سوف يكون { 1 -> 1, 2 -> 2, 3 -> 3, 5 -> 4 }.(و rev سيكون { 1 -> 1, 2 -> 2, 3 -> 3, 4 -> 5 } أو { 1 -> [1], 2 -> [2], 3 -> [3,4], 4 -> [5,6] }, اعتمادا على ما اخترت المخزن.)

• للحصول على q نحسب map(f,runheads) وهو [f(1),f(3),f(2),f(5)] أو مكافئ ، [1,3,2,4].

حتى لو لم يخطئ وإذا هياكل البيانات تلبية المتطلبات المذكورة أعلاه, هذا الحل يجب أن يكون O(n).علما أنه في الممارسة العملية في الواقع قد يكون أكثر فائدة لاستخدام الخاص بك (O(n*log(n))) الحل.إذا كان لديك كبيرة p ولكن مع فقط بضعة أشواط والفرز runheads واستخدام أن بناء تعيينات قد تكون أكثر كفاءة.أعتقد أن p سوف تكون كبيرة جدا عن هذه الحالة.

Answer 2

المحرر clarificaton

الخطوة 1:تشغيل الخوارزمية ولكن بدلا من إنتاج واحد فقط جدول تجزئة تنتج تجزئة الجدول (D1) فهرستها من قبل رئيس المجموعة هو الخرائط (على سبيل المثال ، [3,4] التي سوف تكون 3) وقائمة (L1) مع مجموعة نفسها

[3;4;6;8;1;2]:

   D1              L1

3 -> [3,4]     1 -> [3,4]

6 -> [6]       2 -> [6]

8 -> [8]       3 -> [8]

1 -> [1,2]     4 -> [1,2]

الخطوة 2:أنا كنت أنظر مجموعات لدينا الآن سترى أن مجموعة معينة لدينا مؤشر الذي وجدناه (في L1) و رئيس القيمة.الصحيح الخريطة قيمة الحد الأدنى صحيح بينهما التي لم تكن قد اتخذت.على سبيل المثال [3,4] يجب أن يجب أن تكون قيمة بين 1 و 3 ، 1 ، منذ ، المقابلة القيمة 2.تأخذ في الاعتبار ، كما D1 يتم فهرستها من قبل رئيس القيمة أقل القيم سوف يكون دائما مع إن المقابلة مجموعة موجودا.في المثال ، [1,2] تم تعيينها إلى 1 ، حتى أن هذا المفتاح هو بالفعل "تؤخذ".حتى في شبة الكود:

for (int Current = 1; Current  < L1.Length; Current++)
{
  GetHead(L1[Current]);
  Index = Current;
  While Head > Index
  {
    if D1.Empty(Index)
    {
      D1.Add(Index,D2[Current])
      D1.DeleteIfNotEmpty(Head);
    }
    else
      Index++;
  }
}

على سبيل المثال

• نأخذ القيمة الأولى في L1 -> [3,4]...
• على الرأس = 3
• ابتداء من 1 نحن بحث D1[1] التي اتخذت بالفعل, لذلك نحن الاضافة إلى 2.
• نحن نبحث عن D1[2] والتي هي فارغة لذلك نحن تعيين D1[2] = [3,4] وحذف D[3]

التي لا توفر O(n) ولكن شيئا من هذا القبيل O(n+log(n)) (n للخطوة الأولى, log(n) للمرة الثانية)

على سبيل المثال أعلاه أن يحصل لك:

1 -> [1,2]
2 -> [3,4]
3 -> [6]
4 -> [8]

الآن, إذا كان لديك [3;4;8;6;1;2], التي من شأنها أن تؤدي في

1 -> [1,2]
2 -> [3,4]
3 -> [8]
4 -> [6]

لأنه يستخدم المطلقة في ترتيب المجموعة الأصلية ، أنا لا أعرف إذا كان هذا هو كل الحق أو أنت تريد 6 في الفهرس 3 و 8 في مؤشر 4, في هذه الحالة سوف ربما كان بلاي L1 بناء على الرأس والتي سيتم زيادة الخاص بك التعقيد عن طريق Log(n)

إذا كان لديك بلاي سيكون لديك 0(n+سجل^2(n)) وهي ليست سيئة للغاية (ربما أقل افتراض فرز سريع وقد O(Log n) يأمر L1 سيتم O(log(log n))