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=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=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=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=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; ++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

 Page 1 of 1 [ 4 post ]

Relevant Pages