Generating Combinations

Shell Programming and Scripting
1

Hi,
I need to generate all combinations upto n-1 level,
if the input file looks like say,
A
B
C
D
.
.
....

I need to generate all combinations such that first value remains constant and the remaning are combined with all possible ways.

Output

A
AB
AC
AD
ABC
ABD
ACD
ABCD
........

The input file can contain maximum of 40 values. so the combinations could be extremely high.

Any suggestions atleast how to approach generating the combinations would be helpful. Thanks in advance!!!

2

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 );
    }
    printf("\n");
}


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

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