placas

06-05-2002, 10:30 AM

how can i calculate all the permutations from a string?

ex: ab

ab

ba

ex: abc

abc

acb

bac

bca

cab

cba

ex: ab

ab

ba

ex: abc

abc

acb

bac

bca

cab

cba

Click to See Complete Forum and Search --> : permutations

placas

06-05-2002, 10:30 AM

how can i calculate all the permutations from a string?

ex: ab

ab

ba

ex: abc

abc

acb

bac

bca

cab

cba

ex: ab

ab

ba

ex: abc

abc

acb

bac

bca

cab

cba

brutfood

06-05-2002, 11:44 AM

n! (n factorial)

placas

06-05-2002, 11:50 AM

It's not the number of permutations I want.

I want the list of all permutations

I want the list of all permutations

brutfood

06-05-2002, 11:55 AM

ohhhhhhhh! - I'll need to think about that one.

brutfood

06-05-2002, 12:14 PM

It's late at night - well small hours here - I need some sleep. But I think the solution is sort of recursive.

You know how to deal with two symbols, and you can write a function:

f(a,b) which returns the two solutions a,b and b,a

For longer strings, the function (call it g()) takes a string of characters longer than 2. The string has a head of length 1, and a tail of length n-1.

so g(string) gives the first solution head, g(tail)

(It calls itself recursively - unless the tail is of length 2, then it calls f(tail) )

then it shifts the string right so that head ends up as the last character (a,b,c,d) becomes (b,c,d,a),

and again g(string) gives the next solution head, g(tail)

And it repeats this shift/roll operation until the string returns to its original value. Then it stops.

I'll write you actionscript (not lisp) tomorrow morning if this doesn't sort it out for you :)

You know how to deal with two symbols, and you can write a function:

f(a,b) which returns the two solutions a,b and b,a

For longer strings, the function (call it g()) takes a string of characters longer than 2. The string has a head of length 1, and a tail of length n-1.

so g(string) gives the first solution head, g(tail)

(It calls itself recursively - unless the tail is of length 2, then it calls f(tail) )

then it shifts the string right so that head ends up as the last character (a,b,c,d) becomes (b,c,d,a),

and again g(string) gives the next solution head, g(tail)

And it repeats this shift/roll operation until the string returns to its original value. Then it stops.

I'll write you actionscript (not lisp) tomorrow morning if this doesn't sort it out for you :)

Ed Mack

06-05-2002, 06:31 PM

Do you mean somthing like this:?

<u><b><i><big>Please could somebody turn html off, I can't post my code!</big></i></b></u>

function pre(s,o){

for(i=0;i<s.length-1;i++){

trace(s);

}

s += s.substring(0,1);

s = s.substring(1,s.length);

if(s != o){

pre(s,o);

}

}

function start_pre(s){

pre(s,s);

}

start_pre("abc");

As for the swapping, I'm a bit confused.

<u><b><i><big>Please could somebody turn html off, I can't post my code!</big></i></b></u>

function pre(s,o){

for(i=0;i<s.length-1;i++){

trace(s);

}

s += s.substring(0,1);

s = s.substring(1,s.length);

if(s != o){

pre(s,o);

}

}

function start_pre(s){

pre(s,s);

}

start_pre("abc");

As for the swapping, I'm a bit confused.

brutfood

06-05-2002, 09:00 PM

G'day and good morning from not so sunny Adelaide.

function permutations(before,s) {

if (s.length<=1) trace(before+s);

else for (var i=0;i<s.length;i++) {

permutations(before+s.substring(0,1),s.substring(1 ,s.length));

s += s.substring(0,1);

s = s.substring(1,s.length)

}

}

permutations("","abcd");

function permutations(before,s) {

if (s.length<=1) trace(before+s);

else for (var i=0;i<s.length;i++) {

permutations(before+s.substring(0,1),s.substring(1 ,s.length));

s += s.substring(0,1);

s = s.substring(1,s.length)

}

}

permutations("","abcd");

placas

06-06-2002, 05:29 AM

thanks

mikaelian

06-06-2002, 05:11 PM

Originally posted by placas

It's not the number of permutations I want.

I want the list of all permutations

Hmm.. Here are two methods that enable you to list all the permutations:

Method 1.

You already can list oll the pernutations of 2 elements:

ab

ba

Now let us add the third element c to this list. For the element c we have three places in our already existing two permutations (of two elements a and b). Namely: before the permutation, between the first and second elements, and after the permutation. So we get the following three pairs:

cab

cba

acb

bca

abc

bac

Now we can repeat this step to have all the permutations of four elements, etc...

Method 2.

This method is called lexicographiocal ordering. That is, we order the permutations like the words in a dictionary: first comes a, then b, etc... For example:

abcd

abdc

acbd

acdb

adbc

adcb

bacd

badc

etc...

It's not the number of permutations I want.

I want the list of all permutations

Hmm.. Here are two methods that enable you to list all the permutations:

Method 1.

You already can list oll the pernutations of 2 elements:

ab

ba

Now let us add the third element c to this list. For the element c we have three places in our already existing two permutations (of two elements a and b). Namely: before the permutation, between the first and second elements, and after the permutation. So we get the following three pairs:

cab

cba

acb

bca

abc

bac

Now we can repeat this step to have all the permutations of four elements, etc...

Method 2.

This method is called lexicographiocal ordering. That is, we order the permutations like the words in a dictionary: first comes a, then b, etc... For example:

abcd

abdc

acbd

acdb

adbc

adcb

bacd

badc

etc...

StuartW

04-15-2003, 07:17 AM

Wicked :D That's what I was looking for too.

I have a question for Brutfood...

I am using your permutation function - excellent - but I'm trying to adapt it to calculate and list each permutation onEnterFrame, in order to better understand what's going on. I'm a bit out of my depth here. Can't quite get it to do the part when you call the function from within the function.

This is what I have so far, but obviously I'm missing the most important part so it's just tracing one permutation:

var b = "";

var s = "abcd";

var i = 0;

_root.onEnterFrame = function() {

if (s.length<=1) {

trace(b + s);

} else {

if (i<s.length) {

b = b + s.substring(0, 1);

s = s.substring(1, s.length);

//this bit is in the wrong place, I think:

s += s.substring(0, 1);

s = s.substring(1, s.length);

i++;

}

}

}

:confused: Any pointers would be really appreciated.

Thanks in advance, it's an awsome method.

Stu

I have a question for Brutfood...

I am using your permutation function - excellent - but I'm trying to adapt it to calculate and list each permutation onEnterFrame, in order to better understand what's going on. I'm a bit out of my depth here. Can't quite get it to do the part when you call the function from within the function.

This is what I have so far, but obviously I'm missing the most important part so it's just tracing one permutation:

var b = "";

var s = "abcd";

var i = 0;

_root.onEnterFrame = function() {

if (s.length<=1) {

trace(b + s);

} else {

if (i<s.length) {

b = b + s.substring(0, 1);

s = s.substring(1, s.length);

//this bit is in the wrong place, I think:

s += s.substring(0, 1);

s = s.substring(1, s.length);

i++;

}

}

}

:confused: Any pointers would be really appreciated.

Thanks in advance, it's an awsome method.

Stu

Dickee

04-15-2003, 01:46 PM

StuartW

I've included an excerpt from 'MathExtensions.as' which includes 3 'Sets' prototypes to show the math involved, and to verify the 'permutationsList' result. As for your request to show each permutation result, I've included an array in brutfood's algorithm that is traced after each 'push'.

brutfood

I hope you don't mind that I changed your function name to 'permutationsList' so it wouldn't conflict with my Math prototype name, and to more correctly describe it's functionality.

#include "MathExtensions.as"

/* excerpt from MathExtensions.as:

// http://members.shaw.ca/flashmath101/as/MathExtensions.as

// 30 - returns factorial of a positive integer

Math.factorial = function(n) {

if (n!=0) {

return n*Math.factorial(n-1);

} else {

return (1);

}

};

// 31 - number of ways to arrange a list - order matters

Math.permutations = function(n,r) {

return Math.factorial(n)/Math.factorial(n-r);

};

// 32 - number of ways to arrange a list - order doesn't matter

Math.combinations = function(n,r) {

return Math.permutations(n,r)/Math.factorial(r);

};

*/

// brutfood's permutationsList

temp_array = [];

function permutationsList(before,s) {

if (s.length<=1) temp_array.push(before+s), trace(temp_array);

else for (var i=0;i<s.length;i++) {

permutationsList(before+s.substring(0,1),s.substri ng(1,s.length));

s += s.substring(0,1);

s = s.substring(1,s.length)

}

}

permutationsList("","abcd");

trace(Math.permutations(4,4));

Richard

I've included an excerpt from 'MathExtensions.as' which includes 3 'Sets' prototypes to show the math involved, and to verify the 'permutationsList' result. As for your request to show each permutation result, I've included an array in brutfood's algorithm that is traced after each 'push'.

brutfood

I hope you don't mind that I changed your function name to 'permutationsList' so it wouldn't conflict with my Math prototype name, and to more correctly describe it's functionality.

#include "MathExtensions.as"

/* excerpt from MathExtensions.as:

// http://members.shaw.ca/flashmath101/as/MathExtensions.as

// 30 - returns factorial of a positive integer

Math.factorial = function(n) {

if (n!=0) {

return n*Math.factorial(n-1);

} else {

return (1);

}

};

// 31 - number of ways to arrange a list - order matters

Math.permutations = function(n,r) {

return Math.factorial(n)/Math.factorial(n-r);

};

// 32 - number of ways to arrange a list - order doesn't matter

Math.combinations = function(n,r) {

return Math.permutations(n,r)/Math.factorial(r);

};

*/

// brutfood's permutationsList

temp_array = [];

function permutationsList(before,s) {

if (s.length<=1) temp_array.push(before+s), trace(temp_array);

else for (var i=0;i<s.length;i++) {

permutationsList(before+s.substring(0,1),s.substri ng(1,s.length));

s += s.substring(0,1);

s = s.substring(1,s.length)

}

}

permutationsList("","abcd");

trace(Math.permutations(4,4));

Richard