Scrambled Words Loop

  • Thread starter Thread starter OpticTygre
  • Start date Start date
O

OpticTygre

I need to write a loop that prints all the combination possibilities of a
character array. Basically, taking a scrambled word, or a regular word, and
printing out all the combinations. The letters in the word will only be
used once. It sounds easy, but for some reason, I can't get the logic
straight in my head. The formula is as follows:

If n = the number or letters in the word, the C = the number of
combinations, so:

C = (n)(n - 1)(n - 2)....(n - (n - 1))

Or

C = (n)(n - 1)(n - 2)...(1)

I'm totally screwed up on the logic behind writing a loop (or nested loop)
that would take care of this. Any help is appreciated.
 
Let's make this even harder for all you hardcore guys. The formula below
only works when each letter is distinct. It will not work if there are
duplicate letters. For example:

There are 24 different combinations for ABCD.

However, if I have AABB, then there are quite a few less:

AABB
ABAB
ABBA
BBAA
BABA
BAAB

So, the problem now becomes, how do I cycle through loops and print out all
DISTINCT possible combinations?
 
Hi, here's a little code that I put together, it seems to work fairly well.
I just used a hashtable to remove duplicates: I'm new to VB.NET, so there
is probably some more efficient way to do this. (I didn't comment any of
the code, but I used descriptive variable names, so it should be easy enough
to read.




Imports System.Collections.Hashtable

Public Class Form1
Inherits System.Windows.Forms.Form

Private mScrambledWords As Hashtable = New Hashtable

Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As
System.EventArgs) Handles MyBase.Load
Dim scrambledword As String
Dim i As Long
Dim currentWord As String
Dim currentEntry As DictionaryEntry
Dim oEnum As IEnumerator
scrambledword = "ABCDEFF"
ScrambleWord("", scrambledword)

oEnum = mScrambledWords.GetEnumerator()

'Write out the words
Debug.WriteLine(mScrambledWords.Count & " Unique Words Found.")
Me.Text = mScrambledWords.Count & " Unique Words Found."
Do Until oEnum.MoveNext = False
currentEntry = oEnum.Current
currentWord = currentEntry.Value
Debug.WriteLine(currentWord)
Loop
End Sub

Private Sub ScrambleWord(ByVal baseLetters As String, ByVal
ScrambledLetters As String)
Dim c As String
Dim subScrambledLetters As String
Dim i As Integer
For i = 1 To Len(ScrambledLetters)
'take the current letter in position 1, and then scramble the
remaining letters
c = Mid(ScrambledLetters, i, 1)
subScrambledLetters = excludeLetter(ScrambledLetters, i)
ScrambleWord(baseLetters & c, subScrambledLetters)
If Len(subScrambledLetters) = 0 Then
addWordToHash(baseLetters & c)
End If
Next
End Sub

Private Sub addWordToHash(ByVal word As String)
Try
mScrambledWords.Add(word, word)
Catch ex As Exception
'Debug.WriteLine("Duplicate Word Found: " & word)
End Try
End Sub

Private Function excludeLetter(ByVal sString As String, ByVal
letterIndex As Integer) As String
If Len(sString) <= 1 Then Exit Function
excludeLetter = sString.Remove(letterIndex - 1, 1)
End Function

End Class
 
To actually calculate C (which I don't think that is what you're
looking for) you could use a recursive function (untested):

Public Function Calc(n as integer) As Integer
If n > 1 Then
Return Calc(n-1)
Else
Return 1
Endif
End Function

Perhaps a different recursive function might help you in getting the
possible combinations of the word. Here is a link that may be useful
to you:

http://mathforum.org/library/drmath/view/60844.html
 
Hi Chris,

Actually, calculating C is useful, however, the below function only works if
all the letters are different.

'ABCD' has 24 solutions: n! = n(n-1)(n-2)(n-3) = 4(3)(2)(1) = 24

But 'AABB' only has 6 distinct solutions:

AABB
ABAB
ABBA
BBAA
BABA
BAAB

So after lots of math toiling, I came up with the following:

If 'a' represents the count of the letter 'A', and 'b' represents the count
of the letter 'B' and so on, then:

(a + b + c.....)! / (a! * b! * c!....)

Or, more simply

n! / (a! * b! * c!...)

So in the case of 'AABB':

C = (2 + 2)! / (2! * 2!)
C = 4! / 4
C = 24 / 4
C = 6

This formula should work for finding distinct combinations, whether or not
there are duplicate letters.

-Jason
 
Back
Top