Author Topic: Permutation Algorithm in C  (Read 1091 times)

kathir

  • Administrator
  • Sr. Member
  • *****
  • Posts: 283
Permutation Algorithm in C
« on: June 08, 2011, 04:17:04 am »
I have implemented permutation algorithm on Turbo C, Visual C++, C# and Java.
 
Turbo C/C++ programmers: http://www.softwareandfinance.com/Turbo_CPP/MRP.html
 
Visual C++ programmers: http://www.softwareandfinance.com/Visual_CPP/MRP.html
 
C# programmers: http://www.softwareandfinance.com/CSharp/MRP.html
 
Java programmers: http://www.softwareandfinance.com/Java/MRP.html
 
Make sure you like us on http://facebook.softwareandfinance.com to serve you better.


#include <stdio.h>
#include <string.h>

void sortchar(char *buffer, int len)
{
    int i, j;
    for(i = 1; i < len; i++)
    {
        for(j = 0; j < len - i; j++)
        {
            if(buffer[j] > buffer[j + 1])
            {
                char temp = buffer[j];
                buffer[j] = buffer[j + 1];
                buffer[j + 1] = temp;
            }
        }
    }
}

int NextPermuation(char *p, int len)
{
    int i,j,k;
    int anchor, count;
    char *tempptr;
    char ch, newchar;

    for(k = len - 1; k > 0; k--)
    {
   if(p[k - 1] >= p[k])
       continue;
   else
   {
       if(k <= len - 3)
       {
      newchar = p[k-1];
      anchor = -1;
      for(j = len - 1; j >= k; j--)
      {
          if(newchar < p[j])
          {
         anchor = j;
         break;
          }
      }
      if(anchor == -1)
          return 0;
      ch = p[k-1];
      p[k-1] = p[anchor];
      p[anchor] = ch;
      // sort last remaining chars
      sortchar(p+k,len - k);
      return 1;
       }
       else
       {
      tempptr = &p[len-3];
      count = 3;
      for(i = count - 1; i > 0; i--)
      {
          if(tempptr[i - 1] >= tempptr)
         continue;
          else
          {
         if(i <= count - 2)
         {
             if(tempptr[i+1] > tempptr[i-1])
             {
            ch = tempptr[i+1];
            tempptr[i+1] = tempptr;
            tempptr = tempptr[i-1];
            tempptr[i-1] = ch;
             }
             else
             {
            ch = tempptr[i-1];
            tempptr[i-1] = tempptr;
            tempptr = tempptr[i+1];
            tempptr[i+1] = ch;
             }
         }
         else
         {
             ch = tempptr;
             tempptr = tempptr[i-1];
             tempptr[i-1] = ch;
         }
         return 1;
          }
      }
      return 0;
       }
   }
    }
    return 0;
}

int main(int argc, char* argv[])
{
    char buf[32];
    int ret;
    int count = 0;

    printf("Enter a string to find permutation:");
    scanf("%s", buf);
    //sortchar(buf, strlen(buf));

    while(1)
    {
   printf("%s\n", buf);
   count++;
   ret = NextPermuation(buf, strlen(buf));
   if(ret == 0)
       break;
    }

    printf("\n\nCount: %d\n\n\n", count);
    return 0;
}

 


Disclaimer: This web site is for educational and informational purposes only. Click here to read the Disclaimer.
Content copyright 2010-2014. Kathiresan. All rights reserved.
This page is using SMF version 2.0.1