|  | Combinations | | |
| | | Guest |  |
|  Posted: Sat Aug 16, 2008 8:54 pm Post subject: Combinations |  |
someone has an idea on how to write a program that takes some letters
and gives all possible words(with sense or without ) that we can make
with these letters? |
| |
| | | Malcolm McLean | |
| | Posted: Sat Aug 16, 2008 8:54 pm Post subject: Re: Combinations | |
<jrdacc.i@gmail.com> wrote in message
| Quote: | someone has an idea on how to write a program that takes some letters
and gives all possible words(with sense or without ) that we can make
with these letters?
Think recursion. Take each letter in turn, and put it to the front of the |
word. The simply repeat making all the word of N-1 letters, until fianlly
with words of one letter you have only one combination.
For extra marks don't treat duplicate letters as different if they are in
the same place.
--
Free games and programming goodies.
LINK |
| |
| | | Andrew Poelstra | |
| | Posted: Sat Aug 16, 2008 8:54 pm Post subject: Re: Combinations | |
On 2008-08-16, jrdacc.i@gmail.com <jrdacc.i@gmail.com> wrote:
| Quote: | someone has an idea on how to write a program that takes some letters
and gives all possible words(with sense or without ) that we can make
with these letters?
|
Assuming you won't have obscenely long inputs, I'd use recursion. To
get more specific help than that, you'll have to ask a more specific
question, or (preferably) post some C code that doesn't work the way
that you want it to, and the group will offer suggestions.
For a more general (not C-related) discussion on what algorithms you
should use, try posting in comp.programming.
--
Andrew Poelstra apoelstra@wpsoftware.com
To email me, use the above email addresss with .com set to .net |
| |
| | | Eric Sosman | |
| | Posted: Sat Aug 16, 2008 8:54 pm Post subject: Re: Combinations | |
| |  | |
Andrew Poelstra wrote:
| Quote: | On 2008-08-16, jrdacc.i@gmail.com <jrdacc.i@gmail.com> wrote:
someone has an idea on how to write a program that takes some letters
and gives all possible words(with sense or without ) that we can make
with these letters?
Assuming you won't have obscenely long inputs, I'd use recursion. [...]
|
I wonder whether the O.P. means "combinations" as stated
in his subject line, or whether he means "permutations."
Combinations could be generated recursively, but that's
not the method I'd choose. If there are N letters I'd just
count a suitably-sized integer from 0 to (1<<N)-1, associate
each bit of the integer with one of the letters, and use the
bit's value to decide whether its letter is In or Out.
Recursion seems a good choice for permutations, though.
Note that if the inputs are obscenely long the program will
not run to completion anyhow. Permuting the twenty-six upper-
case letters at the rate of one terahertz would take almost
thirteen million years -- perhaps longer, with time out for
patches.
--
Eric Sosman
esosman@ieee-dot-org.invalid |
| |
| | | Richard Heathfield | |
| | Posted: Sun Aug 17, 2008 6:32 am Post subject: Re: Combinations | |
| | | |
jrdacc.i@gmail.com said:
| Quote: | someone has an idea on how to write a program that takes some letters
and gives all possible words(with sense or without ) that we can make
with these letters?
|
I've read all the other responses, and they've acknowledged your "with
sense or without" comment by discussing how to generate all possible
permutations.
At the risk of straying a little from your question, I'd like to discuss
how to generate all the words that /do/ make sense, ignoring the ones that
don't.
For this purpose, we define "makes sense" as "appears in a dictionary".
I would approach this as follows:
1) write a program that takes as input a dictionary, takes each word and
sorts the letters alphabetically, forming a { sorted, unsorted } pair, and
adding this to a tree keyed on 'sorted', where duplicates are dealt with
via a linked list. This whole shebang is then written out as a file
(because it only needs preparing once, or once per dictionary update, but
can be used many times).
2) write a second program that slurps the file in, and then takes as input
the word of which you want to find anagrams. This now becomes a simple
lookup, rather than a combinatorial exercise - and will run very, very
fast.
--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999 |
| |
| | | rio | |
| | Posted: Tue Aug 19, 2008 2:57 am Post subject: Re: Combinations | |
<jrdacc.i@gmail.com> ha scritto nel messaggio
news:8ee9f697-68a3-4bed-b67e-9d789ce12561@y21g2000hsf.googlegroups.com...
| Quote: | someone has an idea on how to write a program that takes some letters
and gives all possible words(with sense or without ) that we can make
with these letters?
|
2!=2
4!=24
5!=120
6!=720
7!=5040
''''
10!=3628800
so for a world of 7 letter you should have 5040 derived world
of 7 letter
for find these have some meaning it is easyer to find it in a
ordered dictionary |
| |
| | | Guest | |
| | Posted: Tue Aug 19, 2008 3:09 pm Post subject: Re: Combinations | |
Richard Heathfield:
| Quote: | I would approach this as follows:
|
I agree with your approach if there's a need of repeated searches,
otherwise a simple linear search in the dictionary for works with the
same signature may suffice.
If the search has to be performed many times then the two-phases
strategy of yours is better. The two phases are totally separated, so
you can even use different languages for them. The first phase then
can be done with a scripting language (like python) in few lines of
code (using a dict (hash) instead of the tree) in few seconds of
runtime.
The second phase can be written in C if necessary, it can use a hash
again (for example using GLib), but in C that may be overkill and just
a binary search among the keys may suffice (the keys are the
signatures, the words with sorted letters).
Bye,
bearophile
(First post of mine on this newsgroup) |
| |
| | | Paul Hsieh | |
| | Posted: Tue Aug 19, 2008 6:20 pm Post subject: Re: Combinations | |
| | | |
On Aug 16, 1:54 pm, jrdac...@gmail.com wrote:
| Quote: | someone has an idea on how to write a program that takes some
letters and gives all possible words(with sense or without ) that
we can make with these letters?
|
For words that make sense I would take the following approach:
For each word in the dictionary compute a letter usage mask;
i.e., one bit per letter in the word case unified, and based with
'a' => 1 << 0. Then for your set of input letters, first compute
its letter mask and scan for the set of words with an exactly
matching letter mask. Then simply check if the letter frequency
count of the word matches that of the input letters and if so,
output it as a matching word.
For words that make no sense you can put the letters into an array,
and do reversible delete_at and insert_at functions (both would swap
with the last element and change the array count by 1) then its just a
matter of a for loop and recursion. You will also want to hand each
recursive function a list node that points back into an auto declared
node that contains the currently selected letter in your for-loop.
This way, when you reach the bottom, it will be easy to display the
letter sequence by walking the linked list.
--
Paul Hsieh
LINK
LINK |
| |
|
|
