Results 1 to 6 of 6

Math Help - Algorithm - Finding index of an array

  1. #1
    Member
    Joined
    Sep 2010
    Posts
    86

    Algorithm - Finding index of an array

    Hello everybody,
    I am having trouble of finding an index number that identifies the position of an array which is ordered as follows:

    [1, 1, 1, 1] : index 1
    [1, 1, 1, 2] : index 2
    ...
    [4, 4, 6, 6] : index ?
    [4, 4, 6, 7] : index ?
    [4, 4, 7, 7] : index ?
    [4, 5, 5, 5] : index ?
    [4, 5, 5, 6] : index ?
    [4, 5, 5, 7] : index ?
    [4, 5, 6, 6] : index ?
    ...
    [7, 7, 7, 7] : index ?

    i.e. the numbers at later positions are always at least as high as the former ones. If the maximum value of 7 is reached the former number is increased. I am wondering what would be the right way of computing the index of one of these numbers in this presented order?

    The array consists of 4 values and takes values from 1-7.
    Thank you a lot for help!
    Best, Rafael
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member BAdhi's Avatar
    Joined
    Oct 2010
    From
    Gampaha, Sri Lanka
    Posts
    252
    Thanks
    6
    you can use heptal number system for this

    for example, if you want to find the index of [4,4,6,6],

    since there is no 0 used we consider 1 as 0, 2 as 1 likewise, which eventually make us to take above array as
    3355(reduce 1 from every digit)

    this is expressed in heptal number system(since 0 to 6 is used). So convert it to decimal number system to find the index

    3355_7=(3\times7^3+3\times7^2+5\times7^1+5\times7^  0)_{10}=1216

    since first index ([1,1,1,1] or after adjusting 0000) is named - 1, add 1 to the final result (ie 1217)

    check out my work i think this works
    Last edited by BAdhi; March 5th 2011 at 06:44 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2010
    Posts
    86
    Thank you for your answer. This does unfortunately not work since e.g. consider a similar row:

    [0,0,0,0] : index 0
    [0,0,0,1] : index 1
    [0,0,0,2] : index 2
    [0,0,1,1] : index 3
    [0,0,1,2] : index 4
    [0,0,2,2] : index 5
    [0,1,1,1] : index 6
    ...

    Your calculation solves:
    {0111}_3 = 0\cdot 3^3 + 1\cdot 3^2 + 1\cdot 3^1 + 1\cdot 3^0 = 13 \neq 6

    The trick is that values are omitted by increasing dependet on the former values: This is why that kind of computation is not working.

    Any other ideas?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    5
    Awards
    2
    Does it have to be a mathematical formula, or could you use an algorithm?

    1. Generate list of all the numbers (obviously a finite list, and maybe not even very long).
    2. Given an element in the list, just do a search (might be able to do a fancy binary search, since your list is already ordered), and output the index of the matching element in the list.

    Then you're done. Would this work for you?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Sep 2010
    Posts
    86
    This is how I have it implemented now but the general trade-off is that of choosing a map over an array where the later would be much faster. I use it in a simulation that is quite limited by runtime which is why I would look for some way to compute such an index as quick as possible. What I do now is compute a hash value to which each state is mapped.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    5
    Awards
    2
    How are you using the word "map" in this context? Isn't what I'm talking about an array?

    where the later would be much faster.
    Do you mean the map or the array?

    You might be able to combine BAdhi's idea with mine: convert all the 4-digit numbers to one number, and store in an ordered array. Binary search would then be on the order of log base 2 of the number of elements in the list. That's pretty fast. Short of an actual formula to spit out the answer, I doubt you'll do much better at runtime.

    You could try listing out all the numbers yourself. I bet the list isn't all that long. You might be able to find a pattern between the digits and the index that could help you out.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. find the k'th smallest in array algorithm
    Posted in the Math Software Forum
    Replies: 1
    Last Post: December 12th 2011, 10:25 AM
  2. Finding subgroups of index 2 of the free group.
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: November 6th 2011, 03:46 PM
  3. Index calculus algorithm, -1 in factorization
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 8th 2011, 01:36 PM
  4. Replies: 0
    Last Post: July 26th 2010, 02:33 PM
  5. finding general algorithm
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 11th 2008, 06:12 AM

Search Tags


/mathhelpforum @mathhelpforum