permutations

[Bill Cunningham]

Before I can come up with 1/2 or even 1/4 of the code I need to see all
permutations of a word I need to know what I'm asking. Which of these would
correctly be all the permutations of the word tax?

tax
axt
xta

-- or

tax
axa
xat

or something else?

Bill

 

[Keith Thompson]

Before I can come up with 1/2 or even 1/4 of the code I need to see all
permutations of a word I need to know what I'm asking. Which of these would
correctly be all the permutations of the word tax?

tax
axt
xta

-- or

tax
axa
xat

or something else?

tax txa atx axt xta xat

 

[Bill Cunningham]

tax txa atx axt xta xat

How did you obtain that? I've googled and see that permutation has many
different meanings.

Bill

 

[CBFalconer]

Before I can come up with 1/2 or even 1/4 of the code I need to
see all permutations of a word I need to know what I'm asking.
Which of these would correctly be all the permutations of the
word tax?

tax
axt
xta

-- or

tax
axa
xat

or something else?

else.

[1] c:\c\junk>jumble tax
string="tax", max=6, len=3
atx axt tax txa xat xta

 

[Stefan Ram]

Before I can come up with 1/2 or even 1/4 of the code I need to see all
permutations of a word I need to know what I'm asking. Which of these would
correctly be all the permutations of the word tax?

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

static void swap( int a[], int const i, int const j )
{ int const tmp = a[ i ];
a[ i ]= a[ j ];
a[ j ]= tmp; }

int array[] ={ 0, 1, 2 };

int dummy;

int l = sizeof array / sizeof 0[ array ];

int next()
{ int j = l - 1;
while( j > 0 && array[ j - 1 ]>= array[ j + 1 - 1 ])--j;
if( j == 0 )return 0;
else
{ int m = l;
while( array[ j - 1 ]>= array[ m - 1 ])--m;
swap( array, j - 1, m - 1 );
{ int k = j + 1;
m = l;
while( k < m ){ swap( array, k - 1, m - 1 ); ++k; --m; }}
return 1; }}

void print()
{ for( int i = 0; i < l; ++i )putchar( "tax"[ array[ i ]]);
putchar( '\n' ); }

int main( void )
{ do { print(); }while( next() ); }

 

[Stefan Ram]

correctly be all the permutations of the word tax?

int array[] ={ 0, 1, 2 };

That was just written for three-letter words.
This is more general:

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

inline void swap( int a[], int const i, int const j )
{ int const tmp = a[ i ];
a[ i ]= a[ j ];
a[ j ]= tmp; }

int next
( size_t const length,
int * const array )
{ int j = length - 1;
while( j > 0 && array[ j - 1 ]>= array[ j + 1 - 1 ])--j;
if( j == 0 )return 0;
else
{ int l = length;
while( array[ j - 1 ]>= array[ l - 1 ])--l;
swap( array, j - 1, l - 1 );
{ int k = j + 1;
l = length;
while( k < l ){ swap( array, k - 1, l - 1 ); ++k; --l; }}
return 1; }}

void print
( size_t const length,
char const * const text,
int const * const array )
{ for( size_t i = 0; i < length; ++i )putchar( text[ array[ i ]]);
putchar( '\n' ); }

/* Prints all permutations of "word" */
int main( void )
{ char const * const text = "word";
size_t const textlength = strlen( text );
int * const array = malloc( textlength * sizeof( int ));
if( array )
{ for( size_t i = 0; i < textlength; ++i )array[ i ]= i;
do { print( textlength, text, array ); }
while( next( textlength, array ));
free( array ); }
else fprintf( stderr, "no array.\n" ); }

 

[CBFalconer]

correctly be all the permutations of the word tax?

int array[] ={ 0, 1, 2 };

That was just written for three-letter words.
This is more general:

Here's another general version:

#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;
wd = 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 */

 

[Falcon Kirtaran]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Before I can come up with 1/2 or even 1/4 of the code I need to see all
permutations of a word I need to know what I'm asking. Which of these would
correctly be all the permutations of the word tax?

tax
axt
xta

-- or

tax
axa
xat

or something else?

Bill

Neither of them. The standard definition of a permutation essentially
comes down to every arrangement of the order of each character, of which
there are 3! (because there are three letters).

tax
txa
xat
xta
atx
axt

As you might notice, a common way of teaching this in elementary
combinatorics courses is putting it in the context of anagrams.

- --
- --Falcon Darkstar Christopher Momot
- --
- --OpenPGP: (7902:4457) 9282:A431

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iQIcBAEBAgAGBQJJ7TS+AAoJEKmxP9YxEE4rwhEP/RO13o9CnUBiUOt1aOcZz3HU
rpG8XSJcBFy00/fyrMBxH7EgO8Wzm7tted6gTWK3Duxt7WvTLS9dLufeku1XKWap
kKwATfbhcobkyPKLOrxZIMPGR5Sx2bxTuXa2W4CXEy9Uj2sG3w0EDIf2P6TelRgy
G52IdOdEMiB31TjoYwQ2QIXTyJQji8hG/qRcKOnodJe0f6h3B5fCwaGjFWyMfthH
vNE2g/wQjRFS+W87mKrjFujOu64zIrRyqBdsNVXtk8TYG9piITpFc7xuftOfH4dq
5QsmPsJ/ZL7zrN4OdnESpT7iq1FfzK780XQ/OZ+s2A49z45WWNR0zKfLuMnt/bVS
7oeX43iLABWp5y0G0TwY7vtUU61/pB5SJITVgu4VaAeKCOBA/AdsKX7onZRjnmUZ
NMpT9XaydWfrNzKIGVKOEXntQZptfzOB8jxd8r0Y19Bne4cvB7cRR3uNTAzRr0cY
RKPZj73ckDJut/3BB0xaG9gl4QLXGjvcmGB0H0oqrQbuczEPeCmEj51+oyFcX/6n
Zqb7CNF8J7x2rdOX49drdxm642D7D2fJ1kfZpW+x4nZjTICfRgOQ1v5kLYYblyA1
oJVf0qzB0pRnnCDvVdu0E9bOU0IAFve4N3bkaFiotjsGAdR0CK6KKrM9/8BVMIJI
c9Mr4V0XtA4VsHDtR4+I
=aghY
-----END PGP SIGNATURE-----

 

[Ben Bacarisse]

How did you obtain that?

With short strings it is relatively easy. For longer strings it helps
to use an algorithm:

(a) remove a letter (the first or last is a good choice).
(b) make a list of the permutation of the string you have left.
(c) for each string in this list
(c2) for each position in this string (including the ends)
(c3) insert the letter you removed into the string at that
place.

The algorithm is recursive -- making a list of permutations is done from a
list of permutations.

To illustrate with taxi:

(a) remove i from the end to get "tax".
(b) tax txa atx axt xta xat
(c) tax gives us: itax tiax taix taxi
txa gives: itxa tixa txia txai
atx gives: iatx aitx atix atxi
axt gives: iaxt aixt axit axti
xta gives: ixta xita xtia xtai
xat gives: ixat xiat xait xati

(check: that is 4x6 = 24 permutations, i.e. 4! = 4x3x2.)

I've googled and see that permutation has many
different meanings.

I suspect they are all closely related.

 

[Ben Bacarisse]

Ben Bacarisse wrote:
[...]

(check: that is 4x6 = 24 permutations, i.e. 4! = 4x3x2.)

[...]

Nit: 4! = 4x3x2x1

Ha! That must be one of the smallest nits ever picked!

 

[Ben Bacarisse]

Well, don't trust everything you happen to find with Google (or any
search engine, for that matter). There is only one mathematical
meaning for "permutation" that I am aware of. As I recall, it's
basically an ordered subset of a given set.

For any set of X items,
the number of permutations for a subset of Y items is X!/(X-Y)!.

So, for your set of 3 letters, the number of permutations of 3-letter
subsets is 3!/(3-3)!, or 6.

This view will confuse matters, I fear. It combines selection with
ordering in way that useful in combinatorics, but it not the best
match for what the OP is talking about. And by dealing with sets, it is
not applicable to words. For example, in computer science we'd say
that there are 24 permutations of the letters in "book" (and not all
of them are unique) but you can't even select 4 letters from the set
{b, o, k}.

The two most usual CS meanings of permutation are (a) an ordering of
the elements of a list and (b) a bijection from [1..n] to [1..n].

 

[kid joe]

With short strings it is relatively easy. For longer strings it helps
to use an algorithm:

(a) remove a letter (the first or last is a good choice).
(b) make a list of the permutation of the string you have left.
(c) for each string in this list
(c2) for each position in this string (including the ends)
(c3) insert the letter you removed into the string at that
place.

The algorithm is recursive -- making a list of permutations is done from a
list of permutations.

Hi Ben,

You can also do this nonrecursively. Heres a permutation program I wrote
when I was learning C based on an algorithm on Wikipedia.

Cheers,
Joe


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

void swap(char *s, char *t)
{
char w = *s;
*s = *t;
*t = w;
}

char *getperm(char *s, long long int i)
{
char *p = strdup(s);
for (unsigned int j = 1; j < strlen(p); i /= j, j++)
swap(p + j, p + i % j);
return p;
}

main(int argc, char **argv)
{
if (argc <= 1) {
fputs("Unspecified error\n", stderr);
abort();
}
long long int n = strlen(*++argv), m = n;
while (--n > 1)
m *= n;
while (m--) {
char *p = getperm(*argv, m);
puts(p);
free(p);
}
}


--
.---. .-----------
/ \ __ / ------
/ / \( )/ -----
////// ' \/ ` --- /=================\
//// / // : : --- | |
// / / /` '-- | Good Evening... |
// //..\\ | |
=============UU====UU============\================/
'//||\\`
''``

 

[Ben Bacarisse]

correctly be all the permutations of the word tax?

int array[] ={ 0, 1, 2 };

That was just written for three-letter words.
This is more general:

Here's another general version:

Yours is slightly less general that Stefan Ram's. Did you see how his
'main' had a loop that iterates over permutations? His code chose to
print the permutation, but it could do anything else if it wanted to.
In your version, you have to edit the source of the jumble function to
do something other than print the permutation.

/* 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 */

 

[Ben Bacarisse]

You can also do this nonrecursively. Heres a permutation program I wrote
when I was learning C based on an algorithm on Wikipedia.

char *getperm(char *s, long long int i)
{
char *p = strdup(s);
for (unsigned int j = 1; j < strlen(p); i /= j, j++)
swap(p + j, p + i % j);
return p;
}

This is not the right algorithm.

main(int argc, char **argv)
{
if (argc <= 1) {
fputs("Unspecified error\n", stderr);
abort();
}
long long int n = strlen(*++argv), m = n;
while (--n > 1)
m *= n;
while (m--) {
char *p = getperm(*argv, m);
puts(p);
free(p);
}
}

There are some C issues too.

Please cut down your sig.

 

[CBFalconer]

.... snip ...

Yours is slightly less general that Stefan Ram's. Did you see
how his 'main' had a loop that iterates over permutations? His
code chose to print the permutation, but it could do anything
else if it wanted to. In your version, you have to edit the
source of the jumble function to do something other than print
the permutation.

Philosophy. I keep it simple, and then complicate things with
aliases etc. Here are two:

[1] c:\c\junk>alias jumble
\c\jumble\jumble %1& | sort | uniq | pr -a -T --columns=8

[1] c:\c\junk>alias jumspell
c:\c\jumble\jumble %1& | sort | uniq | comm -1 -2 -
\djgpp\share\dict\words

(last line will have wrapped)

 

[Bill Cunningham]

[snip]

There are some C issues too.

Here's what bash's stderr told me.

p.c: In function `getperm':
p.c:15: `for' loop initial declaration used outside C99 mode
p.c: In function `main':
p.c:35: parse error at end of input

I see the swapping in Kid's code though the main function is a little beyond
me. In particualar *++argv. I now know that if there is a pointer in some
cases like this one I think, * dereferencing is what it's called. argv is a
char ** so it must be being dereferenced. The next thing is whats
deferencing again now? I will look into it because I don't want anyone to
think I'm not looking into things myself. If I understand or can remember
what it means, I don't know. Depends on how much I would work with it I
guess.

Bill

 

[Bill Cunningham]

Hi Ben,

You can also do this nonrecursively. Heres a permutation program I wrote
when I was learning C based on an algorithm on Wikipedia.

Cheers,
Joe


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

void swap(char *s, char *t)
{
char w = *s;
*s = *t;
*t = w;
}

Ok. I see.

char *getperm(char *s, long long int i)
{
char *p = strdup(s); /*Is strdup() a std function?

I can't find it anywhere. */

for (unsigned int j = 1; j < strlen(p); i /= j, j++)

/*parameter 3 of for is intellegible to me*/

swap(p + j, p + i % j); /*Whoa*/
return p;
}

main(int argc, char **argv)
{
if (argc <= 1) {
fputs("Unspecified error\n", stderr);
abort();
}
long long int n = strlen(*++argv), m = n;
while (--n > 1)
m *= n; /* What's *m mean? */
while (m--) {
char *p = getperm(*argv, m);
puts(p);
free(p);
}
}

I am not criticizing code here. I'm the student. I see no call to malloc
what's free for?

Bill

 

[Bill Cunningham]

Ben Bacarisse wrote:
[...]

(check: that is 4x6 = 24 permutations, i.e. 4! = 4x3x2.)

[...]

Nit: 4! = 4x3x2x1

What's the factorial and equation here? That's what I'n asking not about
encryption though that interests me too. Just an algebraic definition. I
think that's the math that uses permutations not arithmetic.

Bill

 

[Ben Bacarisse]

[snip]

There are some C issues too.

Here's what bash's stderr told me.

p.c: In function `getperm':
p.c:15: `for' loop initial declaration used outside C99 mode
p.c: In function `main':
p.c:35: parse error at end of input

It uses C99 features (but also has incompatible C90 features).

I see the swapping in Kid's code though the main function is a little beyond
me. In particualar *++argv. I now know that if there is a pointer in some
cases like this one I think, * dereferencing is what it's called. argv is a
char ** so it must be being dereferenced. The next thing is whats
deferencing again now? I will look into it because I don't want anyone to
think I'm not looking into things myself. If I understand or can remember
what it means, I don't know. Depends on how much I would work with it I
guess.

Study it by all means, but note that the algorithm is wrong (in a minor
way) so you won't get the right answers from it.

 

[Keith Thompson]

I can't find it anywhere. */

Nice catch. No, strdup is not a standard C function. (It is
specified by POSIX.) Here's a description from my system's man page:

The strdup() function returns a pointer to a new string which
is a duplicate of the string s. Memory for the new string is
obtained with malloc(3), and can be freed with free(3).

[...]

I am not criticizing code here. I'm the student. I see no call
to malloc what's free for?

It's needed to free the memory allocated by strdup().