Shell Programming and Scripting

Hi,

I'm trying to write an awk function that returns all possible permutations of n items chosen in a list of m items. For example, given the input "a,b,c,d,e" and 3, the function should return the following :

Code:

a a a
a a b
a a c
a b a
a b b
...
c a a
c a b
...
e e c
e e d
e e e

(125 lines = 5 ^^ 3).

I've managed to write a function with nested loops that works, but only for a predetermined depth. I can't seem to manage the recursion if I want n to be variable.

Also, an added difficulty is that I need the results in an array for further processing in the same script, not just output to the console.

Any help would be much appreciated.
Chris

Then. please post your function and script(s) what you wrote so we can help you.

Thanks for your prompt response. I didn't post my code as it's not really much use. I've also searched this forum, but none of the threads about combinations and/or permutations does exactly what I need.

Here's what I have so far. It's not in a function as yet, and the loops are hard-coded two deep. The variable len isn't used at all.

Code:

BEGIN {
  list = "a,b,c,d,e"
  len = 3
  sep = ","
  n = split(list,words,sep)
#  for (i in words) print i, words[i]
  for (i=1;i<=n;i++) {
    for (j=1;j<=n;j++) {
	  print words[i], words[j]
	}
  }
}

Ultimately, I need to be able to access and manipulate the results in an array.

Thanks,
Chris

Some recursion will help...

Code:

#!/usr/bin/awk -f

function perm(list,len,current_set,      word) {
  if(len==1)
    for(word in list)
      print current_set list[word]
  else
    for(word in list)
      perm(list,len-1,current_set list[word] " ")
}

BEGIN {
  list = "a,b,c,d,e"
  sep = ","
  n = split(list,words,sep)
  perm(words,4)
}

Another variation:

Code:

awk -v n=3 -v inp="a,b,c,d,e" '
  function perm(p,s,	i) {
    for(i=1;i<=n;i++)
      if(p==1)
        printf "%s%s\n",s,A[i]
      else
        perm(p-1,s A[i]" ")
  }

  BEGIN {
    split(inp,A,/,/)
    perm(n)
  }
'

What I'm writing now is important for programs with a lot more code, but I think it has benefits in small (awk) programs in this forum too.

Descriptive code

For me - and probably for others like the partly beginner level thread starters more alike - non-descriptive variable names makes it harder to read the code. I see this here in this forum a lot. I assume brevity of code is some kind of goal involved here.

Writing Code that is easily understandable with little effort is far more important to me. And of course readabilty / maintainibility on one side and efficient, clean and short code on the other side are both important and for both must be found a suitable balance. In real life, other people read my code to, or I myself after a long time again and I'd like to avoid that experience I had in the past: "Oh crap! What did I smoke when I wrote that code?"

As an awk example(Scrutinizers variant above is written much better than the first one): split(a,b,c) vs split(text,result,pattern)

This helps me even if I do not know the syntax of split, so I do not have to check the documentation for split() right away.

So I would like it to have code, I can easily understand. I like a solution more, which I may find in this forum even years after it was posted and I quickly can understand it.

Global Variables

(actually i decided to use introduces a new global variable in my fix) I think it's good design, to avoid global variables whenever possible(See http://wiki.c2.com/?GlobalVariablesAreBad). For this forum, a solution that does this without globals avoids copy-and-paste problems: "Huu, I take this function, and put it into my code, and I like it, if it just works." and bamm! Variable collision and it crashes or just does not work. Maybe this(not-working-code with side-effects) is a nice to have too in terms of: Make sure you really understand your code, before trying to run it! Do not just copy it! ...but for I appreciate the other way.

@Scrutinizer:
... a small fix (your variant does only use n elements of the list, not all)

Code:

awk -v n=3 -v inp="a,b,c,d,e" '
  function perm(p,s,    i) {
   for(i=1;i<=c;i++)
     if(p==1)
       printf "%s%s\n",s,A[i]
      else
        perm(p-1,s A[i]" ")
  }
 
  BEGIN {
    c=split(inp,A,/,/)
    perm(n)
  }
'