lo******@marchmail.com said:
<snip>
Hi,
It's really not a homework.
Actually I am not even a CS student.
I am a pharmacist.
Surely I can spend a few months to figure it out.
But I dont think I have to invent the raw wheel again.
Internet help us to stand on efforts on others
that's why it grow so fast.
As a pharmacist, you will realise that there is more to pharmacy than
asking other people how to make up each specific prescription.
Imagine this situation:
Someone who knows little or nothing about pharmacy opens a shop next door
to yours.
Whenever they get a customer, they bring the prescription round to your
shop.
They don't pay you for your skill in making up the prescription.
They take the medicine back to their own shop, and hand it to the customer
in return for some money.
Do that for very long, and you'll be out of business - and shortly
afterwards, they'll be out of business too, because their source of
information has dried up.
When you studied to become a pharmacist, people were willing to teach you,
yes? But they never said "you don't have to learn anything because we'll
always be there to do it for you".
So - here's a starting point for you:
The number of arrangements of a one-letter word is 1, so working out ALL
the arrangements is easy.
If you have a word with more than one letter in it, say N letters, it's a
little bit harder, because any of the N letters could be at the start. So
take each letter in turn, put it BEFORE the other N-1 letters, and then
solve the problem of calculating the arrangement of N-1 letters.
Eventually, N-1 becomes 1, at which point you can switch to the easy
solution (see above).
Example: STUDY
Let's take each letter in turn and put it at the front:
S TUDY
T UDYS
U DYST
D YSTU
Y STUD
We had a complicated problem - all the arrangements of the five-letter word
STUDY - and we've replaced it with five simpler problems. Each of these
simpler problems hands us a given letter, and a group of only FOUR letters
that need to be arranged. We can solve these sub-problems in the same way.
I'll show you how to do this for the S sub-problem, but the technique is
the same for the other four.
S TUDY
Let's take each letter in turn (from the four whose arrangements we need)
and put it at the front, keeping the S around only so that we don't forget
about it:
(S) T UDY
(S) U DYT
(S) D YTU
(S) Y TUD
We had a complicated problem - all the arrangements of the four-letter word
TUDY - and we've replaced it with four simpler problems. Each of these
simpler problems hands us two given letters (including the S), and a group
of only THREE letters that need to be arranged. We can solve these
sub-problems in the same way. I'll show you how to do this for the T
sub-problem, but the technique is the same for the other three.
(S) T UDY
Let's take each letter in turn (from the three whose arrangements we need)
and put it at the front, keeping the S and T around only so that we don't
forget about them:
(ST) U DY
(ST) D YU
(ST) Y UD
We had a complicated problem - all the arrangements of the three-letter
word UDY - and we've replaced it with three simpler problems. Each of
these simpler problems hands us three given letters (including the S and
T), and a group of only TWO letters that need to be arranged. We can solve
these sub-problems in the same way. I'll show you how to do this for the U
sub-problem, but the technique is the same for the other two.
(ST) U DY
Let's take each letter in turn (from the two whose arrangements we need)
and put it at the front, keeping the S, T and U around only so that we
don't forget about them:
(STU) D Y
(STU) Y D
We had a complicated problem - all the arrangements of the two-letter word
DY - and we've replaced it with three simpler problems. Each of these
simpler problems hands us four given letters (including the S, T and U),
and a group of only ONE letter that needs to be arranged. Since there is
only one way to arrange one letter, this sub-problem is done.
Subjects for further study:
1) arrays
2) counters (to keep track of how many given letters you have)
3) array rotation using copy from front, memmove, copy to back
4) recursion
5) function pointers (so that you know what to do with a final arrangement
once you've found it)
In your testing, remember that N unique items can be arranged in N!
different ways - so 1 item can be arranged in 1 way, 2 items in 1x2=2
ways, 3 items in 1x2x3=6 ways, 4 items in 1x2x3x4=24 ways, and so on. If
your testing gives different numbers, you have a bug. And definitely
remember that 10! is 3628800 (about three and a half million); factorials
grow alarmingly quickly, so don't get all excited about finding all the
arrangements of the word DERMATOGLYPHICS - even if you could find a
million arrangements per second, the 1307674368000 arrangements would take
over two weeks to calculate.
--
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
