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].
