Results 1 to 4 of 4

Math Help - Computing arrayindex

  1. #1
    Newbie
    Joined
    Dec 2007
    Posts
    14

    Computing arrayindex

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2007
    Posts
    14
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Dec 2007
    Posts
    14
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Computing A^k
    Posted in the Advanced Algebra Forum
    Replies: 7
    Last Post: September 19th 2011, 02:51 PM
  2. Computing Eigenvectors
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: April 12th 2010, 02:42 AM
  3. Computing ROI ?
    Posted in the Business Math Forum
    Replies: 1
    Last Post: May 13th 2009, 03:46 PM
  4. Computing e^A
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: November 27th 2008, 07:49 AM
  5. computing
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 28th 2007, 01:25 AM

Search Tags


/mathhelpforum @mathhelpforum