Web developers notes,programming tutorials.

Environment: C++, any version that supports namespaces

Introduction

This article explains the technique of finding permutations in a simple and fast manner. It also provides the source code for the same.

Explanation

For a given string of length N, there are actually N! Permutations. The technique we apply here is to find the unique of those permutations and display them.

Let’s take this string: 123. If we rotate this string in a circular manner, we get 231 and 312. The point here is, if we find 1 string of the N! Permutations, we can produce N permutations by rotating it circularly. This reduces the time, which is proportional to N. The greater the value of N, the more the algorithm is optimized.

In short, the algorithm finds a number and rotates the number circularly N times to get N numbers.

Lets apply the algorithm. Lets take string {12} of length 2 (N=2). The unique pattern is 12 and if we rotate we get 21.

Let’s take the string {123} of length 3 (N=3). The unique patterns are as follows:

1(23): 123 is unique pattern resulting in (123)
1(32): Rotate the pattern (23) u get another pattern (32) resulting in a pattern (132)
(231): By rotating the pattern (123)
(312): By rotating the pattern (123)
(321): By rotating the pattern (132)
(213): By rotating the pattern (132)

The output patterns are:

If we apply the same algorithm for the string {1234} of length 4 (N=4), the patterns are as below:

Comparison

The traditional algorithm goes and finds all the permutations where, as in this algorithm, we find only the unique permutation and produce the other permutations by rotating the original permutation in a circular manner.

Conclusion

The algorithm finds only the unique numbers and finds the other (N) permutations by rotating the original permutation circularly. Hence, it increases the performance.

ActiveX Data Objects (ADO) enables you to write a client application to access and manipulate data in a database server through a provider.
ADO’s primary benefits are ease of use, high speed, low memory overhead, and a small disk footprint.
This sample project is for ADODB, an implementation of ADO optimized for use with Microsoft OLE DB providers, including the Microsoft ODBC provider for OLE DB.
Using this we can execute stored procedure, pass arguments and retrieve value. To use this sample you will have to create the two stored procedures mentioned below.
For using this project you need MFC 5.0 OR above + ADO in your machine.

{
CString strTmp;

CString m_sdatasource; // Data source name
CString m_sUserID; // User Id
CString m_sPassword; // Password

// GET the above values from the user
//Without creating Datasource we can use database by the following code
/* strTmp.Format( “driver={sql server};”
“server=%s;”
“Database=%s;”"UID=%s;”"PWD=%s;”,
m_server,m_sdatabase,m_sUserID,m_sPassword );*/

strTmp.Format( “dsn=%s;”"UID=%s;”"PWD=%s;”,m_sdatasource,m_sUserID,m_sPassword );
_bstr_t bstrSQLServerConnect;
_bstr_t bstrProc =( L”sp_StartByteImport” );; //Stored procedure name
_variant_t Final;
bstrSQLServerConnect = (LPCTSTR) strTmp;
m_status=”Empty File”;
_ConnectionPtr Conn1; // connection object pointer
_CommandPtr Cmd1; // command object pointer
_RecordsetPtr Rs1; // recordset object pointer
bool bvalid = false;
try
{
Conn1.CreateInstance( __uuidof( Connection ) ); // Instantiating connection object
Conn1->ConnectionString = bstrSQLServerConnect; // giving the sqlconnection
Conn1->Open( bstrEmpty, bstrEmpty, bstrEmpty ); // open the connection object
Cmd1.CreateInstance( __uuidof( Command ) ); // creating command object
Cmd1->ActiveConnection = Conn1; // giving the connection handle
Cmd1->CommandText = _bstr_t( bstrProc ); // passing the stored procedue
Cmd1->CommandType = adCmdStoredProc; // type
Cmd1->Parameters->Refresh(); // passing string value as argument to stored procedure
Cmd1->Parameters->Item[ _variant_t( (long) 1 ) ]->Value = _variant_t( (LPCTSTR)m_sfilename );
Rs1 = Cmd1->Execute( &vtEmpty, &vtEmpty2, adCmdUnknown ); // executing the stored procedure and storing the recordset value
bvalid = true;
Final = Rs1->Fields->GetItem( _variant_t( 0L ) )->Value; // getting the first column value of the result row
strTmp.Format( “%s”, CrackStrVariant( Final) ); // to see the value
// put your code to see all column values
}
catch( CException *e ) // trapping all error messages
{
TCHAR szCause[255];
e->GetErrorMessage(szCause, 255);
m_status=szCause;
}
catch( _com_error &e )
{
m_status=e.ErrorMessage( );
}
catch(…)
{
m_status=”Error while executing the Import”;

}
//we need to create the stored procedures below before running the application
//CREATE PROCEDURE sp_AddAccountingInfo @nfinal int, @pcDate datetime,
//@pcURL varchar (250), @pcTop varchar (250),
//@pcQueryString varchar (250), @pcBytes int, @pcRequests int AS
/*
Do your operation here
*/
//CREATE PROCEDURE sp_AddAccountingInfo
//@nfinal int,
//@pcDate datetime,
//@pcURL varchar (250),
//@pcTop varchar (250),
//@pcQueryString varchar (250),
//@pcBytes int,
//@pcRequests int
//AS
/*
Put your code here
*/
}

About binary trees

Say you have a list or array holding N numbers of elements, and want to search for a specific element. You then have to go through (aka traverse) each element one by one until you find it (or find out that it is not in the list).

The worst case (if the element is last in the list, or isn’t there at all) you’d have to make N comparisons, which can be quite a treat if the list/array is VeryVeryBig(tm).

By having the elements stored in a tree rather a list you get some key benefits:

• Faster search (don’t have to compare with all elements)
• Elements are automatically sorted as they are added

How does it work then

In a linked list you have a line of elements, each elements pointing to the next:
Fig. 1. A linked list

In a binary tree, each element instead point to two other elements, one “down to the left” (left child) and one “down to the right” (right child).
The left child’s key value is less than its parent’s, and the right child’s key value is greater than or equal than its parent’s:

Fig. 2. A binary tree

Thanks to this, can you fairly easy decide where to search (and where to not search) for a particular element.
If the current node doesn’t match the search criteria, query the left or the right child, depending of wheter the search criteria is < or >= than current node’s key value.

Sorting

Since all elements are stored according to their key values, you can easily retrieve them in an ordered (or reversed) manner. Oh, and when working with trees, you really see the benefits of using recursion…Example of printing the elements in order:

  PrintElement(pTopMostElement)
.
.
void PrintElement(TreeElement* pElement)
{
if (pElement)
{
PrintElement(pElement->LeftChild)
pElement->PrintMe()
PrintElement(pElement->RightChild)
}
}

Example of printing the elements in reversed order:

  PrintElementReversed(pTopMostElement)
.
.
void PrintElementReversed(TreeElement* pElement)
{
if (pElement)
{
PrintElementReversed(pElement->RightChild)
pElement->PrintMe()
PrintElementReversed(pElement->LeftChild)
}
}