Creating every possible value of a fixed size array

Question

Hello, I am trying to make some very elementary thing that will cycle through every possible permutation of an array.

Really this is being done in assembly, but I'll explain it in C.

Basically, say we have an array uint8_t *data=malloc(10);

I want to create an algorithm that will print every possible combination of the bytes in the array data.

Yes, I know it will be slow(and there are many values), and I'm not asking for really a complex optimized version.. I'm just looking for something that I can leave running on my computer as a sort of brute-force type thing to find certain values that obey certain conditions..

(note, I say permutation because [0,1,2] should not be counted the same as [2,1,0])

edit: Also, try not to use too many libc functions because I will be converting this to a freestanding bootloader with only 512 bytes.

I know I know how to do this but for the life of me I just can not make the algorithm work in my head!

Answer 1

There is a classic recursive approach to the problem that is similar to the following:

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

example is taken from link in which there are other approaches. The theory behind it is quite simple.. if you need I can further explain the algorithm but it's quite self-explainatory.

Answer 2

I would suggest that you read,

Donald Knuth. The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Tuples and Permutations.

Answer 3

Have a look at this algorithm for generating combinations of N out of M items. For combinations of N choose N, just use 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');
    }
  }
************************/

The answer to this post may also help you http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n

Answer 4

If you were working in 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;
}

If you input 3, it outputs

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

See Next permutation: When C++ gets it right for how std::next_permutation works.

---

Translating this to plain 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;
}

---

If the question is not asking for permutations of an existing array, but rather generating all possible array contents, this is quite a lot easier. (Also there are a lot more combinations.)

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

Answer 5

You question suffers from a weird terminological mixup. From what you describe it appears that you want to generate all possible 10-tuples of unsigned 8-bit values. These are not "permutations" and all this has nothing to do with generating permutations.

The code that generates all possible 10-tuples of uint8_t values is easy to come up with. For example the following simple code will do it

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

This is nothing else than just a cyclic increment of a 80-bit little-endian number.

Of course, as others already noted, the amount of time this is going to take makes the whole thing absolutely useless from any practical point of view.

Answer 6

Well, the whole thing is a futile exercise (see my comment attached to the question), but here you go anyway (x86_64 AT&T style assembly, assumes the AMD system V calling conventions). I'm just writing this here without testing, so it's entirely possible that it has bugs. Nonetheless, the basic operation of the code should be completely clear.

Instead of operating on an 80-bit buffer in memory, I'm simply running through all possibilities of an 80-bit field split across two 64-bit registers. Your routine that checks your conditions can store them to memory and access that memory as uint8_t if you really want to.

    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