1

我正在尝试制作一些非常基本的东西，它将循环遍历数组的所有可能排列。

确实这是在汇编中完成的，但我将在 C 中解释它。

基本上，假设我们有一个数组uint8_t *data=malloc(10);

我想创建一个算法来打印数组中所有可能的字节组合data。

是的，我知道它会很慢（并且有很多值），而且我并不是要真正复杂的优化版本。我只是在寻找可以在我的计算机上运行的东西，作为一种蛮力-force 类型的东西来找到符合某些条件的某些值..

（注意，我说排列是​​因为 [0,1,2] 不应该被视为与 [2,1,0] 相同）

编辑：另外，尽量不要使用太多的 libc 函数，因为我会将它转换为只有 512 字节的独立引导加载程序。

我知道我知道如何做到这一点，但是对于我的一生，我就是无法让算法在我的脑海中运行！

4

6 回答 6

4

好吧，整个事情都是徒劳的（请参阅我对问题的评论），但无论如何你都可以去（x86_64 AT&T 风格的程序集，假设 AMD 系统 V 调用约定）。我只是在这里写这个没有测试，所以它完全有可能有错误。尽管如此，代码的基本操作应该是完全清楚的。

我没有在内存中的 80 位缓冲区上操作，而是简单地运行了跨两个 64 位寄存器拆分的 80 位字段的所有可能性。检查您的状况的例程可以将它们存储到内存中，并像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
于 2010-01-05T01:48:10.740 回答
3

你的问题遭受了一个奇怪的术语混淆。根据您的描述，您似乎想要生成所有可能的 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 位 little-endian 数字的循环增量。

当然，正如其他人已经指出的那样，从任何实际角度来看，这将花费大量时间使整个事情变得毫无用处。

于 2010-01-05T01:46:02.227 回答
2

我建议你阅读，

唐纳德·克努特。计算机编程艺术，第 4 卷，分册 2：生成所有元组和排列。

于 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 回答
0

如果你在 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

请参阅Next permutation：When C++ get it right to how std::next_permutationworks。

把它翻译成普通的C，

#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);
于 2010-01-05T01:26:55.760 回答