Re: [algogeeks] Reverse dutch flag problem
Sorry, small mistake in designated index calculation.
It should be k*p2 % (n-1) instead of (k*p2 -1) % (n - 1).
Thanks,
- Ravindra
On Thu, Nov 3, 2011 at 11:37 PM, ravindra patel wrote:
> This is a special case of shuffling problem. In shuffling problem we have
> to merge k (here k = 3) parts of array such that each kth element is from
> the same sub-array and in same order. For eg -
> a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4 should become => a1 b1 c1 a2 b2 c2 a3
> b3 c3 a4 b4 c4.
>
> Usually shuffling problem can be solved only in O(n*logn) time without
> additional space, but here you have an added advantage. You know what the
> sequence should look like exactly. So here goes the O(n) solution with
> constant space.
>
> 1- Take 2 pointers p1 and p2 initialize both of them to index 1 (second
> element)
> 2- now for each element at p2 find the right index where it should go and
> put it thr. The right index is -
> (k*p2 -1) % (n-1); // k=3 here
>
> 3- Keep doing it until p2 becomes same as p1 again.
> 4- Now advance p1 till the elements are in order 0 1 2 0
> 5- if p1 is less than n-1 than set p2 = p1. Repeat thru step 2-5 again.
>
> Here is a primitive C code to do the same.
>
> int p1 = p2 = 1;
> int preVal, next, temp;
>
> while (p1 < n)
> {
>preVal = a[p1];
>p2 = p1;
>
> do{
> next = (k*p2 -1) % (n-1); // k=3 here
> temp = a[next];
> a[next] = preVal;
> preVal = temp;
> p2 = next;
> } while (p2 != p1)
>
> while(p1 < n)
> {
>if( ((a[p1] - a[p1-1]) == 1) || (a[p1] - a[p1-1]) == -2)) //
> elements are in sequence 0 1 2 0
> p1++;
> else
> break;
> }
> }
>
>
> Feedback welcome :-).
> - Ravindra
>
>
> On Wed, Nov 2, 2011 at 6:43 PM, shady wrote:
>
>> any solutions for this ?
>> dutch national flag problem could be done in O(n) time and O(1) space by
>> considering two pointers, but how to do this (reverse dutch national flag
>> problem) ?
>>
>>
>> On Sat, Aug 20, 2011 at 3:27 PM, Sanjay Rajpal wrote:
>>
>>> Suppose we are given a string .
>>>
>>> Make it 012012012012 in O(n) time and O(1) space.
>>> Sanju
>>> :)
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Reverse dutch flag problem
This is a special case of shuffling problem. In shuffling problem we have
to merge k (here k = 3) parts of array such that each kth element is from
the same sub-array and in same order. For eg -
a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4 should become => a1 b1 c1 a2 b2 c2 a3
b3 c3 a4 b4 c4.
Usually shuffling problem can be solved only in O(n*logn) time without
additional space, but here you have an added advantage. You know what the
sequence should look like exactly. So here goes the O(n) solution with
constant space.
1- Take 2 pointers p1 and p2 initialize both of them to index 1 (second
element)
2- now for each element at p2 find the right index where it should go and
put it thr. The right index is -
(k*p2 -1) % (n-1); // k=3 here
3- Keep doing it until p2 becomes same as p1 again.
4- Now advance p1 till the elements are in order 0 1 2 0
5- if p1 is less than n-1 than set p2 = p1. Repeat thru step 2-5 again.
Here is a primitive C code to do the same.
int p1 = p2 = 1;
int preVal, next, temp;
while (p1 < n)
{
preVal = a[p1];
p2 = p1;
do{
next = (k*p2 -1) % (n-1); // k=3 here
temp = a[next];
a[next] = preVal;
preVal = temp;
p2 = next;
} while (p2 != p1)
while(p1 < n)
{
if( ((a[p1] - a[p1-1]) == 1) || (a[p1] - a[p1-1]) == -2)) //
elements are in sequence 0 1 2 0
p1++;
else
break;
}
}
Feedback welcome :-).
- Ravindra
On Wed, Nov 2, 2011 at 6:43 PM, shady wrote:
> any solutions for this ?
> dutch national flag problem could be done in O(n) time and O(1) space by
> considering two pointers, but how to do this (reverse dutch national flag
> problem) ?
>
>
> On Sat, Aug 20, 2011 at 3:27 PM, Sanjay Rajpal wrote:
>
>> Suppose we are given a string .
>>
>> Make it 012012012012 in O(n) time and O(1) space.
>> Sanju
>> :)
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Reverse dutch flag problem
any solutions for this ? dutch national flag problem could be done in O(n) time and O(1) space by considering two pointers, but how to do this (reverse dutch national flag problem) ? On Sat, Aug 20, 2011 at 3:27 PM, Sanjay Rajpal wrote: > Suppose we are given a string . > > Make it 012012012012 in O(n) time and O(1) space. > Sanju > :) > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Reverse dutch flag problem
one solution might be: to traverse whole list counting no of zeros and 1's. and then make another string(or overwrite the same) with the required pattern,append any other characters(suppose all 0's exhausted and some 1's and 2's were left) left at the end. is there any better solution?? On Sat, Aug 20, 2011 at 4:20 PM, sukran dhawan wrote: > i that .ink the soln for this problem is given in geeksforgeeks.com > > > On Sat, Aug 20, 2011 at 3:27 PM, Sanjay Rajpal wrote: > >> Suppose we are given a string . >> >> Make it 012012012012 in O(n) time and O(1) space. >> Sanju >> :) >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Reverse dutch flag problem
i think the soln for this problem is given in geeksforgeeks.com On Sat, Aug 20, 2011 at 3:27 PM, Sanjay Rajpal wrote: > Suppose we are given a string . > > Make it 012012012012 in O(n) time and O(1) space. > Sanju > :) > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Reverse dutch flag problem
Suppose we are given a string . Make it 012012012012 in O(n) time and O(1) space. Sanju :) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
