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.
