1

配列の可能なすべての順列を循環する非常に基本的なものを作成しようとしています。

本当はアセンブルでやっているのですが、Cで説明します。

基本的に、配列があるとしますuint8_t *data=malloc(10);

array 内のバイトの可能なすべての組み合わせを出力するアルゴリズムを作成したいと考えていますdata。

はい、私はそれが遅くなることを知っています（そして多くの値があります）、そして私は本当に複雑な最適化されたバージョンを求めているわけではありません. -特定の条件に従う特定の値を見つけるために型を強制する..

(注、[0,1,2] は [2,1,0] と同じようにカウントされるべきではないため、順列と言います)

編集: また、これを 512 バイトのみの独立したブートローダーに変換するため、あまり多くの libc 関数を使用しないようにしてください。

私はこれを行う方法を知っていますが、私の人生では、頭の中でアルゴリズムを機能させることはできません!

4

6 に答える 6

2

私はあなたが読むことをお勧めします、

ドナルド・クヌース。The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Tuples and Permutations.

于 2010-01-05T00:20:16.767 に答える
0

この問題には、次のような古典的な再帰的アプローチがあります。

#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);
}

例は、他のアプローチがあるリンクから取られています。その背後にある理論は非常に単純です.必要に応じて、アルゴリズムをさらに説明できますが、それは非常に自明です.

于 2010-01-05T00:09:49.393 に答える
0

M 個のアイテムから 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');
    }
  }
************************/

この投稿への回答は、アルゴリズムが n から k 要素のすべての組み合わせを返すのにも役立つ場合があります

于 2010-01-05T01:13:12.947 に答える