A puzzle - nested for-loops 
Author Message
 A puzzle - nested for-loops

I have a frustrating little mathematical/logical challenge
which I have solved but in a very (very) clumsy way

Any ideas for a 'clever' solution

I have an n-dimensional matrix for which I use an associative array.
For instance, here is a 6 dimensional one and I point to any cell with
statements like matrix[1,4,5,7,2,3]=1

Each dimension has dim[] elements, eg dim[1]=4, means that the first
subscript may take values of 1, 3 or 4

My challenge is how to set each of the cells of the matrix to be '1'

 The conceptual way is to have 'n' nested for-loops, but since 'n' is
variable this cant be hard-coded

All help much appreciated

Mark
---
Mark Katz
Mark-IT, London. Delivering MR-IT/Internet solutions
Tel: (44) 20-8731 7516, Fax: (44) 20-8458 9554; http://www.*-*-*.com/



Tue, 30 Dec 2003 19:14:58 GMT  
 A puzzle - nested for-loops

Quote:

> I have a frustrating little mathematical/logical challenge
> which I have solved but in a very (very) clumsy way

> Any ideas for a 'clever' solution

> I have an n-dimensional matrix for which I use an associative array.
> For instance, here is a 6 dimensional one and I point to any cell with
> statements like matrix[1,4,5,7,2,3]=1

> Each dimension has dim[] elements, eg dim[1]=4, means that the first
> subscript may take values of 1, 3 or 4

> My challenge is how to set each of the cells of the matrix to be '1'
>  The conceptual way is to have 'n' nested for-loops, but since 'n' is
> variable this cant be hard-coded

I'd say a 'generic' solution (ok, maybe not a very clever one)
would be something like the recursive function below.

Of course, once existing all the needed elements in each dimension
the obvious approach would be for(n in arr)...

BEGIN{  
  numofdims=0
  dims[++numofdims]=2
  dims[++numofdims]=3
  dims[++numofdims]=4

  setfromdim(1,arr,numofdims,dims,"",1)  ## THIS ONE

  printfromdim(arr,numofdims,dims,"",1)  ## THIS a test
  setall(2,arr)
  printfromdim(arr,numofdims,dims,"",1)
  exit

Quote:
}  

function setfromdim(value, arr, numofdims, dims, keysofar, thisdim \
, n){
  if(thisdim > 1) {
    keysofar = keysofar ","
  }
  if(thisdim < numofdims) {
    for(n=1; n<=dims[thisdim]; n++) {
      setfromdim(value, arr, numofdims, dims, keysofar n, thisdim+1)
    }    
  } else {
    for(n=1; n <= dims[thisdim]; n++) {
      arr[keysofar n] = value
    }    
  }

Quote:
}

function printfromdim(arr, numofdims, dims, keysofar, thisdim \
, n,key){
  if(thisdim > 1) {
    keysofar = keysofar ","
  }
  if(thisdim < numofdims) {
    for(n=1; n<=dims[thisdim]; n++) {
      printfromdim(arr, numofdims, dims, keysofar n, thisdim+1)
    }    
  } else {
    for(n=1; n <= dims[thisdim]; n++) {
      key=keysofar n
      print "arr["key"]=" arr[key]
    }    
  }

Quote:
}

function setall(value, arr \
, n) {
  for(n in arr) {
    arr[n]=value
  }

Quote:
}

--
  All true believers shall break their eggs at the convenient end.



Tue, 30 Dec 2003 19:50:12 GMT  
 A puzzle - nested for-loops

Quote:

>I have a frustrating little mathematical/logical challenge
>which I have solved but in a very (very) clumsy way

>Any ideas for a 'clever' solution

>I have an n-dimensional matrix for which I use an associative array.
>For instance, here is a 6 dimensional one and I point to any cell with
>statements like matrix[1,4,5,7,2,3]=1

>Each dimension has dim[] elements, eg dim[1]=4, means that the first
>subscript may take values of 1, 3 or 4

>My challenge is how to set each of the cells of the matrix to be '1'

> The conceptual way is to have 'n' nested for-loops, but since 'n' is
>variable this cant be hard-coded

>All help much appreciated

>Mark

Thanks to Perique (??) for his interesting and mega fast response

I went for a 5 mins walk in the nearby Hampstead Heath and came up
with the following intriguing solution. It simply maps each of
the combinations into a number and then unravels it

eg imagine the matrix was 3 by 2
Then we get
1,1  -> 1
1,2  -> 2
2,1  -> 3
2,2  -> 4
3,1  -> 5
3,2  -> 6
And here's the code that I used to check it out
--
# Program to generate all combination for an n-dimensional matrix
function fill(j){
  lval=j; key=""
  for (i1=n; i1 >= 1; i1--) {
    thiss=lval % dim[i1]
    key = thiss +1 "," key
    lval= int(lval/dim[i1])}
  print j, lval, key}

{ n=split($0,dim," ")}
END {
  maxval=1; for (i=1; i<=n; i++) maxval=maxval*dim[i]
  for (i=0;i<maxval;i++) fill(i)}

#On this data
#  4 5 2 3
---
Mark Katz
Mark-IT, London. Delivering MR-IT/Internet solutions
Tel: (44) 20-8731 7516, Fax: (44) 20-8458 9554; http://www.mark-it.co.uk



Tue, 30 Dec 2003 20:30:31 GMT  
 A puzzle - nested for-loops
...

Quote:
>I have an n-dimensional matrix for which I use an associative array.
>For instance, here is a 6 dimensional one and I point to any cell with
>statements like matrix[1,4,5,7,2,3]=1

>Each dimension has dim[] elements, eg dim[1]=4, means that the first
>subscript may take values of 1, 3 or 4

>My challenge is how to set each of the cells of the matrix to be '1'

>The conceptual way is to have 'n' nested for-loops, but since 'n' is
>variable this cant be hard-coded

#begin mat_test.awk
BEGIN {
    #reuse dims to store number of dimensions
    if ((dims = split(dims, dim, "[,;]?[ \t]+")) == 0) exit

    #instantiate the matrix
    for (j = 1; j <= dim[1]; ++j) m[j] = 1

    #flesh it out without undue concern about index order
    for (n = 2; n <= dims; ++n) {
        for (i in m) {
            for (j = 1; j <= dim[n]; ++j) m[i, j] = 1
            delete m[i]
        }
    }

    if (dims > 0) printmat(m, dim, dims)

Quote:
}

#recursive function preserves index order
#nb: n and t are 'optional' args used when fcn calls itself
function printmat(m, dim, dims    , n, t    , i, j) {
    ++n
    for (i = 1; i <= dim[n]; ++i) {
        j = ((n > 1) ? t SUBSEP i : i)
        if (n < dims) {
            printmat(m, dim, dims, n, j)
        } else {
            print j, m[j]
        }
    }
Quote:
}

#end mat_test.awk

Call as (e.g.)

awk -f mat_test.awk -v dims="2 3 4 5"



Wed, 31 Dec 2003 03:43:37 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. How to get out of the Forloop while it is still in the loop

2. nested while loops, inside loop not stopping correctly

3. That nested nested nested if statement...

4. real numbers while loop puzzle

5. while loop - real numbers - puzzle

6. Puzzle: Fortran 77 do-loop.

7. Puzzle: Fortran 77 do-loop (integer*2 version).

8. how to nest while loops

9. Smalltalk rocks, and a newbie question ( nested loops ).

10. Nested Awk loops?

11. Nested ACCEPT loops with ROUTINE

12. Smalltalk rocks, and a newbie question ( nested loops ).

 

 
Powered by phpBB® Forum Software