PDA

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

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

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 :)

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.

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");

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

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

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