Iterive Permutation Method Woes

Get help on programming - C++, Java, Delphi, etc.
Post Reply
DarkRanger
Registered User
Posts: 8346
Joined: 10 May 2006, 02:00
Processor: Intel i5-3750
Motherboard: Gigabyte
Graphics card: nVidia GTX 550Ti
Memory: 8GB Jetram
Contact:

Iterive Permutation Method Woes

Post by DarkRanger »

Hi,

It's me again!! :P 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!! :cry: :cry:

Thanks for the help!
Image
RuadRauFlessa
Registered User
Posts: 20576
Joined: 19 Sep 2003, 02:00
Location: Bloodbank

Re: Iterive Permutation Method Woes

Post 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?
:rock: :rock: :rock: :rock: :rock: :rock: :rock: :rock: :rock: :rock:
Spoiler (show)
Intel Core i7-2600k @ 3.4GHz
Corsair Vengence 2x4GB DDR3 2000MHz
Thermaltake Toughpower 850W
ASUS nVidia GTX560 1GB
CoolerMaster HAF 932
Monty
Forum Moderator
Posts: 10000
Joined: 05 Feb 2004, 02:00
Processor: Intel i5-4690K @ 4.5GHZ
Motherboard: ASUS Maximus VII Formula
Graphics card: ASUS GTX970 Strix
Memory: 4 x 4GB Corsair Dominators
Location: Messing with your Mind
Contact:

Re: Iterive Permutation Method Woes

Post 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
Art Williams wrote:I'm not telling you it is going to be easy, I'm telling you it's going to be worth it.
SykomantiS
Registered User
Posts: 14085
Joined: 06 Oct 2004, 02:00
Location: Location, Location...
Contact:

Re: Iterive Permutation Method Woes

Post 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.
Moses
Registered User
Posts: 2545
Joined: 21 Jul 2004, 02:00
Location: Location:
Contact:

Re: Iterive Permutation Method Woes

Post 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'.
DarkRanger
Registered User
Posts: 8346
Joined: 10 May 2006, 02:00
Processor: Intel i5-3750
Motherboard: Gigabyte
Graphics card: nVidia GTX 550Ti
Memory: 8GB Jetram
Contact:

Re: Iterive Permutation Method Woes

Post by DarkRanger »

okay... But I don't know another way... :mrgreen:

shucks... I'm sinking, I'm sinking.
Image
RuadRauFlessa
Registered User
Posts: 20576
Joined: 19 Sep 2003, 02:00
Location: Bloodbank

Re: Iterive Permutation Method Woes

Post by RuadRauFlessa »

:rock: :rock: :rock: :rock: :rock: :rock: :rock: :rock: :rock: :rock:
Spoiler (show)
Intel Core i7-2600k @ 3.4GHz
Corsair Vengence 2x4GB DDR3 2000MHz
Thermaltake Toughpower 850W
ASUS nVidia GTX560 1GB
CoolerMaster HAF 932
Post Reply