Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > permutations

Reply
Thread Tools

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


 
Reply With Quote
 
 
 
 
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"
 
Reply With Quote
 
 
 
 
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


 
Reply With Quote
 
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>
Try the download section.

 
Reply With Quote
 
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() ); }


 
Reply With Quote
 
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" ); }

 
Reply With Quote
 
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 */
/* 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.


 
Reply With Quote
 
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
7oeX43iLABWp5y0G0TwY7vtUU61/pB5SJITVgu4VaAeKCOBA/AdsKX7onZRjnmUZ
NMpT9XaydWfrNzKIGVKOEXntQZptfzOB8jxd8r0Y19Bne4cvB7 cRR3uNTAzRr0cY
RKPZj73ckDJut/3BB0xaG9gl4QLXGjvcmGB0H0oqrQbuczEPeCmEj51+oyFcX/6n
Zqb7CNF8J7x2rdOX49drdxm642D7D2fJ1kfZpW+x4nZjTICfRg OQ1v5kLYYblyA1
oJVf0qzB0pRnnCDvVdu0E9bOU0IAFve4N3bkaFiotjsGAdR0CK 6KKrM9/8BVMIJI
c9Mr4V0XtA4VsHDtR4+I
=aghY
-----END PGP SIGNATURE-----
 
Reply With Quote
 
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.
 
Reply With Quote
 
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.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
[Slightly OT] Which algorithm for permutations Hendrik Maryns Java 0 03-03-2006 02:10 PM
Permutations of instances in array Karsten Wutzke Java 5 03-04-2004 04:49 AM
Finding permutations of a list in a map or multimap Daniel Fortin C++ 3 02-18-2004 09:51 AM
Permutations Ed Neukirch C++ 7 12-27-2003 12:44 AM
Permutations with repatitions in c++ Roger C++ 1 09-24-2003 10:52 PM



Advertisments