Shifting an array to left or right

Learning
1

Greetings,
I’m trying to write a function to move around the elements inside an array.
I want it to look like this:
let a = [|1;2;3;4;5|];;
shift_array a 2;;
int array array = [|4;5;1;2;3|];;
or
shift_array a (-2);;
int array array = [|3;4;5;1;2|];;

I have it somewhat figured out for a list, but for an array I’m still unable to come up with a solution. Some advice or help would be greatly appreciated. Thank you!

2

First question: are you doing this in-place, or are you going to build a fresh array?

3

Would be great if it could be done in-place. But it’s not that important.

4

After just cursorily thinking it thru, it seems like maybe it’s worth doing by generating a fresh array first, and then thinking about how to do it in-place. I suspect it’s not possible to do it in-place without some temporary buffer, but I haven’t thought about it long enough to be sure of that.

5

I would just be performing the shifting on any array I pass into the function. I’d like to know if it’s possible to get the value from an index and then put it so many spaces away in a new array of the same length.

6

This task strongly reminds me another famous task about cutting array in two parts, swapping them and concatenating. The fancy algorithm is rather very fancy (spoiler alert!)

perfrom the same operation in-place on three subarrays

but pseudo code of the one kind of optimal can be found here, if I’m not mistaken

1 Like
7

I came up with this, but I’m being held back by an syntax error where the second array is made.
let shift_array arr x =
let size = Array.length arr
let sec_arr = Array.make size 0
for i = 0 to size - 1 do
if i < x
then (sec_arr.(size - x + 1) <-arr.(i))
else (sec_arr.(i - x) <- arr.(i))
done

I’m just not sure how to print out the new array.

8

You are missing in keywords on the 2nd and 3rd lines.

9

Hmm … not gonna spend the time to think about how to extend your pointer to a solution to the original problem [got a ton of code to write today], but it seems … compelling that there’s a way.

10

It is working now, but the function is of type int array -> int -> unit = <fun>. I’m looking to get 'a array -> int 'a array, is there a workaround for that? If not how could I print out the new array in the original function.

11

Will copying array be helpful?

# Array.copy;;
- : 'a array -> 'a array = <fun>
12

Hmm surely, but I’m not so sure I know how to implement that.

13 
let ashift a x =
  let n=Array.length a in
  let f a r s =
    let a1=Array.sub a r s in
    let a2=Array.sub a 0 r in
    Array.blit a1 0 a 0 s;
    Array.blit a2 0 a s r
  in
  if x>=0 then f a (n-x) x
  else f a (abs x) (n+x)

Note: it doesn’t check the boundaries on x (the shift amount).

15

I’ve managed to get a solution from all this, you have all been extremely helpful, thank you all!