This's called permutations.
Here's a starting point - you can expand on this to read from a file:

nawk -v str='1 2 3 4 5 6 7 8 9' -f perm.awk

perm.awk:

BEGIN {
  str = ( str != "") ? str : "1 2 3"
  strN=split(str, arr, " ")
  permute(arr, 1, strN)
}

function printV(v, size,   i)
{
    for (i = 1; i <= size; i++) {
      printf("%4d", v[i] );
    }
    printf("\n");
}


function permute(v, start, n,    i,tmp)
{
  if (start == n) {
    printV(v, n);
  }
  else {
    for (i = start; i <= n; i++) {
      tmp = v[i];

      v[i] = v[start];
      v[start] = tmp;
      permute(v, start+1, n);
      v[start] = v[i];
      v[i] = tmp;
    }
  }
}