• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Liutauras Vilda
  • Campbell Ritchie
  • Tim Cooke
  • Bear Bibeault
  • Devaka Cooray
Sheriffs:
  • Jeanne Boyarsky
  • Knute Snortum
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Ganesh Patekar
  • Stephan van Hulst
  • Pete Letkeman
  • Carey Brown
Bartenders:
  • Tim Holloway
  • Ron McLeod
  • Vijitha Kumara

Rotating array in right in k block  RSS feed

 
Ranch Hand
Posts: 946
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

I am working on a question in which i need to rotate an array right side by k steps. I am trying to use Juggling algorithm.
I got struck in odd case values (specially last and 2nd last values).

ex: say if i have an array like  [1,2,3,4,5,6,7,8}
so rotating 2 steps right means resultant array should be {7,8,1,2,3,4,5}.

I can do the same using brute force algo but need to optimize it.

Any guess where i am getting wrong? Here is my code:




my values are coming:  


 
Rancher
Posts: 2835
96
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Can you explain your algorithm, since it is not clear to me? Meanwhile, put some println's in your code, so that you can follow what is happening. For instance:

But there is little to optimize (in code? simplicity? run time?). You must perform as many translations as your array is long. There is a handy method in the Collections class that enables you to do the rotation without all that index juggling, at the cost of some performance, I think. But does a couple of milliseconds matter much?
 
Piet Souris
Rancher
Posts: 2835
96
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I understand your algo, although it is hard to say where it goes wrong. It is too simple, and when you save the rightmost element to the variable temp, you put that temp too early back into the array. Furthermore, your routine behaves reasonably with a shikt of 2, but fails for higher shifts. Lastly, whenever the shift is odd, the code crashes.

So here is the algo in my words (if wrong, let me know). Lets start with an array of length 7, and a shift of 3. For temporary storage, let Integer[] backup = new Integer[input.size]. Fiurthermore, to simplify the code, lets make shift to lie between 0 and size.
We do 3 blocks of shift, equal to the shift parameter (here 3), with blocknumbrs from 0 to 2
Within each block:
    let the index 'to' be equal to: size - 1 - blocknr
    let the index 'from' be equal to 'to - shift'
    save input[to] to backup: backup[(to + shift) % size = input[to]
    now, while (index from > 0) do:
        input[to] = input[from]
        to = from
        from -=k
     end while
next block
then, put the backup into input again
Code:

It should also work with a negative shift, so a rotateLeft.

But what is wrong with this code?
 
Tushar Goel
Ranch Hand
Posts: 946
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for the reply but i should mentioned to you i am not allowed to use extra array. Yes there are several different way to approach this problem like the way you mentioned, using recursive ops.

But for the learning prospective, i am trying to use algo which does take only constant space and solve it in o(n) time.

The original algo is used to rotate an array left wise but i am trying to use right side. So, i am not sure if it is possible to implement or not.

The actual algo is explained here in method 3, array_rotation

 
Saloon Keeper
Posts: 4766
52
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I was not familiar with "Juggling" but a quick google turned up an example which was subtly different than yours and probably more efficient by a nano-second or two. Unfortunately it only did a rotate left, but you can implement rotate right using that.
 
Tushar Goel
Ranch Hand
Posts: 946
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Carey Brown wrote:




WOW.... it is so easy. I have not think that way. It can be done this way as well.... I have spent 2 days on it and solution was so simple...
Thank you...
 
Carey Brown
Saloon Keeper
Posts: 4766
52
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You're welcome.
 
Piet Souris
Rancher
Posts: 2835
96
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I totally underestimated the role of GCD. That made me having to save 'Shift' numbers, instead of just 1. Clever guys, these GeeksForGeeks!

But I never like methods that do a lot of this index juggling. It is often difficult to get it right and makes the code hard to follow. I mentioned a method in the Collections class, that we can use to let Java do all the hard work. The two problems (what are problems?) are that that method works with Lists, and therefore leaves the input array unmodified. But suppose we have two methods: List arrayToList(int[] array' and 'int[] listToArray(List list)' we could have:

And 'shift' can be positive or negative, to detrmine the direction of the shift.
 
Tushar Goel
Ranch Hand
Posts: 946
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:I totally underestimated the role of GCD. That made me having to save 'Shift' numbers, instead of just 1. Clever guys, these GeeksForGeeks!

But I never like methods that do a lot of this index juggling. It is often difficult to get it right and makes the code hard to follow. I mentioned a method in the Collections class, that we can use to let Java do all the hard work. The two problems (what are problems?) are that that method works with Lists, and therefore leaves the input array unmodified. But suppose we have two methods: List arrayToList(int[] array' and 'int[] listToArray(List list)' we could have:

And 'shift' can be positive or negative, to detrmine the direction of the shift.



Actually i have checked Java 7 rotate method as well.. Internally they are using separate list to perform rotate but sometimes, we have to give a solution which is in place and takes constant memory.

But still i am unable to find out the problem in my original code. Not sure where i am wrong in that solution.

Meantime,i found another solution by recursive calls as mentioned in Programming Pearls.
 
Carey Brown
Saloon Keeper
Posts: 4766
52
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Tushar Goel wrote:Meantime,i found another solution by recursive calls as mentioned in Programming Pearls.


I'm curious. Could you post your code for that?
 
Sheriff
Posts: 23713
50
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Without seeing the code I would guess that its purpose is to store the numbers being moved on the stack, thus sneakily circumventing the rule against storing them in another array.
 
Tushar Goel
Ranch Hand
Posts: 946
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Carey Brown wrote:

Tushar Goel wrote:Meantime,i found another solution by recursive calls as mentioned in Programming Pearls.


I'm curious. Could you post your code for that?



Here is the code, i have implemented:




Actually in this we reverse array 3 times:
1) 0 to n-d-1 times  //so first time this reverse the array of length n-d
2) n-d to n times   //this will reverse the array of d length from end
3) 0 to n times // this again reverse the array so that elements comes to their position
 
Piet Souris
Rancher
Posts: 2835
96
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
First of all, I have not looked at the replies so far, so I might bring old news that others already have explained.

Secondly: if I compare the code to my code in my previous reply, I see that they store 'shift' numbers as well, like I did, but they put them in the array as soon as possible, making it look like there is inly one number stored (in temp), while I stored them in an array, inputting them in the end. Hmmm...

As I said, I never liked this kind of solutions, with all that index juggling, they make it hard to follow what is going on. So, I suggest to look at two variants, and see how the process should go on.
But formost: you use the statement:
from = (j - k) % size;
Now, that is dangerous, since when j - k < 0, the result will also be negative, causing an IndexOutOfBoundError.
So, use
from = j - k;
if (from < 0) from += size;

Now, lets look at an array of length 8, and with a shift of 3 and a shift of 4, and see what should happen. I use more meaningful names than you used. Instead of j, I use 'to', instead of d, I use 'from', and insead of i, I use 'loopnr'.
And I refer to 'shift' as name for the shift taking place. It makes the code a little more readable. I also use the variable 'stop', that determines when a new loop should start. So here goes:

8, 3, gcd = 1
loopnr 0
to = size - 1 - loopnr = 7
temp = a[to]
stop = (to + shift) % size = 2
entering the loop, naming only the indices from and to for brevity
7 -> temp
4 -> 7
1 -> 4
6 -> 1
3 -> 6
0 -> 3
5 -> 0
2 -> 5
break the loop, since index 'from' = stop, so end with
temp -> 2
finished

Now for length 8, with shift 4, and gcd = 4
loop 0
to = size - 1 - loopnr = 7
stop = 3 (= (7 + shift) % 8
7 -> temp
3 -> 7
since 3 = stop break the loop
temp -> 3
loop 1
to = size - 1 - loopnr = 6
stop = 2
6 -> temp
2 -> 6
since 2 = stop, break the loop
temp -> 2
loop 2
to = 5
stop = 1
5 -> temp
1 -> 5
break the loop since 1 = stop
temp -> 1
loop 3
to = 4
stop = 0
4 -> temp
0 -> 4
break the loop
tmp -> 0
finished

Now, if we implement that in code, we get:




 
Marshal
Posts: 6008
415
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Tushar Goel wrote:Meantime,i found another solution by recursive calls as mentioned in Programming Pearls.


Just not to mislead other readers. The solution you showed isn't recursive. In other words, it has no single recursive call.

Remind yourself what is the recursive function. A recursive function normally has two parts:

1. Stopping condition.
Processing the case(s) where the recursive function does not call itself.

2. Recursive step.
Processing the case(s) where the recursive function calls itself.
 
Tushar Goel
Ranch Hand
Posts: 946
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Piet, Thanks for the nice and detailed explanation.. I have understood every single step you tried....

I was missing condition where i need to reset if from goes negative.. Anyway it was cool .. Thanks Again...


@Liutauras Vilda, Sorry for the confusion.. It was long time i have not involved in any serious coding.. So, i miss many points... Anyway, i am back now
and will have more discussion in coming days.. Sorry again for the confusion..
 
Tushar Goel
Ranch Hand
Posts: 946
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
actually it teaches me 1 more thing.. importance of pencil and paper before jumping over the code..

I will try next time to emulate the steps on paper first..
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!