Velocity Reviews > permutations

# permutations

Bill Cunningham
Guest
Posts: n/a

 04-21-2009
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
Guest
Posts: n/a

 04-21-2009
"Bill Cunningham" <(E-Mail Removed)> writes:
> 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

--
Keith Thompson (The_Other_Keith) http://www.velocityreviews.com/forums/(E-Mail Removed) <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"

Bill Cunningham
Guest
Posts: n/a

 04-21-2009

"Keith Thompson" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...

> tax txa atx axt xta xat
>

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

Bill

CBFalconer
Guest
Posts: n/a

 04-21-2009
Bill Cunningham wrote:
>
> 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

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

Stefan Ram
Guest
Posts: n/a

 04-21-2009
"Bill Cunningham" <(E-Mail Removed)> writes:
> 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
Guest
Posts: n/a

 04-21-2009
http://www.velocityreviews.com/forums/(E-Mail Removed)-berlin.de (Stefan Ram) writes:
>>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
Guest
Posts: n/a

 04-21-2009
Stefan Ram wrote:
> (E-Mail Removed)-berlin.de (Stefan Ram) writes:
>
>>>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 */

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

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

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

Falcon Kirtaran
Guest
Posts: n/a

 04-21-2009
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Bill Cunningham wrote:
> 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
kKwATfbhcobkyPKLOrxZIMPGR5Sx2bxTuXa2W4CXEy9Uj2sG3w 0EDIf2P6TelRgy
G52IdOdEMiB31TjoYwQ2QIXTyJQji8hG/qRcKOnodJe0f6h3B5fCwaGjFWyMfthH
vNE2g/wQjRFS+W87mKrjFujOu64zIrRyqBdsNVXtk8TYG9piITpFc7xu ftOfH4dq
5QsmPsJ/ZL7zrN4OdnESpT7iq1FfzK780XQ/OZ+s2A49z45WWNR0zKfLuMnt/bVS
NMpT9XaydWfrNzKIGVKOEXntQZptfzOB8jxd8r0Y19Bne4cvB7 cRR3uNTAzRr0cY
RKPZj73ckDJut/3BB0xaG9gl4QLXGjvcmGB0H0oqrQbuczEPeCmEj51+oyFcX/6n
Zqb7CNF8J7x2rdOX49drdxm642D7D2fJ1kfZpW+x4nZjTICfRg OQ1v5kLYYblyA1
c9Mr4V0XtA4VsHDtR4+I
=aghY
-----END PGP SIGNATURE-----

Ben Bacarisse
Guest
Posts: n/a

 04-21-2009
"Bill Cunningham" <(E-Mail Removed)> writes:

> "Keith Thompson" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)...
>
>> tax txa atx axt xta xat
>>

> 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.

Ben Bacarisse
Guest
Posts: n/a

 04-21-2009
Kenneth Brody <(E-Mail Removed)> writes:

> 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.