Re: [algogeeks] Re: Inplace Array Convertion
@Sunny Your technique of Inshuffle and Outshuffle are perfect. But how to translate into the code without using extra space or say even constant space On Tue, Oct 18, 2011 at 12:43 AM, Dan wrote: > I have a hard copy of the book (years back, I implemented a fortran > version of the algorithm described in the book). I don't know if you > can find an online version or not. I'm sure there is stuff there. > Have you done a simple Google search for "in place reorder > array" ?? It's not a difficult algorithm. And Sedgewicks's books > are well known. Searches for his name may also yield results. > > Just FYI: If your rearrangement doesn't have to be in-place... you > will achieve more speed by other methods. I did testing with > rearrangement of some very large data sets. The in-place method was > noticeably slower. It also required you to write your own routine to > do the reordering. Using basic fortran, I could do the same thing in > just one or two lines of very simple code. The only advantage to the > in-place algorithm is that it uses less memory. This should only be > important if you are dealing with some very large arrays. > > Dan :-) > > > On Oct 14, 9:44 pm, Ankur Garg wrote: > > @Dan ..can you post the algo here or link to the book?? > > @Anika ...yes please post the code here..but please explain a bit about > > underlying algo ...(algo is more important than actual code ) > > > > > > > > > > > > > > > > On Sat, Oct 15, 2011 at 1:54 AM, Dan wrote: > > > On Oct 13, 7:52 pm, "shiva@Algo" wrote: > > > > Convert an array "a1 a2 a3...an b1 b2 b3...bn c1 c2 c3...cn" to > "a1b1c1 > > > > a2b2c2...anbncn", inplace > > > > > See the algorithm for memory efficient rearrangement of array elements > > > in one of the books by Robert Sedgewick such as Algorithms in C++ or > > > Algorithms in Pascal, etc. > > > > > Dan > > > > > -- > > > 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] Re: Inplace Array Convertion
cheers.. clear explanation. thanks for the effort.. :) so.. we swap 3 elements and.. run for one complete cycle of N/3 time in this prob.. Anika has a recusion of N/3 depth.. may be.. a loop that runs N/3 time should suffice. :) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/fypIulpcmZ8J. 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] Re: Inplace Array Convertion
In/Out Shuffle are two shuffling algorithms used for shuffling cards consider a pack of cards (so N = 52) and let cards are numbered from 1, 52 *In Shuffle *: cards are divided into 2 piles (k = 2) (1,2,3.26) (27,28,...52) afer one shuffle operation cards will be like (27,1)(28,2) ..(52,26) and it can be found that the card at position i(0 indexed) has moved to its new position given by formula *i <- 2*i %(N+1) N = 52 *for k piles answer will be simply *k*i % (N+1) N = 52* *Out Shuffle *: cards are divided into 2 piles (k = 2) (1,2,3.26) (27,28,...52) afer one shuffle operation cards will be like (1, 27)(2,28) ..(26,52) and it can be found that the card at position i(0 indexed) has moved to its new position given by formula *i <- 2*i %(N-1) N = 52 *for k piles answer will be simply *k*i % (N-1) N = 52 *now relating this to the Question in this thread k = 3 N = total no of elements in the array shuffle is Out shuffle now for writing program i think it can be done in O(2*n) ...will try to code soon :) On Sun, Oct 16, 2011 at 3:16 AM, sravanreddy001 wrote: > Anika, > Your algorithm appears to take O(n^2) time and also O(n) space in recursion > stack space, storing the 3 elements in recursion level. > > The direct shifting of elements to the right will take O(n2) time and O(1) > space. > > Please comment if my assumptions are incorrect. > > Can anyone provide weblink for IN?OUT shuffle card shuffling prob related > to this scenario. > and Memory efficient rearragnement of array elements. > > Thanks, > sravanreddy001 > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/RdrlNoIGpBEJ. > > 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. > -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] Re: Inplace Array Convertion
Anika, Your algorithm appears to take O(n^2) time and also O(n) space in recursion stack space, storing the 3 elements in recursion level. The direct shifting of elements to the right will take O(n2) time and O(1) space. Please comment if my assumptions are incorrect. Can anyone provide weblink for IN?OUT shuffle card shuffling prob related to this scenario. and Memory efficient rearragnement of array elements. Thanks, sravanreddy001 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/RdrlNoIGpBEJ. 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] Re: Inplace Array Convertion
Hi Anika, Can you comment on the complexity of the algorithm? It appears to be like an O(n^2). By the way, we are asked for a inplace sort, and this recursive call stores the 3 element(a,b,c) in each level. So, i iterations, and starting value of i is n/3.. so this takes an additional O(n) time. If we have additional space, it can done in O(n) time. The direct moving of elements towards the right takes O(n^2) time and no additional space. @All: please comment on the above explanation. (I couldn't find the link or source for the IN/OUT Shuffle card shuffle problems, hence looked at your code ) plz provide an weblink of the card shuffle or memory efficient rearrangement problem. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/juVr-bx5fVoJ. 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] Re: Inplace Array Convertion
initial call to this function is arrange(arr,n/3,n/3) where n is actually
3*n as per the question , like n=30 for a1,...,a10,b1,...,b10,c1,c10
The idea used here is that for some i-1 ranging from 1 to 9 for above
example, i-1 goes to 3*(i-1), n+i-1 to 3*(i-1) +1, and 2*n+i-1 to
3*(i-1)+2.. recursive function calls are used
void arrange(int arr[], int n, int i)
{
if(i == 1)
{
arr[1] = arr[n];
arr[2] = arr[2*n];
return;
}
int a = arr[i - 1];
int b = arr[n + i - 1];
int c = arr[2*n + i - 1];
arrange(arr, n, i - 1);
int x = 3 * (i - 1);
arr[x] = a;
arr[x + 1] = b;
arr[x + 2] = c;
}
On Sat, Oct 15, 2011 at 11:14 AM, Ankur Garg wrote:
> @Dan ..can you post the algo here or link to the book??
> @Anika ...yes please post the code here..but please explain a bit about
> underlying algo ...(algo is more important than actual code )
>
>
>
> On Sat, Oct 15, 2011 at 1:54 AM, Dan wrote:
>
>> On Oct 13, 7:52 pm, "shiva@Algo" wrote:
>> > Convert an array "a1 a2 a3...an b1 b2 b3...bn c1 c2 c3...cn" to "a1b1c1
>> > a2b2c2...anbncn", inplace
>>
>>
>> See the algorithm for memory efficient rearrangement of array elements
>> in one of the books by Robert Sedgewick such as Algorithms in C++ or
>> Algorithms in Pascal, etc.
>>
>> Dan
>>
>> --
>> 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] Re: Inplace Array Convertion
i have already mentioned the source it is famous shuffling algorithm. u can seach some papers on In-Shuffle and Out-Shuffle the original question in the shuffling is like how many times we need to shuffle the cards after which they will return back to initial sequence. On Sat, Oct 15, 2011 at 5:35 PM, Ankur Garg wrote: > @Sunny ..Superb Algo ..but can you share some link where we can read abt it > :)..especially where the info abt the equation u used is given > > > Thanks in Advance > > > On Sat, Oct 15, 2011 at 12:37 PM, Kunal Patil wrote: > >> @Sunny: Thanks for the info !! That's gr8..& your logic also seems to be >> working perfectly fine.. >> >> >> On Sat, Oct 15, 2011 at 12:16 PM, shady wrote: >> >>> u can always post the code.,... but before posting code, you must state >>> your algorithm >>> else code becomes useless for other users >>> >>> On Sat, Oct 15, 2011 at 1:10 AM, Anika Jain wrote: >>> i have the code solution to this.. if m allowed to post it here then i can i post it. m i allowed to post code here? On Fri, Oct 14, 2011 at 9:40 PM, gaurav yadav < gauravyadav1...@gmail.com> wrote: > @shiva...keep swapping the underline elements > > a1*a2*a3a4a5*b1*b2b3b4b5c1c2c3c4c5 > a1b1*a3*a4a5a2b2b3b4b5*c1*c2c3c4c5 > a1b1c1*a4*a5*a2*b2b3b4b5a3c2c3c4c5 > a1b1c1a2*a5*a4*b2*b3b4b5a3c2c3c4c5 > a1b1c1a2b2*a4*a5b3b4b5a3*c2*c3c4c5 > a1b1c1a2b2c2*a5*b3b4b5*a3*a4c3c4c5 > a1b1c1a2b2c2a3b3*b4*b5a5a4*c3*c4c5 > a1b1c1a2b2c2a3b3c3*b5*a5*a4*b4c4c5 > a1b1c1a2b2c2a3b3c3a4*a5*b5*b4*c4c5 > a1b1c1a2b2c2a3b3c3a4b4*b5*a5*c4*c5 > a1b1c1a2b2c2a3b3c3a4b4*c4*a5*b5*c5 > a1b1c1a2b2c2a3b3c3a4b4c4a5b5c5 > > > > -- > 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. >>> >> >> -- >> 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. > -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] Re: Inplace Array Convertion
@Sunny ..Superb Algo ..but can you share some link where we can read abt it :)..especially where the info abt the equation u used is given Thanks in Advance On Sat, Oct 15, 2011 at 12:37 PM, Kunal Patil wrote: > @Sunny: Thanks for the info !! That's gr8..& your logic also seems to be > working perfectly fine.. > > > On Sat, Oct 15, 2011 at 12:16 PM, shady wrote: > >> u can always post the code.,... but before posting code, you must state >> your algorithm >> else code becomes useless for other users >> >> On Sat, Oct 15, 2011 at 1:10 AM, Anika Jain wrote: >> >>> i have the code solution to this.. if m allowed to post it here then i >>> can i post it. m i allowed to post code here? >>> >>> >>> On Fri, Oct 14, 2011 at 9:40 PM, gaurav yadav >> > wrote: >>> @shiva...keep swapping the underline elements a1*a2*a3a4a5*b1*b2b3b4b5c1c2c3c4c5 a1b1*a3*a4a5a2b2b3b4b5*c1*c2c3c4c5 a1b1c1*a4*a5*a2*b2b3b4b5a3c2c3c4c5 a1b1c1a2*a5*a4*b2*b3b4b5a3c2c3c4c5 a1b1c1a2b2*a4*a5b3b4b5a3*c2*c3c4c5 a1b1c1a2b2c2*a5*b3b4b5*a3*a4c3c4c5 a1b1c1a2b2c2a3b3*b4*b5a5a4*c3*c4c5 a1b1c1a2b2c2a3b3c3*b5*a5*a4*b4c4c5 a1b1c1a2b2c2a3b3c3a4*a5*b5*b4*c4c5 a1b1c1a2b2c2a3b3c3a4b4*b5*a5*c4*c5 a1b1c1a2b2c2a3b3c3a4b4*c4*a5*b5*c5 a1b1c1a2b2c2a3b3c3a4b4c4a5b5c5 -- 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. >> > > -- > 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] Re: Inplace Array Convertion
@Sunny: Thanks for the info !! That's gr8..& your logic also seems to be working perfectly fine.. On Sat, Oct 15, 2011 at 12:16 PM, shady wrote: > u can always post the code.,... but before posting code, you must state > your algorithm > else code becomes useless for other users > > On Sat, Oct 15, 2011 at 1:10 AM, Anika Jain wrote: > >> i have the code solution to this.. if m allowed to post it here then i can >> i post it. m i allowed to post code here? >> >> >> On Fri, Oct 14, 2011 at 9:40 PM, gaurav yadav >> wrote: >> >>> @shiva...keep swapping the underline elements >>> >>> a1*a2*a3a4a5*b1*b2b3b4b5c1c2c3c4c5 >>> a1b1*a3*a4a5a2b2b3b4b5*c1*c2c3c4c5 >>> a1b1c1*a4*a5*a2*b2b3b4b5a3c2c3c4c5 >>> a1b1c1a2*a5*a4*b2*b3b4b5a3c2c3c4c5 >>> a1b1c1a2b2*a4*a5b3b4b5a3*c2*c3c4c5 >>> a1b1c1a2b2c2*a5*b3b4b5*a3*a4c3c4c5 >>> a1b1c1a2b2c2a3b3*b4*b5a5a4*c3*c4c5 >>> a1b1c1a2b2c2a3b3c3*b5*a5*a4*b4c4c5 >>> a1b1c1a2b2c2a3b3c3a4*a5*b5*b4*c4c5 >>> a1b1c1a2b2c2a3b3c3a4b4*b5*a5*c4*c5 >>> a1b1c1a2b2c2a3b3c3a4b4*c4*a5*b5*c5 >>> a1b1c1a2b2c2a3b3c3a4b4c4a5b5c5 >>> >>> >>> >>> -- >>> 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. > -- 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] Re: Inplace Array Convertion
u can always post the code.,... but before posting code, you must state your algorithm else code becomes useless for other users On Sat, Oct 15, 2011 at 1:10 AM, Anika Jain wrote: > i have the code solution to this.. if m allowed to post it here then i can > i post it. m i allowed to post code here? > > > On Fri, Oct 14, 2011 at 9:40 PM, gaurav yadav > wrote: > >> @shiva...keep swapping the underline elements >> >> a1*a2*a3a4a5*b1*b2b3b4b5c1c2c3c4c5 >> a1b1*a3*a4a5a2b2b3b4b5*c1*c2c3c4c5 >> a1b1c1*a4*a5*a2*b2b3b4b5a3c2c3c4c5 >> a1b1c1a2*a5*a4*b2*b3b4b5a3c2c3c4c5 >> a1b1c1a2b2*a4*a5b3b4b5a3*c2*c3c4c5 >> a1b1c1a2b2c2*a5*b3b4b5*a3*a4c3c4c5 >> a1b1c1a2b2c2a3b3*b4*b5a5a4*c3*c4c5 >> a1b1c1a2b2c2a3b3c3*b5*a5*a4*b4c4c5 >> a1b1c1a2b2c2a3b3c3a4*a5*b5*b4*c4c5 >> a1b1c1a2b2c2a3b3c3a4b4*b5*a5*c4*c5 >> a1b1c1a2b2c2a3b3c3a4b4*c4*a5*b5*c5 >> a1b1c1a2b2c2a3b3c3a4b4c4a5b5c5 >> >> >> >> -- >> 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] Re: Inplace Array Convertion
@Anika , You Already Have Permission to Post All Algorithms Realted Questions/Queries Thanks Shashank CSE,BIT Mesra -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/ZYLb7oK37rgJ. 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] Re: Inplace Array Convertion
@Dan ..can you post the algo here or link to the book?? @Anika ...yes please post the code here..but please explain a bit about underlying algo ...(algo is more important than actual code ) On Sat, Oct 15, 2011 at 1:54 AM, Dan wrote: > On Oct 13, 7:52 pm, "shiva@Algo" wrote: > > Convert an array "a1 a2 a3...an b1 b2 b3...bn c1 c2 c3...cn" to "a1b1c1 > > a2b2c2...anbncn", inplace > > > See the algorithm for memory efficient rearrangement of array elements > in one of the books by Robert Sedgewick such as Algorithms in C++ or > Algorithms in Pascal, etc. > > Dan > > -- > 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] Re: Inplace Array Convertion
Is there a pattern in the indices of the numbers we are swapping. some formula which may tell the next two indices to swap. Thanks, - Ravindra On Fri, Oct 14, 2011 at 9:40 PM, gaurav yadav wrote: > @shiva...keep swapping the underline elements > > a1*a2*a3a4a5*b1*b2b3b4b5c1c2c3c4c5 > a1b1*a3*a4a5a2b2b3b4b5*c1*c2c3c4c5 > a1b1c1*a4*a5*a2*b2b3b4b5a3c2c3c4c5 > a1b1c1a2*a5*a4*b2*b3b4b5a3c2c3c4c5 > a1b1c1a2b2*a4*a5b3b4b5a3*c2*c3c4c5 > a1b1c1a2b2c2*a5*b3b4b5*a3*a4c3c4c5 > a1b1c1a2b2c2a3b3*b4*b5a5a4*c3*c4c5 > a1b1c1a2b2c2a3b3c3*b5*a5*a4*b4c4c5 > a1b1c1a2b2c2a3b3c3a4*a5*b5*b4*c4c5 > a1b1c1a2b2c2a3b3c3a4b4*b5*a5*c4*c5 > a1b1c1a2b2c2a3b3c3a4b4*c4*a5*b5*c5 > a1b1c1a2b2c2a3b3c3a4b4c4a5b5c5 > > > > -- > 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] Re: Inplace Array Convertion
i have the code solution to this.. if m allowed to post it here then i can i post it. m i allowed to post code here? On Fri, Oct 14, 2011 at 9:40 PM, gaurav yadav wrote: > @shiva...keep swapping the underline elements > > a1*a2*a3a4a5*b1*b2b3b4b5c1c2c3c4c5 > a1b1*a3*a4a5a2b2b3b4b5*c1*c2c3c4c5 > a1b1c1*a4*a5*a2*b2b3b4b5a3c2c3c4c5 > a1b1c1a2*a5*a4*b2*b3b4b5a3c2c3c4c5 > a1b1c1a2b2*a4*a5b3b4b5a3*c2*c3c4c5 > a1b1c1a2b2c2*a5*b3b4b5*a3*a4c3c4c5 > a1b1c1a2b2c2a3b3*b4*b5a5a4*c3*c4c5 > a1b1c1a2b2c2a3b3c3*b5*a5*a4*b4c4c5 > a1b1c1a2b2c2a3b3c3a4*a5*b5*b4*c4c5 > a1b1c1a2b2c2a3b3c3a4b4*b5*a5*c4*c5 > a1b1c1a2b2c2a3b3c3a4b4*c4*a5*b5*c5 > a1b1c1a2b2c2a3b3c3a4b4c4a5b5c5 > > > > -- > 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] Re: Inplace Array Convertion
@shiva...keep swapping the underline elements a1*a2*a3a4a5*b1*b2b3b4b5c1c2c3c4c5 a1b1*a3*a4a5a2b2b3b4b5*c1*c2c3c4c5 a1b1c1*a4*a5*a2*b2b3b4b5a3c2c3c4c5 a1b1c1a2*a5*a4*b2*b3b4b5a3c2c3c4c5 a1b1c1a2b2*a4*a5b3b4b5a3*c2*c3c4c5 a1b1c1a2b2c2*a5*b3b4b5*a3*a4c3c4c5 a1b1c1a2b2c2a3b3*b4*b5a5a4*c3*c4c5 a1b1c1a2b2c2a3b3c3*b5*a5*a4*b4c4c5 a1b1c1a2b2c2a3b3c3a4*a5*b5*b4*c4c5 a1b1c1a2b2c2a3b3c3a4b4*b5*a5*c4*c5 a1b1c1a2b2c2a3b3c3a4b4*c4*a5*b5*c5 a1b1c1a2b2c2a3b3c3a4b4c4a5b5c5 -- 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] Re: Inplace Array Convertion
What should be the output in this case : a1a2a3a4b1b2b3b4c1c2c3c4 ?? -- 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] Re: Inplace Array Convertion
this problem is like Card shuffling problem(search for In-shuffle) i think solution is if indexing is zero based each i will go to -> k*i % (N-1) k = 3 and N = 3*n -1 n = no of cards in one pile Or No of a's On Fri, Oct 14, 2011 at 7:52 PM, shiva@Algo wrote: > @Gaurav how will u do for > a1a2a3a4a5b1b2b3b4b5c1c2c3c4c5 > > > On Fri, Oct 14, 2011 at 6:49 AM, gaurav yadav > wrote: > >> consider following example... >> suppose initailly we have a1a2a3b1b2b3c1c2c3 >> >> then do the following-> >> a1a2a3 b1b2b3 c1c2c3 (look for b1 in the remaining array and swap with >> a2 , so in this case swap(a2,b1) ) >> a1b1a3 a2b2b3 c1c2c3 (similarly swap(a3,c1) ) >> a1b1c1 a2b2b3 a3c2c3swap(b3,c2) >> a1b1c1 a2b2c2 a3b2c3 >> >> >> this in inplace >> >> (plz correct if im wrong) >> >> -- >> 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. > -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] Re: Inplace Array Convertion
Its Out Shuffle not In shuffle, although both are similar and you can read both On Fri, Oct 14, 2011 at 8:26 PM, sunny agrawal wrote: > this problem is like Card shuffling problem(search for In-shuffle) > i think solution is > if indexing is zero based > each i will go to -> k*i % (N-1) > k = 3 and N = 3*n -1 > n = no of cards in one pile Or No of a's > > > On Fri, Oct 14, 2011 at 7:52 PM, shiva@Algo wrote: > >> @Gaurav how will u do for >> a1a2a3a4a5b1b2b3b4b5c1c2c3c4c5 >> >> >> On Fri, Oct 14, 2011 at 6:49 AM, gaurav yadav >> wrote: >> >>> consider following example... >>> suppose initailly we have a1a2a3b1b2b3c1c2c3 >>> >>> then do the following-> >>> a1a2a3 b1b2b3 c1c2c3 (look for b1 in the remaining array and swap with >>> a2 , so in this case swap(a2,b1) ) >>> a1b1a3 a2b2b3 c1c2c3 (similarly swap(a3,c1) ) >>> a1b1c1 a2b2b3 a3c2c3swap(b3,c2) >>> a1b1c1 a2b2c2 a3b2c3 >>> >>> >>> this in inplace >>> >>> (plz correct if im wrong) >>> >>> -- >>> 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. >> > > > > -- > Sunny Aggrawal > B.Tech. V year,CSI > Indian Institute Of Technology,Roorkee > > -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] Re: Inplace Array Convertion
@Gaurav how will u do for a1a2a3a4a5b1b2b3b4b5c1c2c3c4c5 On Fri, Oct 14, 2011 at 6:49 AM, gaurav yadav wrote: > consider following example... > suppose initailly we have a1a2a3b1b2b3c1c2c3 > > then do the following-> > a1a2a3 b1b2b3 c1c2c3 (look for b1 in the remaining array and swap with > a2 , so in this case swap(a2,b1) ) > a1b1a3 a2b2b3 c1c2c3 (similarly swap(a3,c1) ) > a1b1c1 a2b2b3 a3c2c3swap(b3,c2) > a1b1c1 a2b2c2 a3b2c3 > > > this in inplace > > (plz correct if im wrong) > > -- > 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] Re: Inplace Array Convertion
consider following example... suppose initailly we have a1a2a3b1b2b3c1c2c3 then do the following-> a1a2a3 b1b2b3 c1c2c3 (look for b1 in the remaining array and swap with a2 , so in this case swap(a2,b1) ) a1b1a3 a2b2b3 c1c2c3 (similarly swap(a3,c1) ) a1b1c1 a2b2b3 a3c2c3swap(b3,c2) a1b1c1 a2b2c2 a3b2c3 this in inplace (plz correct if im wrong) -- 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] Re: Inplace Array Convertion
@Utkarsh As efficient as possible.. On Fri, Oct 14, 2011 at 6:25 AM, UTKARSH SRIVASTAV wrote: > > > @siddharth what is the complexity? > > -- > *UTKARSH SRIVASTAV > CSE-3 > B-Tech 3rd Year > @MNNIT ALLAHABAD* > > > -- > 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] Re: Inplace Array Convertion
@siddharth what is the complexity? -- *UTKARSH SRIVASTAV CSE-3 B-Tech 3rd Year @MNNIT ALLAHABAD* -- 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.
