Computing arrayindex

SoftwareTester · #1 $Old$ December 26th, 2007, 02:16 AM

As i think my problem is a mathematical one I post it here, if I should be somewhere else please tell me where.

I have a multiple array (5 or 6 dimensions each being of same size) where only elements with different indexcombinations are being filled (i.e. if element [1,2,3,4,5,6] being filled element [6,5,4,3,2,1] will NOT be filled) so I want to store all elements of such a multiple array in a lineairarray and compute the indexes for each element as it saves a lot of memory.

in code
N = 20; // maximum number of an element in each dimension
MaxIndex= N * ((N+1)/2) * ((N+2)/3) * ((N+3)/4) * ((N+4)/5) * ((N+5)/6);
long[] Array = new long [MaxIndex];
Index=0;// Index in the array
for (i1=0; i1<N; i++)
for (i2=0; i2<N+1; i++)
for (i3=0; i3<N+3; i++)
for (i4=0; i4<N+4; i++)
for (i5=0; i5<N+5; i++)
for (i6=0; i6<N+6; i++)
{
Array[Index++] = <something>;
}
}
}
}
}
}

How can I calculate the index of ANY element in Array[] given values for i1, i2, i3, i4, i5, i6 ?

Remark:
for a 2 dimensional array I know the formule
i2 + i1 * N - (i1 * (i1+1) / 2);

I'm looking for something similar for multiple dimensions

Thanks for any help in advance

CaptainBlack · #2 $Old$ December 29th, 2007, 02:10 AM

Quote:

Originally Posted by SoftwareTester $View Post$

As i think my problem is a mathematical one I post it here, if I should be somewhere else please tell me where.

I have a multiple array (5 or 6 dimensions each being of same size) where only elements with different indexcombinations are being filled (i.e. if element [1,2,3,4,5,6] being filled element [6,5,4,3,2,1] will NOT be filled) so I want to store all elements of such a multiple array in a lineairarray and compute the indexes for each element as it saves a lot of memory.

in code
N = 20; // maximum number of an element in each dimension
MaxIndex= N * ((N+1)/2) * ((N+2)/3) * ((N+3)/4) * ((N+4)/5) * ((N+5)/6);
long[] Array = new long [MaxIndex];

[snip]

Why do you think MaxIndex is this ( $30800$ ), rather than say:

$MaxIndex1=N(N-1)(N-2)(N-3)(N-4)(N-5)\approx 27.9\times 10^{6}$ ?

(I would consider using some other type of structure for this data, maybe a linked list
with each record holding the indices and the value)

RonL

SoftwareTester · #3 $Old$ December 29th, 2007, 03:29 PM

Quote:

Originally Posted by CaptainBlack $View Post$

Why do you think MaxIndex is this ( $30800$ ), rather than say:

$MaxIndex1=N(N-1)(N-2)(N-3)(N-4)(N-5)\approx 27.9\times 10^{6}$ ?

(I would consider using some other type of structure for this data, maybe a linked list
with each record holding the indices and the value)

RonL

As to me element (1,2,3,4,5,6) is the same like (3,1,5,6,2,4) or any other combination of those indeces and I created and counted the elements (output in Excel, I checked the numbers) I actually SEE MaxIndex being that value.

Using linked lists will double (at least) the memory usage and also (at least) lookup time (important as I have to access the elements millions of times).
What I actually want is being able to calculate the position of each individual element so that for a given combination of indices I can retrieve the individual element very fast without the need for SEARCHING.

Any help will be appreciated

SoftwareTester · #4 $Old$ August 2nd, 2008, 07:14 AM

For those who are interested:

I managed to calculate the index of ANY combination in a list by using combinadics and its speed is very good (and independent of the element to lookup) and actually much better compared to binary searching the list even for rather small lists.
Information leading to solving the problem has been obtained from Combinadic - Wikipedia, the free encyclopedia