Page 1 of 1
Iterive Permutation Method Woes
Posted: 30 Jul 2009, 09:35
by DarkRanger
Hi,
It's me again!!
Can someone please help me with my C++ code?
I need to write a permutation method which is iterative. Now, I am getting some output, but it is repeating a bit. Could someone please tell me where I am going wrong?
The permutation Method:
Code: Select all
void permuteIterate(string* c,stack<string>* s)
{
int length = c->length();
for (int i = 0; i < length; i++)
{
for (int k = 0; k < length; k++)
{
if (k != i)
{
swapChars(c,i,k);
s->push(*c);
}
}
}
}
swapChars:
Code: Select all
void swapChars(string* s, int j, int i)
{
char tmp = (*s)[i];
(*s)[i] = (*s)[j];
(*s)[j] = tmp;
}
Output
Code: Select all
Enter String:
abc
The iterative version returns:
cab
cba
abc
acb
cab
bac
it repeats cab... WHY!!
Thanks for the help!
Re: Iterive Permutation Method Woes
Posted: 30 Jul 2009, 09:46
by RuadRauFlessa
Good question but the true question is actually why is it not returning bac first
c=abc
i=0
k=0
so swap 0 and 0 but it should not as it is redundant
c=abc
i=0
k=1
so swap 0 and 1 cab
[0] = a
[1] = b
c should be bac not cab
also I take it that the idea is to get all the different combinations of the char literals within the string?
Re: Iterive Permutation Method Woes
Posted: 30 Jul 2009, 09:57
by Monty
Try doing the testing with 4 or 5 characters. I remember (trying to) do something like this, and for 3 characters it worked, but above 3 i always got repeats
Re: Iterive Permutation Method Woes
Posted: 30 Jul 2009, 10:50
by SykomantiS
I'm not exactly sure, but it looks to me like you are swapping three letters at a time, instead of two- If I read that correctly you are using a stack; and popping everything out of the stack.
It's been quite a while since I've worked with stacks, and they give me headaches anyway.
But that's my 2c.
Re: Iterive Permutation Method Woes
Posted: 30 Jul 2009, 11:24
by Moses
The algorithm is flawed, you need to rethink it.
when i = 0 and k = 2, c = 'bac', so after the swap c = 'cab'
then,
when i = 1 and k = 2, c = 'cba', so after the swap c = 'cab' again
furthermore, your flawed algorithm never generates 'bca'.
Re: Iterive Permutation Method Woes
Posted: 30 Jul 2009, 11:34
by DarkRanger
okay... But I don't know another way...
shucks... I'm sinking, I'm sinking.
Re: Iterive Permutation Method Woes
Posted: 30 Jul 2009, 12:16
by RuadRauFlessa