تبديل i و T[i]

Question

على افتراض أن لدي مجموعة من int t ، أنا أبحث عن خوارزمية في مكانها تتوصل إلى i و t [i

أملك :[3 2 0 1] (أ)

أريد :[2 3 1 0] (ب)

على سبيل المثال.في (ب) T[0] = 2 لأنه في (أ) T[2] كان يساوي 0.

كنت أتوقع العثور على خوارزمية وقت O(n) بسيطة وخوارزمية مساحة O(1)، لكن لم أتمكن من العثور عليها.أيه أفكار ؟

ملحوظة :

• يوجد مصفوفة واحدة (أ) قبل (ب) بعد.

• تنتمي القيم الموجودة في المصفوفة إلى [0، N[، بدون تكرار.

Answer 1

للحصول على قلب التقليب، عليك فقط السير في دورات التقليب

int i, j, next, prev;
for(int i=0; i<N; i++) {
  if(T[i]>=N) continue;
  j=T[i];
  prev=i;
  while(j < N) {
    next=T[j];
    T[j]=prev+N;
    prev=j;
    j=next;
  }
}
for(int i=0; i<N; i++)
  T[i]-=N;

أستخدم أرقامًا أكبر من N لتمييز أن هذا جزء من دورة تمت معالجتها بالفعل.

Answer 2

يمكنك الذهاب لترتيب المعجم للحصول على جميع التباديل الممكنة.اتبع الرابط أدناه للحصول على قائمة خوارزميات التقليب

التباديل

Answer 3

يبدو أنك تبحث عن العكس في مجموعة التقليب من مصفوفة.صفيف المثال الخاص بك هو {0→3، 1→2، 2→0، 3→1}، وتريد {3→0، 2→1، 0→2، 1→3}.أعيد ترتيبها، وهي {0→2، 1→3، 2→1، 3→0}، أو [2 3 1 0].لذلك، للعثور على المعكوس، تحتاج فقط إلى التكرار عبر المصفوفة الأصلية وعكس تعيين المؤشرات.يجب أن ينجح هذا (يمكنك استخدام أي مصفوفة إذا كنت تعرف الطول):

int t[] = { 3, 2, 0, 1};
int tinv[4];
for (int i = 0; i < 4; i++)
    tinv[t[i]] = i;

طالما أن t (مع الطول n) هو تبديل لـ [0 ..n-1]، لا ينبغي أن يكون tinv غير محدد لأي قيم.يعد حل jpalecek أكثر تعقيدًا إلى حد ما، لذا لست متأكدًا مما إذا كان هذا الحل شاملاً بدرجة كافية بالنسبة لك.

Answer 4

هذه هي محاولتي لحل هذه المشكلة في مكانها دون ذاكرة إضافية.إنها خوارزمية O(n).

الخوارزمية التي طورها jpalecek ذكية للغاية ولكنها ليست بديهية للقراءة، على الأقل ليس بالنسبة لي.لقد جربته ويعمل ولكن لم يكن لدي الوقت الكافي لفهم السبب والتعليقات ستكون رائعة.

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

الفكرة الأساسية في الخوارزمية الخاصة بي هي تحديث المصفوفة باتباع سلسلة أزواج الفهرس والقيمة.على سبيل المثال، يعين الفهرس 0 القيمة 3.باستخدام القيمة 3 كمؤشر، ستجد الزوج التالي وهو الفهرس 3 في المصفوفة والقيمة 1.أقوم بشكل أساسي بحفظ الفهرس وزوج القيمة التاليين وتحديث الفهرس السابق وقيمة الزوج حتى أنتهي من السلسلة.

إذا كان بإمكانك جعله أكثر كفاءة أو أناقة أو أفضل بشكل عام، سأكون مهتمًا.

لقد قمت بتجميع واختبار الكود أدناه ولكن لم أستخدم أي إدخال اختبار آخر.لقد تركت إخراج التصحيح لأولئك الذين يرغبون في تجربته وفهم كيفية عمله بشكل أفضل.

// Array print routine.
void printArray (const char * str_p,int a[], int n)
{
   printf ("%s\n", str_p);
   for (int i = 0; i < n; i++)
   {
      printf ("%i ", i);
   }
   printf ("\n");
   for (int i = 0; i < n; i++)
   {
      printf ("%i ", a[i]);
   }
   printf ("\n\n");
}

// The main code.
void PermuteTheDamnArray()
{
   printArray ("Initial Array", a,n);

   int i = 0;     // Simply a counter.
   int p_ix = 0;  // Previous Index.
   int p_val = a[0]; // Previous Value.
   int n_ix = a[0];  // Next index.
   int n_val = a[n_ix]; // Next Value.
   for (i = 0; i < n; i++)
   {
      // Replace. 
      printf ("Swapping orig (%i,%i) with (%i,%i)\n", n_ix, n_val,p_val, p_ix);
      a[p_val] = p_ix;

      printArray ("Array after swap", a,n);

      // The next index and value pair becomes the new previous index and value pair.
      p_ix = n_ix;
      p_val = n_val;
      printf ("The previous pair is now: (%i,%i)\n", p_ix, p_val);

      // Get the next index and value pair.
      n_ix = n_val;
      n_val = a[n_val];
      printf ("The next pair is now: (%i,%i)\n", n_ix, n_val);

   }

   printArray ("Final Array", a,n);
}



Output:

Swapping orig (3,1) with (3,0)
Array after swap
0 1 2 3 
3 2 0 0 

The previous pair is now: (3,1)
The next pair is now: (1,2)
Swapping orig (1,2) with (1,3)
Array after swap
0 1 2 3 
3 3 0 0 

The previous pair is now: (1,2)
The next pair is now: (2,0)
Swapping orig (2,0) with (2,1)
Array after swap
0 1 2 3 
3 3 1 0 

The previous pair is now: (2,0)
The next pair is now: (0,3)
Swapping orig (0,3) with (0,2)
Array after swap
0 1 2 3 
2 3 1 0 

The previous pair is now: (0,3)
The next pair is now: (3,0)
Final Array
0 1 2 3 
2 3 1 0