-1

Say I have an array of 8 elements: old_array = [6, 3, 0, 12, 14, 2, 10, 5] and I start at the last element old_array[7]=5. I want to use the new element as the index of the next element I want to copy from old_array to new_array. Result is new_array = [0,2,5]. Here is some pseudocode to do this:

old_array = [6, 3, 0, 12, 14, 2, 10, 5]
i=7
len=0
while i>0:
    len+=1
    i=old_array[i]

i=7
while i>0:
    new_array[len]=old_array[i]
    len-=1
    i=old_array[i]

This method does work, however it does not seem efficient since it uses repeated code; one loop to get the length of the new array and another to copy the array. My question is there a better way of doing this?

Edit: I am expecting some pseudocode that would do this better than my current code. Note that the array can be arbritrary, except there will eventually be a 0 element and there is a way to get to it from the last element. Also we know the last index in the old array. The preferred language is Python, but I am ok with other languages.

If this question has been answered before or can be improved kindly point me to it. Thank you.

LogicThinker12
  • 1
  • 6
  • 1
    The answer is going to be different for different programming languages. What language are you using? – Andrew Merrill Mar 03 '21 at 20:25
  • This has already been answered here -> https://stackoverflow.com/questions/4108313/how-do-i-find-the-length-of-an-array – xx4g Mar 03 '21 at 20:27
  • @AndrewMerrill I am using Python. – LogicThinker12 Mar 03 '21 at 20:30
  • @xx4g, that is not quite what I am looking for, how would you then go about copying that array to the new one? Doing sizeof(array)/sizeof(array[0]) in C simply gives me the size of an array, but I already know that to begin with. – LogicThinker12 Mar 03 '21 at 20:32
  • I voted "needs focus" because different languages have different ideas of what an "array" is. If you want an answer for Python, ask for Python, and create another question for C if you're curious (obviously, search first, etc.) Stack Overflow is not a good place to have an open-ended discussion about how *all programming languages* do anything. – trent Mar 03 '21 at 22:36
  • Thanks for the feedback, I'll make a new post about this. – LogicThinker12 Mar 04 '21 at 00:47

2 Answers2

0

You could simply start with an empty list and append the items one by one:

indices = [6, 3, 0, 12, 14, 2, 10, 5]
start = -1
result = []
index = start
while index != 0:
    index = indices[index]
    result.append(index)
result

Which returns [5, 2, 0].

Note that the list is reversed compared to your desired output, so you could simply reverse it:

result[::-1]
# [0, 2, 5]

or use a deque in order to prepend the values.

You seem to be worried about using more than one loop. It really isn't a problem if you use more than one, and you probably won't notice any performance difference anyway.

What you should be worried about, is that your list isn't properly defined if indexes are outside of the range (e.g. [3, 4, 5]) or that the generation can be stuck in an infinite loop (e.g. [0, 1]).

As far as I can tell, if the new list is correctly defined, it cannot be larger than the original list, so you could use the same length for both if you want to use static lengths.

Eric Duminil
  • 52,989
  • 9
  • 71
  • 124
  • Hi, thanks for your response, this is along the lines of what I am looking for. How would you do this in a language that didn't support array.append like C? Would you need to build a queue? – LogicThinker12 Mar 03 '21 at 21:27
  • Also python allows you to do result[::-1], but would you need to make a loop to reverse it in another language? – LogicThinker12 Mar 03 '21 at 21:39
  • @LogicThinker12: I edited my answer. Using two loops instead of 1 (or even 100) really shouldn't make much of a difference. You've got potentially larger problems with your definition, though. – Eric Duminil Mar 03 '21 at 21:54
0

There is no native function that will do that but you can use a bit of trickery in a list comprehension:

old = [6, 3, 0, 12, 14, 2, 10, 5]

new = [i.extend(old[i[0]:][:i[0]>0]) or i.pop(0) for i in [old[-1:]]
       for _ in old if i][::-1]

print(new)
[0, 2, 5]

This uses an internal list (i) to hold the value to be placed in the array. Each iteration adds the next value to the i list and consumes its first value as output. The next value is taken from the old list at the position specified in i only if that position is > 0. This is what i.extend(old[i[0]:][:i[0]>0]) does. Given that append() always returns None, the actual output value alswya comes from or i.pop(0) which also removes the value from i. When i is empty, no more values are output. The for _ in old part ensure that we will perform the operation as many times would be needed if all elements were copied.

Although the reduce() function is frowned upon by many Python users, it could be used for this:

from functools import reduce

new = reduce(lambda a,_:([old[a[0]]] + a) if a[0] else a,old[:-1],old[-1:])

print(new)
[0, 2, 5]

If you're going to do it using loops, it can be expressed simply as:

new = old[-1:]
while new[0]:new.insert(0,old[new[0]])

print(new)
[0, 2, 5]
Alain T.
  • 40,517
  • 4
  • 31
  • 51
  • Thanks for your response, this is a much shorter way of doing it. Python allows you to do result[::-1], but would you need to make a loop to reverse it in another language that did not support this feature like C? – LogicThinker12 Mar 03 '21 at 21:45