perfect answer
On Fri, Feb 21, 2014 at 12:40 AM, kumar raja <[email protected]>wrote: > Thanks for the solution. The idea worked for me. > > > On 21 February 2014 01:58, Shashwat Anand <[email protected]> wrote: > >> Think in binaries. >> '1' = push, '0' = pop. >> So a sequence of operations will consist of 0's and 1s. >> >> Say N = length of set. >> >> Property 1: count of 0 = count of 1 = N. >> There will be N push and N pop. >> Property 2: At any point count of 1s >= count of 0s. >> 1100 is valid. [2 push, 2 pop.] >> 1001 is invalid. [1 push, 2 pop] At index 3, number of 0s increased >> that of 1s. >> Hence invalid. >> >> Now just simulate the process by generating valid binaries. >> Time complexity: O (N * (2 ^ N)), Space complexity: O (N) >> >> Code follows, >> >> >> int >> main () { >> >> string s = "abc"; >> int N = s.size (); >> for (int mask = 0; mask < (1 << (2 * N)); mask++) { >> bool ok = true; >> if (__builtin_popcount (mask) != N) continue; >> for (int i = 0, x = mask, c0 = 0, c1 = 0; i < 2 * N; i++, x /= 2) >> { >> (x & 1) ? c1++ : c0++; >> ok &= (c0 <= c1); >> } >> if (! ok) continue; // Invalid mask. >> stack <char> st; >> string t = ""; >> for (int i = 0, x = mask, idx = 0; i < 2 * N; i++, x /= 2) >> if (x & 1) >> st.push (s [idx++]); >> else >> t += st.top (), st.pop (); >> >> printf ("%s\n", t.c_str ()); >> } >> >> return 0; >> } >> >> For s = "ab", >> >> ba >> ab >> >> For s = "abc", >> >> cba >> bca >> acb >> bac >> abc >> >> For s = "abcd", >> >> dcba >> cdba >> bdca >> adcb >> cbda >> bcda >> acdb >> badc >> abdc >> cbad >> bcad >> acbd >> bacd >> abcd >> >> >> Alternatively, you can simply simulate the whole process and do a >> validity >> check after generation of string. The check being, stack should be empty >> and at any point during simulation, you should not try to pop from empty >> stack. >> >> On Thu, Feb 20, 2014 at 11:57 PM, kumar raja <[email protected]>wrote: >> >>> Hi all, >>> >>> Here is a permuatation related question. >>> >>> Suppose the set is {a,b,c}; >>> >>> At a given point of time either u can push an >>> elemnt on to the stack or pop of the element. >>> While pushing the elements u have to follow the >>> order a,b,c as given in the set. >>> >>> When u pop the element u will print it to the >>> output array. >>> >>> one possible sequence of operations is >>> >>> push(a),push(b),pop(),push(c),pop(),pop() >>> >>> The permuation obtained by above combination is >>> >>> {b,c,a}. >>> >>> But out of 6! permuations possible one invalid >>> permutation is {c,a,b} (guess how?) >>> >>> So how to print all valid permuations with the >>> above constaraints? >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to [email protected]. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
