توليد التباديل k من n في C

2

أحتاج بشكل أساسي إلى النتيجة المكافئة لـ Python التالية itertools الأمر في C:

a = itertools.permutations(range(4),2))

تتضمن عمليتي حاليًا أولاً "اختيار" 5 عناصر من 10 ثم إنشاء تبدلات لتلك العناصر الخمسة كما هو موضح هنا

المشكلة في هذا النهج هي ترتيب المخرجات. أحتاج أن يكون (أ) ، في حين أن ما أحصل عليه هو (ب) ، كما هو موضح أدناه.

a = itertools.permutations(range(4),2)
for i in a:
    print(i)

(0, 1)
(0, 2)
(0, 3)
(1, 0)
(1, 2)
(1, 3)
(2, 0)
(2, 1)
(2, 3)
(3, 0)
(3, 1)
(3, 2)

b = itertools.combinations(range(4),2) 
for i in b:
    c = itertools.permutations(i)
    for j in c:
        print(j)
(0, 1)
(1, 0)
(0, 2)
(2, 0)
(0, 3)
(3, 0)
(1, 2)
(2, 1)
(1, 3)
(3, 1)
(2, 3)
(3, 2)

النهج البديل الذي أستخدمه هو كما يلي

void perm(int n, int k)
{
    bool valid = true;
    int h = 0, i = 0, j = 0, limit = 1;
    int id = 0;
    int perm[10] = { 0,0,0,0,0,0,0,0,0,0 };
    for (i = 0; i < k; i++)
        limit *= n;
    for (i = 0; i < limit; i++)
    {
        id = i;
        valid = true;
        for (j = 0; j < k; j++)
        {
            perms[j] = id % n;
            id /= n;
            for (h = j - 1; h >= 0; h--)
                if (perms[j] == perms[h])
                {
                    valid = false; break;
                }
            if (!valid) break;
        }
        if (valid)
        {
            for (h = k - 1; h > 0; h--)
                printf("%d,", perms[h]);
            printf("%d\n", perms[h]);
            count++;
        }
    }
}

الذاكرة هي القيد الخاص بي ، لذلك لا يمكنني تخزين التباديل إلى أجل غير مسمى. يجب أن يكون الأداء أفضل من الخوارزمية أعلاه ، كما هو الحال عند n هو 50 و k هو 10 ، ينتهي بي الأمر بالتكرار من خلال المزيد من المجموعات غير الصالحة (60 +٪)

أنا على دراية بخوارزمية أكوام لإنشاء التبدلات في مكانها ولكن مرة أخرى يتم إنشاؤها لمجموعة كاملة وليس ك n مثل أحتاج.

الأسئلة.

  1. هل هناك طريقة أفضل للقيام بذلك من تكرار n ^ k مرات؟
  2. هل يمكنني عمل مكرر بطيء ينتقل إلى التباديل التالي بالنظر إلى التباديل الحالي؟

تعديل هذه ليست نسخة مكررة من تنفيذ std :: next_permutation لأن ذلك سيسمح بنطاق المدخلات بالكامل. لقد ذكرت بوضوح أنني بحاجة إلى k من n التباديل. على سبيل المثال إذا كان نطاقي 10 ، فأنا أريد جميع التباديل ذات الطول (k) أن نقول 5 ، std :: next_permutation يعمل عندما يكون الطول أو التحويل نفس طول نطاق الإدخال

UPDATE هنا هو حل NextPerm التكراري القبيح والذي هو أسرع بحوالي 4 مرات من الحل القديم الخاص بي ويعطي NextPerm المتزايد مثل المكرر البطيء Python.

int nextPerm(int perm[], int k, int n)
{
    bool invalid = true;
    int subject,i;
    if (k == 1)
    {
        if (perm[0] == n - 1)
            return 0;
        else { perm[0]=perm[0]+1; return 1; }
    }
    subject = perm[k - 1]+1;

    while (invalid)
    {
        if (subject == n)
        {
            subject = 0;
            if (!nextPerm(perm, k - 1, n))
                return 0;
        }
        for (i = 0; i < k-1; i++)
        {
            if (perm[i] != subject)
                invalid = false;
            else
            {
                invalid = true;subject++; break; 
            }
        }
    }
    perm[k - 1] = subject;
    return 1;
}
int main()
{
    int a, k =3 ,n = 10;
    int perm2[3] = { 0,1,2}; //starting permutation
    unsigned long long count = 0;
    int depth = 0;
    do
    {
        for (a = 0; a < k - 1; a++)
            printf("%d,", perm2[a]);
        printf("%d\n", perm2[k - 1]);
        count++;
    }
    while (nextPerm(perm2,k,n));
    printf("\n%llu", count);
    getchar();
    return 0;
}

1 إجابة

2
افضل جواب

هناك تعديل بسيط لخوارزميات التبادل القياسية التي ستنتج التباديل ك.

التباديل بأمر معجمي (الملقب std::next_permutation )

في C ++ ، يمكن إنشاء التباديل k بواسطة الوسيلة البسيطة باستخدام std::next_permutation ، وعكس اتجاه n-k -إفقية التباديل قبل كل مكالمة std::next_permutation .

من الواضح بشكل معقول كيف يعمل: الخوارزمية تولد التباديل بالترتيب ، لذا فإن التباديل الأول الذي يبدأ ببادئة معينة له اللاحقة المتبقية بترتيب متزايد ، والتبديل الأخير مع نفس البادئة له لاحقة في ترتيب تنازلي. إن تناقص الترتيب هو ببساطة عكس الترتيب المتزايد ، لذا فإن استدعاء واحد لـ std::reverse كافي.

خوارزمية الترحيل التالي للترتيب المعجمي بسيطة للغاية:

  1. ابحث للخلف من النهاية عن عنصر يمكن زيادته من خلال تبديله بعنصر لاحق.

  2. بمجرد العثور على العنصر الموجود في أقصى اليمين ، ابحث عن أصغر عنصر يلي يمكن استبداله به ، وقم بتبديله.

  3. قم بفرز اللاحقة الجديدة إلى ترتيب متزايد (من خلال عكسها ، حيث كانت في السابق في ترتيب تنازلي).

ميزة الخوارزمية المعجمية هي أنها تتعامل بشفافية مع المصفوفات مع العناصر المتكررة. طالما أن عدد التكرارات لأي عنصر معين هو O (1) ، next-permutation يتم إطفاء O (1) (لكل مكالمة) ، وفي أسوأ الحالات يكون O (n). عند إنشاء التباديل k ، فإن الوجه الإضافي يسبب تكلفة next_k_permutation أن يكون O (nk) ، وهو فعال O (n) إذا k تم إصلاحه. لا يزال هذا سريعًا إلى حد ما ، ولكن ليس بالسرعة مثل الخوارزميات غير التكرارية التي يمكن أن تحافظ على الحالة بدلاً من إجراء البحث في الخطوة 1 لمعرفة العنصر الذي يجب نقله.

تنفيذ C التالي يعادل std::reverse(); std::next_permutation(); (باستثناء أنه يتبادل قبل أن ينعكس):

#include <stddef.h>

/* Helper functions */
static void swap(int* elements, size_t a, size_t b) {
  int tmp = elements[a]; elements[a] = elements[b]; elements[b] = tmp;
}
static void flip(int* elements, size_t lo, size_t hi) {
  for (; lo + 1 < hi; ++lo, --hi) swap(elements, lo, hi - 1);
}

/* Given an array of n elements, finds the next permutation in
 * lexicographical order with a different k-prefix; in effect, it 
 * generates all k-permutations of the array.
 * It is required that the suffix be sorted in ascending order. This
 * invariant will be maintained by the function.
 * Before the first call, the array must be sorted in ascending order.
 * Returns true unless the input is the last k-permutation.
 */ 
int next_k_permutation(int* elements, size_t n, size_t k) {
  // Find the rightmost element which is strictly less than some element to its
  // right.
  int tailmax = elements[n - 1];
  size_t tail = k;
  while (tail && elements[tail - 1] >= tailmax)
    tailmax = elements[--tail];
  // If no pivot was found, the given permutation is the last one.
  if (tail) {
    size_t swap_in;
    int pivot = elements[tail - 1];
    // Find the smallest element strictly greater than the pivot, either
    // by searching forward from the pivot or backwards from the end.
    if (pivot >= elements[n - 1]) {
      for (swap_in = tail; swap_in + 1 < k && elements[swap_in + 1] > pivot; ++swap_in) {}
    } else {
      for (swap_in = n - 1; swap_in > k && elements[swap_in - 1] > pivot; --swap_in) {}
    }
    // Swap the pivots
    elements[tail - 1] = elements[swap_in];
    elements[swap_in] = pivot;
    // Flip the tail. 
    flip(elements, k, n);
    flip(elements, tail, n);
  }
  return tail;
}

إليك برنامج تشغيل بسيط وعينة تشغيل:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int intcmp(const void* a, const void* b) {
  return *(int*)a < *(int*)b ? -1 : 
         *(int*)a > *(int*)b ?  1 :
                                0 ;
}

int main(int argc, char** argv) {
  size_t k = (argc > 1) ? atoi(argv[1]) : 0;
  if (argc < k + 2) {
    fprintf(stderr, "Usage: %s K element...\n"
                    "       where K <= number of elements\n",
                    argv[0]);
    return 1;
  }
  size_t n = argc - 2;
  int elements[n];
  for (int i = 0; i < n; ++i) elements[i] = atoi(argv[i + 2]);
  qsort(elements, n, sizeof *elements, intcmp);
  do {
    const char* delimiter = "";
    for (size_t i = 0; i < k; ++i) {
      printf("%s%2d ", delimiter, elements[i]);
      delimiter = " ";
    }
    putchar('\n');
  } while (next_k_permutation(elements, n, k));
  return 0;
}

تشغيل عينة (مع عنصر متكرر):

$ ./k_next_permutation 2 7 3 4 4 5
 3   4 
 3   5 
 3   7 
 4   3 
 4   4 
 4   5 
 4   7 
 5   3 
 5   4 
 5   7 
 7   3 
 7   4 
 7   5 

خوارزمية كومة معدلة

كمثال على خوارزمية تحافظ على الحالة ، يمكن تعديل خوارزمية Heap بسهولة لإنتاج التباديل k. التغيير الوحيد هو أنه عندما تتكرر الخوارزمية إلى الموضع n - k يتم الإبلاغ عن اللاحقة k على أنها التبدل k ويتم تحويل (nk) -prefix بالطريقة التي ستحولها خوارزمية Heap إذا تم تشغيلها حتى النهاية: تنعكس البادئة إذا كان طولها وتدوير واحدًا إلى اليسار إذا طوله متساوي. (هذا تلميح كبير حول كيفية عمل خوارزمية Heap ، بالمناسبة).

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

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>

/* Helper functions */
static void swap(int* elements, size_t a, size_t b) {
  int tmp = elements[a]; elements[a] = elements[b]; elements[b] = tmp;
}
static void flip(int* elements, size_t lo, size_t hi) {
  for (; lo + 1 < hi; ++lo, --hi) swap(elements, lo, hi - 1);
}
static void rotate_left(int* elements, size_t lo, size_t hi) {
  if (hi > lo) {
    int tmp = elements[lo];
    for (size_t i = lo + 1; i < hi; ++i) elements[i - 1] = elements[i];
    elements[hi - 1] = tmp;
  }
}

/* Recursive function; the main function will fill in the extra parameters */
/* Requires hi >= lo and hi >= k. Array must have size (at least) lo + k */    
static bool helper(int* array, size_t lo, size_t k, size_t hi,
                       bool(*process)(void*, int*, size_t), void* baton) {
  if (hi == lo) {
    if (!process(baton, array + lo, k)) return false;
    if (lo % 2)
      flip(array, 0, lo);
    else
      rotate_left(array, 0, lo);
  }
  else {
    for (size_t i = 0; i < hi - 1; ++i) {
      if (!helper(array, lo, k, hi - 1, process, baton))
        return false;
      swap(array, hi % 2 ? 0 : i, hi - 1);
    }
    if (!helper(array, lo, k, hi - 1, process, baton))
      return false;
  }
  return true;
}

/* Generate all k-permutations of the given array of size n.
 * The process function is called with each permutation; if it returns false,
 * generation of permutations is terminated.
 */ 
bool k_heap_permute(int* array, size_t n, size_t k,
                    bool(*process)(void*, int*, size_t), void* baton) {
  assert(k <= n);
  return helper(array, n - k, k, n, process, baton);
}

إليك مثال على استخدامه:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

bool print_array(void* vf, int* elements, size_t n) {
  FILE* f = vf;
  const char* delim = "";
  for (size_t i = 0; i < n; ++i) {
    fprintf(f, "%s%2d", delim, elements[i]);
    delim = " ";
  }
  putc('\n', f);
  return true;
}

int main(int argc, char** argv) {
  size_t k = (argc > 1) ? atoi(argv[1]) : 0;
  if (argc < k + 2) {
    fprintf(stderr, "Usage: %s K element...\n"
                    "       where K <= number of elements\n",
                    argv[0]);
    return 1;
  }
  size_t n = argc - 2;
  int elements[n];
  for (int i = 0; i < n; ++i)
    elements[i] = atoi(argv[i + 2]);
  k_heap_permute(elements, n, k, print_array, stdout);
  return 0;
}

تشغيل العينة:

$ ./permut 2      1 5 9 7 3
 7  3
 9  3
 5  3
 1  3
 1  5
 7  5
 9  5
 3  5
 3  9
 1  9
 7  9
 5  9
 5  7
 3  7
 1  7
 9  7
 9  1
 5  1
 3  1
 7  1
:مؤلف

أسئلة ذات صلة

فوق
قائمة طعام