472,982 Members | 2,270 Online

# VB + Text Manipulation

Has anybody worked on an algorythm to calculate all the possible
letter combinations given a string?

Example:
Given edgar
the program would output
dgare
gared
aredg
redga

etc... and it would do this for all the letters and possible
combinations.

Any ideas?
Jul 17 '05 #1
11 7579
All combinations is one.

Order matters in combinations and permutations. AB and BA is one combination
and two permutations. Consult any basic statistics text.

"Edgar" <mr********@yahoo.com> wrote in message
Has anybody worked on an algorythm to calculate all the possible
letter combinations given a string?

Example:
Given edgar
the program would output
dgare
gared
aredg
redga

etc... and it would do this for all the letters and possible
combinations.

Any ideas?

Jul 17 '05 #2
Are you looking for the one word the combination of letters can make or
are you looking for all possible words?

For edgar (5 letters) the possible combinations is 1x2x3x4x5 = 120

Jim
"Edgar" <mr********@yahoo.com> wrote in message
Has anybody worked on an algorythm to calculate all the possible
letter combinations given a string?

Example:
Given edgar
the program would output
dgare
gared
aredg
redga

etc... and it would do this for all the letters and possible
combinations.

Any ideas?

Jul 17 '05 #3
"Edgar" <mr********@yahoo.com> wrote in message <news:14**************************@posting.google. com>...
Has anybody worked on an algorythm to calculate all the possible
letter combinations given a string?

Example:
Given edgar
the program would output
dgare
gared
aredg
redga

etc... and it would do this for all the letters and possible
combinations.

Any ideas?

This matches your example, but we'll need to see your actual
homework assignment to be sure...

for i = 2 to len(s)
debug.print mid\$(s & s, i, len(s))
next

--
Joe Foster <mailto:jlfoster%40znet.com> "Regged" again? <http://www.xenu.net/>
WARNING: I cannot be held responsible for the above They're coming to
because my cats have apparently learned to type. take me away, ha ha!
Jul 17 '05 #4

"Joe "Nuke Me Xemu" Foster" <jo*@bftsi0.UUCP> wrote in message
news:10***************@news-1.nethere.net...
"Edgar" <mr********@yahoo.com> wrote in message <news:14**************************@posting.google. com>...
Has anybody worked on an algorythm to calculate all the possible
letter combinations given a string?

Example:
Given edgar
the program would output
dgare
gared
aredg
redga

etc... and it would do this for all the letters and possible
combinations.

Any ideas?

This matches your example, but we'll need to see your actual
homework assignment to be sure...

Nah, not homework, it's gunna be a painfully slow brute force
password hack by the sounds of it.

Or maybe one of those word puzzles where they give
one word and you have to find all the other words that can
be made up using the letters of the first. Shuffle the letters and
spell check would find all the valid words.

then again.... maybe not..
GtG
Jul 17 '05 #5
This was posted not too long ago on this group:
One way of generating all anagrams for a word systematically is to use
numbers of a base correspondiing to the number of characters in the
word. Then, assign a "digit" to each letter of the word. If you have
a 4-letter word you will use a base 4 counter which will have a range
from 0000 to 3333. Enumerate all members of the range: 0000, 0001,
0002, 0003, 0010, 0011, 0012, 0013, 0020, etc. Select only those
members which have all different digits. E.g, 0123 would be the
first one, then 0132, 0213, etc. For each of these selected members,
substitute the letters corresponding to the original word. Thus, for
"abcd", a=0, b=1, c=2, d=3. Taking the first member from our
enumeration with 4 different digits, (0123) becomes (abcd), (0213)
becomes (acbd), etc.

If the original word has non-unique letters, some of your anagrams
will be duplicated. This process is sytematic and complete, but not
very efficient because a lot of the numbers have to be discarded
because they don't have unique digits. Also, as your word length
increases, so does the length of the process. An 8-letter word would
require an 8-digit, base-8 counter.

If you want to find all anagrams of a word in a dictionary, there are
better ways of doing this using word lengths and hash codes based on
letter content.

Good luck,

xyz
==============

On Tue, 30 Sep 2003 23:47:38 GMT, "Eric A. Johnson"
Hi,
Thanks for reading this. How do I list all possible permutations of a
word? I've figured out how to get all the characters in alphabetical order.
I then want to display every possible character permutation in sequence,
like so:
cbda cdab cdba dabc dacb dbac dbca dcab dcba
This is turning out to be much more difficult than I thought it would
be. It seems to be that a recursive function or procedure, possibly using
the length of the string, might be a good idea... but since the number of
permutations is x!, where x is the length of the string, I don't quite know
where to begin. Can anybody give me some hints? Thanks!

Thanks,
Eric A. Johnson

On 1 Dec 2003 11:42:07 -0800, mr********@yahoo.com (Edgar) wrote:
Has anybody worked on an algorythm to calculate all the possible
letter combinations given a string?

Example:
Given edgar
the program would output
dgare
gared
aredg
redga

etc... and it would do this for all the letters and possible
combinations.

Any ideas?

Jul 17 '05 #6
This is more of a scrabble-game type of thing. Where you are given 7
letters and you are supposed to create a word or words with those...

This is actually not a hoomework assignment but I'm just curious to
see if there is something like this outthere. I am sure there is...
Jul 17 '05 #7
"Edgar" <mr********@yahoo.com> wrote in message
This is more of a scrabble-game type of thing. Where you are given 7
letters and you are supposed to create a word or words with those...

This is actually not a hoomework assignment but I'm just curious to
see if there is something like this outthere. I am sure there is...

Yes, here is an interesting algorithm for the permutation problem.
Add a command button, a textbox, and a listbox to a new form
and try out the code below...

Have fun!
LFS
Private Sub Command1_Click()
List1.Clear
Debug.Print GetPermutation(Text1.Text)
End Sub
Private Function GetPermutation(Y As String, _
Optional X As String = "") As Long
Dim idx As Long, pos As Long
Static cnt As Long
' The source of this algorithm is unknown

' Init counter
If Len(X) = 0 Then cnt = 0

pos = Len(Y)
If pos < 2 Then
' Put it somewhere
List1.AddItem X & Y
cnt = cnt + 1
Else
' The switcharoo....
For idx = 1 To pos
GetPermutation Left\$(Y, idx - 1) + Right\$(Y, pos - idx), _
X + Mid\$(Y, idx, 1)
Next
End If
GetPermutation = cnt
End Function

-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----== Over 100,000 Newsgroups - 19 Different Servers! =-----
Jul 17 '05 #8
"Larry Serflaten" <Ab***@SpamBusters.com> wrote in message
news:3f********@corp.newsgroups.com...
Yes, here is an interesting algorithm for the permutation
problem . . . . .

The main problem with that code is that it returns every possible
permutation, including many, many duplicates when a particular character
occurs more than once in the string. For example, running it on the string
"aaaaaaa" will return 5040 possible "words", whereas there is in fact only
one "word" that can be made from those seven characters!

It is possible, of course, to write code that produces all of the possible
"words" without producing any duplicates, but I personally believe that you
should take a completely different approach. For example, in a game of
Scrabble you would probably want to work with words of up to eight or maybe
nine characters, and if each character is different this would produce a
list of 362,880 words. This can exceed the total number of words in the
dictionary, each of which would have to be tested against it. This would be
slow, even using a binary search. In fact, if you have a dictionary
containing (say) 100,000 words and you have nine characters to look at then
even if all those characters are different they would between them
constitute only about a third of the alphabet. This means that you would
really have to look at an absolute maximum of only 30,000 words if you
instead checked the characters (one at a time) against words in the
dictionary.

So, rather than produce a complete list of all of the possible arrangements
of letters it would be better to . . . bloody hell . . . I'm too drunk to
do it at the moment . . . perhaps someone else can come up with a suitable
method :-)

Mike

Jul 17 '05 #9
"Edgar" <mr********@yahoo.com> wrote in message <news:14*************************@posting.google.c om>...
This is more of a scrabble-game type of thing. Where you are given 7
letters and you are supposed to create a word or words with those...

This is actually not a hoomework assignment but I'm just curious to
see if there is something like this outthere. I am sure there is...

Are word-lists for games like Scrabble online anywhere? I'd start
with that instead of trying to generate all possible permutations
of seven letters. Instead, count the occurrences of each letter
in your 7-character input, then fetch words from your dictionary
that have equal or lesser counts of each letter.

Private Type Word
Word As String
Counts(vbKeyA To vbKeyZ) As Long
End Type

Public Sub Anagram(ByVal String1 As String)
Dim Words(1 To 4) As Word, Used() As Long
Words(1) = Anagram0("A")
Words(2) = Anagram0("ABA")
Words(3) = Anagram0("B")
Words(4) = Anagram0("BAB")
ReDim Used(1 To Len(String1))
Anagram1 Anagram0(String1), Words, Used, 0
End Sub

Private Function Anagram0(String1 As String) As Word
If Len(String1) = 0 Or String1 Like "*[!A-Za-z]*" Then Error 5
Dim i As Long, j As Integer
Anagram0.Word = UCase\$(String1)
For i = 1 To Len(Anagram0.Word)
j = Asc(Mid\$(Anagram0.Word, i, 1))
Anagram0.Counts(j) = Anagram0.Counts(j) + 1
Next
End Function

Private Sub Anagram1(Match As Word, Words() As Word, Used() As Long, ByVal Max As Long)
Dim i As Long, j As Integer, Temp As Word, Remain As Long, Start As Long
If Max = 0 Then Start = LBound(Words) Else Start = Used(Max)
For i = Start To UBound(Words)
Temp = Match
Remain = 0
For j = vbKeyA To vbKeyZ
If Words(i).Counts(j) = 0 Then
' skip it
ElseIf Words(i).Counts(j) > Temp.Counts(j) Then
Remain = -1
Exit For
Else
Temp.Counts(j) = Temp.Counts(j) - Words(i).Counts(j)
End If
Remain = Remain + Temp.Counts(j)
Next
If Remain = 0 Then
For j = 1 To Max
Debug.Print Words(Used(j)).Word; " ";
Next
Debug.Print Words(i).Word
ElseIf Remain > 0 Then
Used(Max + 1) = i
Anagram1 Temp, Words, Used, Max + 1
End If
Next
End Sub

In a "real" application, the words and their counts should be kept
in an indexed database table so you can query the table instead of
looping through the entire word list, and the output will have to
go somewhere other than just the Immediate window.

--
Joe Foster <mailto:jlfoster%40znet.com> "Regged" again? <http://www.xenu.net/>
WARNING: I cannot be held responsible for the above They're coming to
because my cats have apparently learned to type. take me away, ha ha!
Jul 17 '05 #10
The possible combinations are 1.

My first impression was that this was a school lesson in fully understanding
the problem before starting to write code.

"Falsehat" <ji****@sympatico.ca> wrote in message
news:Zv******************@news20.bellglobal.com...
Are you looking for the one word the combination of letters can make or
are you looking for all possible words?

For edgar (5 letters) the possible combinations is 1x2x3x4x5 = 120

Jim

Jul 17 '05 #11
>> This is more of a scrabble-game type of thing. Where you are given 7
letters and you are supposed to create a word or words with those...
Yes, here is an interesting algorithm for the permutation problem.
Add a command button, a textbox, and a listbox to a new form
and try out the code below...
Private Sub Command1_Click()
List1.Clear
Debug.Print GetPermutation(Text1.Text)
End Sub

Private Function GetPermutation(Y As String, _
Optional X As String = "") As Long
Dim idx As Long, pos As Long
Static cnt As Long
' The source of this algorithm is unknown

' Init counter
If Len(X) = 0 Then cnt = 0

pos = Len(Y)
If pos < 2 Then
' Put it somewhere
List1.AddItem X & Y
cnt = cnt + 1
Else
' The switcharoo....
For idx = 1 To pos
GetPermutation Left\$(Y, idx - 1) + Right\$(Y, pos - idx), _
X + Mid\$(Y, idx, 1)
Next
End If
GetPermutation = cnt
End Function

As you noted, this generates duplicates, but that could be fixed by
checking your output list for an existing same word and not adding a
second one.
This would consume time on a slow computer, but if you want the answer
badly enough just take a coffee break. Or you could display each new word
actually added to the list, and/or a loop count, as a progress display to
amuse yourself while you wait.

Jul 17 '05 #12

This thread has been closed and replies have been disabled. Please start a new discussion.