all arrangement of a word

[longshan]

Hi friends,
Can you help me write some code to list all the arrangement of a word?
for example
"unix"
it has possibilities like
nixu,ixun,,,and so on.
I think we can get 4!(4*3*2*!)=24 possibilities

But how to list them all by C?
thanks

[Peter Nilsson]

longs...@marchm ail.com wrote:

Hi friends,
Can you help me write some code to list all the arrangement of
a word?
for example
"unix"
it has possibilities like
nixu,ixun,,,and so on.
I think we can get 4!(4*3*2*!)=24 possibilities

But how to list them all by C?

http://groups.google.com/group/comp....c0260bb56e83f2

--
Peter

[Keith Thompson]

lo******@marchm ail.com writes:

Hi friends,
Can you help me write some code to list all the arrangement of a word?
for example
"unix"
it has possibilities like
nixu,ixun,,,and so on.
I think we can get 4!(4*3*2*!)=24 possibilities

But how to list them all by C?
thanks

What have you tried? Where did you run into problems? What C
language issues are you having trouble with?

Or did you just want us to do your homework for you?

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[longshan]

On Jul 7, 12:25*pm, Keith Thompson <[e-mail] rote:

longs...@marchm ail.com writes:

Hi friends,
Can you help me write some code to list all the arrangement of a word?
for example
"unix"
it has possibilities like
nixu,ixun,,,and so on.
I think we can get 4!(4*3*2*!)=24 possibilities

But how to list them all by C?
thanks

What have you tried? *Where did you run into problems? *What C
language issues are you having trouble with?

Or did you just want us to do your homework for you?

--
Keith Thompson (The_Other_Keit h) [e-mail] *<http://www.ghoti.net/~kst>
Nokia
"We must do something. *This is something. *Therefore, we must do this."
* * -- Antony Jay and Jonathan Lynn, "Yes Minister"

Hi,
I just need some idea about how to do this.

[santosh]

lo******@marchm ail.com wrote:

<snip>

Hi,
It's really not a homework.
Actually I am not even a CS student.
I am a pharmacist.

Nevertheless unless you indicate that you have made an attempt at the
problem (by posting your solution, code or pseudocode, complete or
incomplete, right or wrong), you'll find that almost everyone will
refuse to hand you ready-made code.

<snip>

[Richard Heathfield]

lo******@marchm ail.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

[CBFalconer]

lo******@marchm ail.com wrote:

>
Can you help me write some code to list all the arrangement of a word?
for example
"unix"
it has possibilities like
nixu,ixun,,,and so on.
I think we can get 4!(4*3*2*!)=24 possibilities

But how to list them all by C?

Try the following, combined with the following alias:

[1] c:\c\jumble>ali as jumble
\c\jumble\jumbl e %1& | sort | uniq | pr -a -T --columns=8

[1] c:\c\jumble>jum ble unix
string="unix", max=24, len=4
inux inxu iunx iuxn ixnu ixun niux nixu
nuix nuxi nxiu nxui uinx uixn unix unxi
uxin uxni xinu xiun xniu xnui xuin xuni

and the code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/* Public domain, by C.B. Falconer. *//* 2003-Aug-21 */
/* Attribution appreciated. */

/* Things get out of hand when larger than 8 */
#define MAXWORD 12

/* ------------------ */

/* exchange 0th and ith char in wd */
void trade(char *wd, unsigned int i)
{
char c;

c = *wd;
*wd = wd[i];
wd[i] = c;
} /* trade */

/* ------------------ */

/* Form all n char permutations of the characters in the
string wd of length lgh into outstring at index ix.
Output the results to stdout. */
void jumble(char *wd, unsigned int lgh,
unsigned int ix, /* output place to fill */
unsigned int n, /* max out places to fill */
char *outstring)
{
unsigned int i;

if (0 == n) {
outstring[ix] = '\0';
puts(outstring) ;
}
else
for (i = 0; i < lgh; i++) {
trade(wd, i); /* nop when (0 == i) */
outstring[ix] = *wd;
jumble(wd+1, lgh-1, ix+1, n-1, outstring);
trade(wd, i); /* restore the wd string */
}
} /* jumble */

/* ------------------ */

int main(int argc, char *argv[])
{
unsigned int n, lgh, min;
double max;
char outstring[MAXWORD];

if (argc < 2) {
fprintf(stderr,
"Usage: jumble <baseword[lgh]\n"
" where the (optional) lgh specifies the\n"
" maximum length of the output words\n");
return 0;
}
lgh = strlen(argv[1]);
if (lgh >= MAXWORD) argv[1][lgh = MAXWORD-1] = '\0';

min = lgh;
if ((argc 2) && (1 == sscanf(argv[2], "%u", &n)))
if (n && (n <= lgh)) min = n;

for (n = lgh, max = 1.0; n (lgh - min); n--)
max = max * n;

fprintf(stderr, "string=\"% s\", max=%.0f, len=%u\n",
argv[1], max, min);

jumble(argv[1], lgh, 0, min, outstring);
return 0;
} /* main */

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home .att.net>
Try the download section.

[Ben Bacarisse]

CBFalconer <cb********@yah oo.comwrites:

<snip>

/* Things get out of hand when larger than 8 */
#define MAXWORD 12

Is this a deliberate mystery or an editing error?

--
Ben.

[CBFalconer]

Ben Bacarisse wrote:

CBFalconer <cb********@yah oo.comwrites:

<snip>

>/* Things get out of hand when larger than 8 */
#define MAXWORD 12

Is this a deliberate mystery or an editing error?

As I recall it, the first version ran on a 486, and the runtime
became annoying at 8. Later it was copied to a Pentium system, and
things ran faster, so I allowed that. For my purposes I make it
17, and just abort if I am not willing to wait it out.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home .att.net>
Try the download section.

[temppimaili]

Seems that you got answers already, but I'll add my 2c.

On Jul 7, 6:01 am, longs...@marchm ail.com wrote:

Hi friends,
Can you help me write some code to list all the arrangement of a word?
for example
"unix"
it has possibilities like
nixu,ixun,,,and so on.
I think we can get 4!(4*3*2*!)=24 possibilities

For n different character yes, you can have n! different n-length
words as explained previously. But it gets more complicated if not all
the characters differ and in that case the count of possible
permutations decrease.

But how to list them all by C?
thanks

If you are just looking for an working algorithm without jumping in
the glory details I would suggest you to take a look at
http://en.wikipedia.org/wiki/Permutation

All you have to do is to implement the algorithm in C. Now that you
already know the number of possible permutations just pack the
algorithm inside a suitable for-loop and you're done. Note that the
Wikipedia algorithm indexing scheme differs from C..