Monthly Archives: June 2011

HOW TO: Get a list of all permutations of a string

Recently, I was working with my boss to interview new developers and he asked me for a trick on how to analyze the level of skill that a coder had. I applied for a position at a job when I was just starting out as a developer and was asked a very simple question, which turned out to be very difficult to interpret into code. He asked me how would I find every permutation of a string without duplicate values.

It seems very simple, but for a developer to interpret that into code takes some time and understanding of how everything is interpreted in software.

Here is a sample snippet of code to achieve this:

Sub Main()
        Dim strInputString As String = String.Empty
        Dim lstPermutations As List(Of String)
        'Loop until exit character is read
        While strInputString <> "x"
            Console.Write("Please enter a string or x to exit: ")
            strInputString = Console.ReadLine()
            If strInputString = "x" Then
                Continue While
            End If
            'Create a new list and append all possible permutations to it.
            lstPermutations = New List(Of String)
            Append(strInputString, lstPermutations)

            'Sort and display list+stats
            lstPermutations.Sort()
            For Each strPermutation As String In lstPermutations
                Console.WriteLine("Permutation: " + strPermutation)
            Next
            Console.WriteLine("Total: " + lstPermutations.Count.ToString)
            Console.WriteLine("")
        End While
    End Sub

    Public Sub Append(ByVal pString As String, ByRef pList As List(Of String))
        Dim strInsertValue As String
        Dim strBase As String
        Dim strComposed As String
        'Add the base string to the list if it doesn't exist

        If pList.Contains(pString) = False Then
            pList.Add(pString)
        End If
        'Iterate through every possible set of characters
        For intLoop As Integer = 1 To pString.Length - 1
            'we need to slide and call an interative function.
            For intInnerLoop As Integer = 0 To pString.Length - intLoop
                'Get a base insert value, example (a,ab,abc)
                strInsertValue = pString.Substring(intInnerLoop, intLoop)
                'Remove the base insert value from the string eg (bcd,cd,d)
                strBase = pString.Remove(intInnerLoop, intLoop)
                'insert the value from the string into spot and check
                For intCharLoop As Integer = 0 To strBase.Length - 1
                    strComposed = strBase.Insert(intCharLoop, strInsertValue)
                    If pList.Contains(strComposed) = False Then
                        pList.Add(strComposed)
                        'Call the same function to review any sub-permutations.
                        Append(strComposed, pList)
                    End If
                Next
            Next
        Next
End Sub

HOW TO: Sort an array using an IComparable

A common problem in .NET is being able to present your data to a user in a way that makes sense to them. One such way is to provide them a list of information that is sorted in a way that is proper to their function. For example, if you were showing a list of transactions, you may want to sort in a descending order based on their date to show the last transaction that happened.

This can be accomplished using an array and/or list and the IComparable. In the object which you are sorting, implement the interface and use any rules necessary to compare two objects. In our previous example, we discussed a transaction. Here is a transaction object which sorts based on the transaction date:

Public Class Transaction
   Implements IComparable
   Private m_TransactionAmount As Decimal
   Private m_TransactionDate As Date
   Public Sub New(ByVal TransactionAmount As Decimal, ByVal TransactionDate As Date)
      m_TransactionAmount = TransactionAmount
      m_TransactionDate = TransactionDate
   End Sub

   Public Function CompareTo(ByVal obj As Object) As Integer Implements System.IComparable.CompareTo
      'implements a icomparer rule to allow for sorting based on transaction date, and then transaction type

      Dim dteValueToCompare As Date
      Dim blnCredit As Boolean
      If TypeOf obj Is Transaction Then
         dteValueToCompare = CType(obj, Transaction).TransactionDate
      Else
         dteValueToCompare = obj
      End If
      Return Date.Compare(TransactionDate, dteValueToCompare)
   End Function
End Class

Now, to sort the transactions, you can use an Array and use the Array.Sort method to sort them by date. You can also use a Array.Reverse to get a reverse sort in case you want them in descending order. Happy coding!

OAuth Usage In Web Design

A feature which DevExpress has recently released into their library is the oAuth integration library. This allows for Facebook, LinkedIn and popular oAuth login methods to connect to your XAF or ASP.NET website. A nice feature of this tool is the automation of the login process, and seemless integration into websites.

This login method is a token based login, which was not a popular method until it was adopted by media giants such as Google and Facebook.There are a lot of good sample websites on how to use oAuth if you were to write your own integration library:

About OAuth
Hueniverse
OAuth By Example
Twitter Developers On OAuth

I would also recommend reading the third part in the DevExpress blog regarding setting up an oAuth website while using their controls. It is a great read, and helps any developer get up and going with this technology in a few simple steps:

DevExpress Using OAuth