La creación de cada posible valor de una matriz de tamaño fijo

Question

Estoy tratando de hacer algo muy elemental que recorrerá cada posible permutación de una matriz.

Realmente esto se está haciendo en el montaje, pero lo explicaré en C.

Básicamente, digamos que tenemos un uint8_t *data=malloc(10); array

Quiero crear un algoritmo que imprima todas las combinaciones posibles de los bytes en el data matriz.

Sí, sé que va a ser lenta (y hay muchos valores), y yo no estoy pidiendo en realidad una versión optimizada complejo .. Estoy buscando algo que me pueden dejar que se ejecuta en el ordenador como tipo de cosas tipo de fuerza bruta para encontrar ciertos valores que obedecen a ciertas condiciones ..

(nota, digo, porque permutación [0,1,2] no deben contarse los mismos que [2,1,0])

editar: También, trate de no usar demasiadas funciones libc porque voy a la conversión a un gestor de arranque independiente con sólo 512 bytes.

Yo sé Yo sé cómo hacer esto, pero para la vida de mí no puedo hacer que el algoritmo en mi cabeza!

Answer 1

Usted cuestiona sufre de una confusión terminológica raro. De lo que usted describe parece que desea generar todas las posibles 10-tuplas de valores sin signo de 8 bits. Estos no son "permutaciones" y todo esto no tiene nada que ver con la generación de permutaciones.

El código que genera todas las posibles 10-tuplas de valores uint8_t es fácil de llegar a. Por ejemplo el siguiente código simple lo hará

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

Esto no es otra cosa que un incremento cíclico de un número de 80 bits ascendente hacia la izquierda.

Por supuesto, como otros ya se ha señalado, la cantidad de tiempo que esto va a tomar hace que todo sea absolutamente inútil desde cualquier punto de vista práctico.

Answer 2

Bueno, todo el asunto es un ejercicio inútil (ver mi comentario adjunta a la pregunta), pero aquí va de todos modos (x86_64 montaje de estilo AT & T, asume las convenciones del sistema V de llamada AMD). Estoy escribiendo esto aquí sin pruebas, por lo que es muy posible que tenga errores. No obstante, la operación básica del código debe ser completamente claro.

En lugar de operar en un buffer de 80 bits en la memoria, simplemente estoy corriendo a través de todas las posibilidades de una fracción de campo de 80 bits a través de dos registros de 64 bits. Su rutina que comprueba las condiciones pueden almacenarlos en memoria y acceder a esa memoria como uint8_t si realmente desea.

    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

Yo sugeriría que lea,

Donald Knuth. The Art of Computer Programming, Volumen 4, Fascículo 2:. Generación de todas las tuplas y permutaciones

Answer 4

Hay un enfoque recursivo clásica al problema que es similar a lo siguiente:

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

ejemplo se toma de enlace en el que hay otros enfoques. La teoría detrás de esto es bastante simple .. si es necesario puedo explicar con más detalle el algoritmo pero es bastante auto-explainatory.

Answer 5

Tener un vistazo a este algoritmo para generar combinaciones de N de M elementos . Para las combinaciones de N eligen N, sólo tiene que utilizar 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');
    }
  }
************************/

La respuesta a este mensaje también puede ayudar a Algoritmo para volver todas las combinaciones de k elementos de n

Answer 6

Si estaba trabajando en 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;
}

Si 3 de entrada, salidas

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

siguiente permutación: Cuando C ++ lo hace bien de cómo funciona la std::next_permutation

---

Traduciendo esto a llano 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;
}

---

Si la pregunta no está pidiendo permutaciones de una matriz existente, sino más bien generar todas las posibles contenido de la matriz, esto es mucho más fácil. (También hay muchas más combinaciones.)

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