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?

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" <EMAIL REMOVED> wrote in message
news:EMAIL REMOVED om...
> 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?

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" <EMAIL REMOVED> wrote in message
news:EMAIL REMOVED om...
> 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?

"Edgar" <EMAIL REMOVED> wrote in message <news:EMAIL REMOVED. 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 ***ignment 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!

"Joe "Nuke Me Xemu" Foster" <EMAIL REMOVED> wrote in message
news:EMAIL REMOVED...
> "Edgar" <EMAIL REMOVED> wrote in message
<news:EMAIL REMOVED. 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 ***ignment to be sure...

Nah, not homework, it's gunna be a painfully slow brute force
p***word 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

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, ***ign 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"
<EMAIL REMOVED> wrote:

>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:
>abcd abdc acbd acdb adbc adcb bacd badc bcad bcda bdac bdca cabd cadb cbad
>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, EMAIL REMOVED (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?

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 ***ignment but I'm just curious to
see if there is something like this outthere. I am sure there is...

"Edgar" <EMAIL REMOVED> 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 ***ignment 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! =-----

"Larry Serflaten" <EMAIL REMOVED> wrote in message
news:EMAIL REMOVED...

> 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

"Edgar" <EMAIL REMOVED> wrote in message <news:EMAIL REMOVED 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 ***ignment 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!