Author Topic: Permutation Algorithm in Visual C++  (Read 1059 times)

kathir

  • Administrator
  • Sr. Member
  • *****
  • Posts: 283
Permutation Algorithm in Visual C++
« on: June 08, 2011, 04:15:20 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 <tchar.h>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <iostream>

void sortchar(char *buffer, int len)
{
    for(int i = 1; i < len; i++)
    {
        for(int 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;
            }
        }
    }
}

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


int _tmain(int argc, _TCHAR* argv[])
{
    char buf[32];

    std::cout << "Enter a string to find permutation:";
    std::cin >> buf;
    // sortchar(buf, strlen(buf)); // use it only if you require

    int count = 0;
    while(1)
    {
        std::cout << buf << "\n";
        count++;
        bool bRetVal = NextPermuation(buf, strlen(buf));
        if(bRetVal == false)
            break;
    }

    std::cout << "\n\nCount: " << count << "\n";
    std::cout << "\n\n";
    return 0;

}

« Last Edit: June 14, 2011, 03:44:52 pm by kathir »

 


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