[algogeeks] Permuations with stack constraints
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.
Re: [algogeeks] Permuations with stack constraints
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.comwrote:
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.
Re: [algogeeks] Permuations with stack constraints
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.comwrote:
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.
