Thread: 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

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



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

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:


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?

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?

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.

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.