Listing 1 String Combination Demo

Imports System
Imports StringCombinationsLib

Module Program

  Sub Main()
    Try
      Console.WriteLine(Environment.NewLine() & "Begin string combination demo" & Environment.NewLine())
      Dim animals As String() = New String() {"ant", "bat", "cow", "dog", "elk"}

      Dim i As Integer
      Console.Write("The original set of string elements is: [ ")
      For i = 0 To animals.Length - 1
        Console.Write(animals(i) & " ")
      Next
      Console.WriteLine("]" & Environment.NewLine())

      Dim n As Integer = animals.Length
      Console.WriteLine("Size original elements (n) = " & n)
      Console.Write("Enter your subset size (k) : ")
      Dim k As Integer
      k = Console.ReadLine()

      Console.WriteLine(Environment.NewLine() & "There are " & StringCombination.Choose(n, k) & " elements ")

      Dim c As StringCombination = New StringCombination(animals, k)

      Console.WriteLine(Environment.NewLine() & "The combination elements are: ")
      i = 0
      While Not c Is Nothing
        Console.WriteLine("[" & i & "] " & c.ToString())
        'Console.ReadLine()
        i = i + 1
        c = c.Successor
      End While
      Console.WriteLine(Environment.NewLine() & "End demo")
      Console.ReadLine()
    Catch ex As Exception
      Console.WriteLine("Fatal error: " + ex.Message)
      Console.ReadLine()
    End Try
  End Sub

End Module


Listing 2 String Combinations Library

Public Class StringCombination
  Private n As Integer = 0
  Private k As Integer = 0
  Private data As String() = Nothing
  Private orig As String() = Nothing

  Public Sub New(ByVal a As String(), ByVal k As Integer)
    If a Is Nothing OrElse k < 1 Then
      Throw New Exception("Invalid argument in StringCombination constructor")
    End If
    Me.n = a.Length
    Me.k = k
    Me.data = New String(k - 1) {}
    Me.orig = New String(n - 1) {}

    Dim i As Integer = 0
    While i < Me.n
      Me.orig(i) = a(i)
      i = i + 1
    End While
    i = 0
    While i < Me.k
      Me.data(i) = a(i)
      i = i + 1
    End While
  End Sub 'New()

  Public Overrides Function ToString() As String
    Dim s As String = "{ "
    Dim i As Integer = 0
    While i < Me.k
      s = s & Me.data(i) & " "
      i = i + 1
    End While
    s = s & "}"
    Return s
  End Function 'ToString()

  Private Function indexOf(ByVal s As String) As Integer
    Dim i As Integer = 0
    While i < Me.n
      If Me.orig(i) = s Then
        Return i
      End If
      i = i + 1
    End While
    Throw New Exception("Could not find the index in indexOf()")
  End Function 'indexOf()

  Public Function Successor() As StringCombination
    If Me.data(0) = Me.orig(Me.n - Me.k) Then
      Return Nothing
    End If

    Dim result As StringCombination = New StringCombination(Me.orig, Me.k)
    Dim i As Integer = 0
    While i < Me.k
      result.data(i) = Me.data(i)
      i = i + 1
    End While

    Dim x As Integer = Me.k - 1
    While x > 0 AndAlso indexOf(result.data(x)) = Me.n - Me.k + x
      'Console.WriteLine("So i am in loop")
      x = x - 1
    End While

    Dim olds As String = result.data(x)
    Dim news As String = Me.orig(indexOf(olds) + 1)
    result.data(x) = news
    'Console.WriteLine("Replacing " & olds & " with " & news)

    Dim j As Integer = x
    While j < Me.k - 1
      Dim replacement As String = Me.orig(indexOf(result.data(j)) + 1)
      result.data(j + 1) = replacement
      j = j + 1
    End While
    Return result
  End Function 'Successor()

  Public Shared Function Choose(ByVal n As Integer, ByVal k As Integer) As Long
    If n <= 0 OrElse k <= 0 Then
    Throw New Exception("Negative argument in Choose")
  End If

  If n < k Then
    Return 0
  End If
  If n = k Then
    Return 1
  End If

  Dim diff As Integer
  Dim newk As Integer
  If k < n - k Then
    diff = n - k
    newk = k
  Else
    diff = k
    newk = n - k
  End If

  Dim answer As Long = diff + 1
  Dim i As Integer = 2
  While i <= newk
    answer = (answer * (diff + i)) / i
    i = i + 1
  End While
  Return answer

  End Function 'Choose()

End Class 'StringCombination


Listing 3

Public Class StringCombination
  Private n As Integer = 0
  Private k As Integer = 0
  Private data As String() = Nothing
  Private orig As String() = Nothing

  Public Sub New(ByVal a As String(), ByVal k As Integer)
    'implementation here
  End Sub 'New()

  Private Function indexOf(ByVal s As String) As Integer
    'implementation here 
  End Function 'indexOf()

  Public Overrides Function ToString() As String
    'implementation here 
  End Function 'ToString()

  Public Function Successor() As StringCombination
    'implementation here 
  End Function 'Successor()

  Public Shared Function Choose(ByVal n As Integer, ByVal k As Integer) As Long
    'implementation here 
  End Function 'Choose()

End Class 'StringCombination

Listing 4

Public Function Successor() As StringCombination
  If Me.data(0) = Me.orig(Me.n - Me.k) Then
    Return Nothing
  End If

  Dim result As StringCombination = New StringCombination(Me.orig, Me.k)
  Dim i As Integer = 0
  While i < Me.k
    result.data(i) = Me.data(i)
    i = i + 1
  End While

  Dim x As Integer = Me.k - 1
  While x > 0 AndAlso indexOf(result.data(x)) = Me.n - Me.k + x
    x = x - 1
  End While

  Dim olds As String = result.data(x)
  Dim news As String = Me.orig(indexOf(olds) + 1)
  result.data(x) = news
    
  Dim j As Integer = x
  While j < Me.k - 1
    Dim replacement As String = Me.orig(indexOf(result.data(j)) + 1)
    result.data(j + 1) = replacement
    j = j + 1
  End While
  Return result
End Function 'Successor()


Listing 5

Public Shared Function Choose(ByVal n As Integer, ByVal k As Integer) As Long
  If n <= 0 OrElse k <= 0 Then
    Throw New Exception("Negative argument in Choose")
  End If

  If n < k Then
    Return 0
  End If
  If n = k Then
    Return 1
  End If

  Dim diff As Integer
  Dim newk As Integer
  If k < n - k Then
    diff = n - k
    newk = k
  Else
    diff = k
    newk = n - k
  End If

  Dim answer As Long = diff + 1
  Dim i As Integer = 2
  While i <= newk
    answer = (answer * (diff + i)) / i
    i = i + 1
  End While
  Return answer
End Function 'Choose()