3 Replies - 423 Views - Last Post: 06 November 2012 - 10:01 AM Rate Topic: -----

#1 andre1011  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 87
  • Joined: 12-January 11

Recursive Algorithms for strings

Posted 05 November 2012 - 05:21 PM

Hello everyone, I am looking for an algorithm to find recurcive permutations of a string. Could someone point me

in the right direction? For example I have a link list of strings:

C A T

the number of permutations is 6 (3! = 3x2x1) so the different arrangements of letters would go like this

C A T

A C T

A T C

T A C

T C A

C T A

If I have the algorithm I can do the rest myself. This is what I have tried so far

void permute::permutation(int n)
{
 node *rightNeighbor;
 node *nextRightNeighbor;
 node *previousNeighbor;

 //cout<<" numberOfNodes "<<numberOfNodes<<" n = "<<n<<endl<<endl;
 if( n == numberOfNodes )
 {
   return;
 }
 else
 {
    if(n == 1)
    {
      anchor = firstNode; /* first letter = first node (c) is the anchor */
    }

    rightNeighbor = anchor->Link();
    nextRightNeighbor = rightNeighbor->Link();
    if( nextRightNeighbor != NULL)
    {
      nextRightNeighbor = rightNeighbor->Link();
    }
    else
    {
      nextRightNeighbor = NULL;
    }
 
    previousNeighbor = rightNeighbor;
    anchor->set_link( nextRightNeighbor );
    rightNeighbor->set_link( anchor );
    firstNode = rightNeighbor;
    rightNeighbor = anchor->Link();
	if(rightNeighbor->Link() == NULL)
	{
      nextRightNeighbor = NULL;
	}
    permutation(n + 1);
 }
 printList();

}/* end permutation */



Is This A Good Question/Topic? 0
  • +

Replies To: Recursive Algorithms for strings

#2 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3116
  • View blog
  • Posts: 19,153
  • Joined: 14-September 07

Re: Recursive Algorithms for strings

Posted 05 November 2012 - 05:29 PM

Here's a snippet of mine that does recursive string permutation.
Was This Post Helpful? 0
  • +
  • -

#3 andre1011  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 87
  • Joined: 12-January 11

Re: Recursive Algorithms for strings

Posted 06 November 2012 - 08:47 AM

I understand what you did but I need to do the same thing with a link list of strings
Was This Post Helpful? 0
  • +
  • -

#4 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3650
  • View blog
  • Posts: 11,420
  • Joined: 05-May 12

Re: Recursive Algorithms for strings

Posted 06 November 2012 - 10:01 AM

If you understand the code snippet, then you should know that the same concepts apply with a linked list. The swapping was easier to do with an array, but the same thing can be done with a linked list.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1