إنشاء كل قيمة ممكنة لصفيف حجم ثابت

Question

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

حقا يجري القيام بذلك في التجميع، لكنني سأشرح ذلك في جيم

أساسا، قل لدينا مجموعة uint8_t *data=malloc(10);

أريد إنشاء خوارزمية ستطبع كل مزيج ممكن من البايتات في الصفيف data.

نعم، أعرف أنه سيكون بطيئا (وهناك العديد من القيم)، وأنا لا أسأل عن نسخة محسنة معقدة حقا .. أبحث عن شيء يمكنني تركه على جهاز الكمبيوتر الخاص بي كنوع من الغاشم - فورس نوع شيء للعثور على بعض القيم التي تطيع ظروف معينة ..

(لاحظ، أقول التقاطية لأن [0،1،2] يجب أن تحسب نفسها تقريبا [2،1،0])

تحرير: أيضا، حاول ألا تستخدم الكثير من الوظائف LIBC لأنني سأقوم بتحويل هذا إلى أداة تحميل شحن قائم بذاته مع 512 بايت فقط.

أعلم أنني أعرف كيف أن أفعل هذا ولكن بالنسبة لحياة لي أنا فقط لا أستطيع أن أجعل الخوارزمية تعمل في رأسي!

Answer 1

أنت سؤال يعاني من خلط غريبة المصطلحات. من ما تصفه يبدو أنك تريد إنشاء كل 10 مكاني من قيم 8 بت غير موقعة. هذه ليست "تصاميم" وكل هذا لا علاقة له بتكوين تصاميم.

الرمز الذي يولد كل ما هو ممكن 10 سن uint8_t القيم سهلة التوصل إلى. على سبيل المثال، سوف يقوم الرمز البسيط التالي بذلك

#define N 10u

uint8_t data[N] = { 0 };
unsigned i;

do {

  /* Process the current 10-typle in `data` array */
  /* in any way you want do */

  /* Generate next tuple */
  for (i = 0; i < N && ++data[i] == 0; ++i);

} while (i < N);

هذا ليس شيئا آخر من مجرد زيادة دورية لعدد قليل 80 بت.

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

Answer 2

حسنا، كل شيء هو تمرين غير مجدي (انظر تعليقي المرفقة بالسؤال)، ولكن هنا تذهب على أي حال (X86_64 AT & T TEVILES TEVILENT، يفترض اتفاقيات الاتصال نظام AMD V). أنا فقط أكتب هذا هنا دون اختبار، لذلك من الممكن تماما أن يكون له البق. ومع ذلك، يجب أن تكون العملية الأساسية للقانون واضحة تماما.

بدلا من التشغيل على المخزن المؤقت 80 بت في الذاكرة، أقوم ببساطة بتشغيل جميع إمكانيات حقل 80 بت تقسيم عبر سجلتين 64 بت. روتينك الذي يتحقق من شروطك يمكن تخزينها إلى الذاكرة والوصول إلى تلك الذاكرة uint8_t إذا كنت تريد حقا أن.

    push r12
    push r13
    xor  r12, r12 // zero out low 64 bits of our "buffer" in register
    xor  r13, r13 // zero out high 16 bits of our "buffer"

loop:
    // Copy the current array value into rsi:rdi and call whatever routine you're
    // using to check for magic conditions.  This routine's copy (in r13:r12)
    // should be unaffected if you're obeying the System V calling conventions.
    mov  r12, rdi
    mov  r13, rsi
    call _doSomethingWithValue

    // Increment r13:r12 to get the next value.  We only need to worry about r13
    // if the increment of r12 wraps around to zero.
    inc  r12
    jnz  loop
    inc  r13

    // Check for the termination condition, though you'll never hit it =)
    cmp  $0x10000, r13
    jne  loop

    // We don't actually need to clean up; the apocalypse will come and there
    // won't be electricity to run the computer before it reaches this point of
    // the program.  Nonetheless, let's be exhaustively correct.
    pop  r13 
    pop  r12

Answer 3

أود أن أقترح عليك أن تقرأ،

دونالد نوث. فن برمجة الكمبيوتر، المجلد 4، Fascicle 2: توليد جميع tuples and التباديل.

Answer 4

هناك نهج تكرس الكلاسيكية للمشكلة مماثلة لما يلي:

#include <stdio.h>


void print(const uint8_t *v, const int size)
{
  if (v != 0) {
    for (int i = 0; i < size; i++) {
      printf("%4d", v[i] );
    }
    printf("\n");
  }
} // print


void visit(uint8_t *Value, int N, int k)
{
  static level = -1;
  level = level+1; Value[k] = level;

  if (level == N)
    print(Value, N);
  else
    for (int i = 0; i < N; i++)
      if (Value[i] == 0)
        visit(Value, N, i);

  level = level-1; Value[k] = 0;
}


main()
{
  const int N = 4;
  uint8_t Value[N];
  for (int i = 0; i < N; i++) {
    Value[i] = 0;
  }
  visit(Value, N, 0);
}

مثال مأخوذ من حلقة الوصل التي توجد مناهج أخرى. النظرية وراءها بسيطة للغاية .. إذا كنت بحاجة إلى أنه يمكنني زيادة شرح الخوارزمية ولكنها شفافة ذاتيا تماما.

Answer 5

القي نظرة على هذه الخوارزمية لتوليد مجموعات من N خارج عن العناصر. بالنسبة لمجموعات N، اختر N، استخدم فقط InittWiddle (N، N، P)؛

int twiddle(x, y, z, p)
int *x, *y, *z, *p;
  {
  register int i, j, k;
  j = 1;
  while(p[j] <= 0)
    j++;
  if(p[j-1] == 0)
    {
    for(i = j-1; i != 1; i--)
      p[i] = -1;
    p[j] = 0;
    *x = *z = 0;
    p[1] = 1;
    *y = j-1;
    }
  else
    {
    if(j > 1)
      p[j-1] = 0;
    do
      j++;
    while(p[j] > 0);
    k = j-1;
    i = j;
    while(p[i] == 0)
      p[i++] = -1;
    if(p[i] == -1)
      {
      p[i] = p[k];
      *z = p[k]-1;
      *x = i-1;
      *y = k-1;
      p[k] = -1;
      }
    else
      {
      if(i == p[0])
    return(1);
      else
    {
    p[j] = p[i];
    *z = p[i]-1;
    p[i] = 0;
    *x = j-1;
    *y = i-1;
    }
      }
    }
  return(0);
  }

void inittwiddle(m, n, p)
int m, n, *p;
  {
  int i;
  p[0] = n+1;
  for(i = 1; i != n-m+1; i++)
    p[i] = 0;
  while(i != n+1)
    {
    p[i] = i+m-n;
    i++;
    }
  p[n+1] = -2;
  if(m == 0)
    p[1] = 1;
  }

/************************
  Here is a sample use of twiddle() and inittwiddle():
#define N 5
#define M 2
#include <stdio.h>
void main()
  {
  int i, x, y, z, p[N+2], b[N];
  inittwiddle(M, N, p);
  for(i = 0; i != N-M; i++)
    {
    b[i] = 0;
    putchar('0');
    }
  while(i != N)
    {
    b[i++] = 1;
    putchar('1');
    }
  putchar('\n');
  while(!twiddle(&x, &y, &z, p))
    {
    b[x] = 1;
    b[y] = 0;
    for(i = 0; i != N; i++)
      putchar(b[i]? '1': '0');
    putchar('\n');
    }
  }
************************/

الجواب على هذا المنصب قد يساعدك أيضا خوارزمية لإرجاع جميع مجموعات عناصر K من N

Answer 6

إذا كنت تعمل في C ++،

#include <algorithm>
#include <iterator>
#include <iostream>
#include <numeric>

int main() {
    int N;
    std::cin >> N;
    std::vector<int> data(N);
    std::fill(data.begin(), data.end(), 1);
    std::partial_sum(data.begin(), data.end(), data.begin());

    do {
        std::copy(data.begin(), data.end(),
                std::ostream_iterator<int>(std::cout, " "));
        std::cout << std::endl;
    } while (std::next_permutation(data.begin(), data.end()));

    return 0;
}

إذا كنت مدخل 3, ، مخرجاتها

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

يرى التقليب التالي: عند C ++ يحصل عليه بشكل صحيح حول كيف std::next_permutation يعمل.

---

ترجمة هذا إلى عادي ج،

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

int main() {
    int i, N, *data;

    scanf("%d", &N);
    data = malloc(N);
    for (i = 0; i < N; i++) data[i] = i + 1;

    while (1) {
        int j, temp;

        for (i = 0; i < N; i++) printf("%d ", data[i]);
        printf("\n");

        for (i = N - 1; i > 0 && data[i] < data[i - 1]; i--);
        if (i <= 0) break;
        for (j = N; data[i - 1] >= data[--j];);
        temp = data[i - 1], data[i - 1] = data[j], data[j] = temp;
        for (j = N - 1; i < j; i++, j--)
            temp = data[i], data[i] = data[j], data[j] = temp;
    }

    return 0;
}

---

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

memset(data, 0, N);
do {
    for (i = 0; i < N; i++) printf("%d ", data[i]);
    printf("\n");
    for (i = 0; i < N && !++data[i++];);
} while (i < N);