perfect answer
On Fri, Feb 21, 2014 at 12:40 AM, kumar raja <rajkumar.cs...@gmail.com>wrote:
> Thanks for the solution. The idea worked for me.
>
>
> On 21 February 2014 01:58, Shashwat Anand <m...@shashwat.me> 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 <rajkumar.cs...@gmail.com>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 algogeeks+unsubscr...@googlegroups.com.
>>>
>>
>> --
>> 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 algogeeks+unsubscr...@googlegroups.com.
>>
>
> --
> 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 algogeeks+unsubscr...@googlegroups.com.
>
--
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 algogeeks+unsubscr...@googlegroups.com.
