Can this be optimized?

[mdr]

Hi,

I have a string permutation function that generates all permutations, of all lengths, for a given string input. I don't like that I have to create a dictionary object to check if that combination has already been created. I think the whole function could be optimized, honestly.

<script type="text/javascript">
var list = [];

function permutate(permutation, addendum) {
if (addendum.length == 0) {
if (list[permutation] == undefined) {
list[permutation] = 1;
console.log(permutation);
}
return;
}
for (var i = 0; i < addendum.length; i++) {
permutate(permutation + addendum.charAt(i), addendum.substring(0, i) + addendum.substring(i+1, addendum.length));
}
for (var i = permutation.length; i > 0; i--) {
permutate("", permutation.substring(0, i));
}
}

permutate("", "abc");
</script>

Does anyone know how to do this more efficiently?

 

[wolfgang zeidler]

Hi,

I have a string permutation function that generates all permutations, of all lengths, for a given string input. I don't like that I have to create a dictionary object to check if that combination has already been created. I think the whole function could be optimized, honestly.

<script type="text/javascript">
var list = [];

function permutate(permutation, addendum) {
if (addendum.length == 0) {
if (list[permutation] == undefined) {
list[permutation] = 1;
console.log(permutation);
}
return;
}
for (var i = 0; i< addendum.length; i++) {
permutate(permutation + addendum.charAt(i), addendum.substring(0, i) + addendum.substring(i+1, addendum.length));
}
for (var i = permutation.length; i> 0; i--) {
permutate("", permutation.substring(0, i));
}
}

permutate("", "abc");
</script>

Does anyone know how to do this more efficiently?

2 questions:

1.
What result do you expect?
I assume you want all permutations of all "subset-strings",
e.g. input string 'abc' --> all permutions of ...
.... abc
.... ab
.... ac
.... ab
.... a
.... b
.... c
.... ''

2.
May your input string contain a letter more than once,
e.g. 'aab' ( letter 'a' twice )

wz

 

[Michael Haufe (\TNO\)]

Hi,

I have a string permutation function that generates all permutations, of all lengths, for a given string input. I don't like that I have to create adictionary object to check if that combination has already been created. Ithink the whole function could be optimized, honestly.

<script type="text/javascript">
var list = [];

function permutate(permutation, addendum) {
        if (addendum.length == 0) {
                if (list[permutation] == undefined) {
                        list[permutation] = 1;
                        console.log(permutation);
                }
                return;
        }
        for (var i = 0; i < addendum.length; i++) {
                permutate(permutation + addendum.charAt(i), addendum.substring(0, i) + addendum.substring(i+1, addendum.length));
        }
        for (var i = permutation.length; i > 0; i--) {
                permutate("", permutation.substring(0, i));
        }

}

permutate("", "abc");
</script>

Does anyone know how to do this more efficiently?

var perm = (function(){
function perm(xs,ys){
if(ys.length){
for(var i = 0; i < ys.length; i++){
WScript.Echo(xs + ys.charAt(i))
perm( xs + ys.charAt(i), ys.slice(0,i) + ys.slice(i +
1))
}
}
}
return function(ys){ perm("",ys) }
})()

perm("abcd");


This is 3ms vs 12ms for yours

 

[Dr J R Stockton]

In comp.lang.javascript message <fdbf6c65-74da-46c1-9334-899d7581cea4@gl
egroupsg2000goo.googlegroups.com>, Tue, 21 Jun 2011 09:12:09, mdr

I have a string permutation function that generates all permutations,
of all lengths, for a given string input. I don't like that I have to
create a dictionary object to check if that combination has already
been created. I think the whole function could be optimized, honestly.

Does anyone know how to do this more efficiently?

Web <http://www.merlyn.demon.co.uk/js-misc0.htm#CaP> should include
essentially what you require, presentation apart. It is possible
(untested) that the internal string manipulation might be better done by
RegExps.

Since your code looks not unlike mine - did you check that your
uniqueness check actually finds any non-uniques?

But perhaps you need that only for the case of characters in the string
being repeated? I have, I think, a better way of handling that. While
there must be 6! = 720 permutations of "Orange", I see only 60 for
"Banana" - theory says 6! / (2! * 3!) = 720/12 = 60 - voila!

so perhaps my function PermDups is what you need; the page explains it.

For those unwilling to read the page :

The set of permutations of "Mississippi" is the set of
permutations of sorted "Mississippi" ("Miiiippssss"), and
sorting is fast enough.

So first sort the input, then after 'for (;' insert code for
/but only if this element differs from the previous/ - in other
words, where successive available elements are
indistinguishable, only one should be a candidate.

I think my algorithm is good and the coding direct; but there are
probably small optimisations that could be done. Also, someone might
know how to convert the recursive algorithm into an iterative one.

- - -

Now looking at Michael Haufe's code - that does not deal with duplicates
- permuting "boo" I get for example two instances of "oo". And my
PermDups only gives full-length output, though Perms there shows all
length. Combine them.

 

[RobG]

Hi,

I have a string permutation function that generates all permutations, of all lengths, for a given string input. I don't like that I have to createa dictionary object to check if that combination has already been created.I think the whole function could be optimized, honestly.

<script type="text/javascript">
var list = [];

function permutate(permutation, addendum) {
        if (addendum.length == 0) {
                if (list[permutation] == undefined){
                        list[permutation] = 1;
                        console.log(permutation);
                }
                return;
        }
        for (var i = 0; i < addendum.length; i++) {
                permutate(permutation + addendum.charAt(i), addendum.substring(0, i) + addendum.substring(i+1, addendum.length));
        }
        for (var i = permutation.length; i > 0; i--) {
                permutate("", permutation.substring(0, i));
        }

}

permutate("", "abc");
</script>

Does anyone know how to do this more efficiently?

var perm = (function(){
    function perm(xs,ys){
        if(ys.length){
            for(var i = 0; i < ys.length; i++){
                WScript.Echo(xs + ys.charAt(i))
                perm( xs + ys.charAt(i), ys.slice(0,i) + ys.slice(i +
1))
            }
        }
    }
    return function(ys){ perm("",ys) }

})()

perm("abcd");

This is 3ms vs 12ms for yours

Great code

Probably also worth noting that the number of combinations and
permutations increases exponentially based on the string length. For a
string of 20 characters, there are 20! permutations of 20 characters,
which is 2,432,902,008,176,640,000 (or about 2.4 million trillion). If
given to a super computer the task would take 770 years if it
calculated 100 million permutations per second.

The number of permutations of all lengths of a 20 character string is
several orders of magnitude higher.

 

[Ben Bacarisse]

... For a
string of 20 characters, there are 20! permutations of 20 characters,
which is 2,432,902,008,176,640,000 (or about 2.4 million trillion).

The number of permutations of all lengths of a 20 character string is
several orders of magnitude higher.

I make it about 2.71828 times larger. Unless I've gone wrong, if P(N)
is the number of permutations of all sub-strings of a string of length
N, then the ratio P(N)/N! tends to e as N increases. I suppose it would
be "natural" to call that one order of magnitude, but not several.

<snip>

 

[RobG]

I make it about 2.71828 times larger.  Unless I've gone wrong, if P(N)
is the number of permutations of all sub-strings of a string of length
N, then the ratio P(N)/N! tends to e as N increases.  I suppose it would
be "natural" to call that one order of magnitude, but not several.

I don't know how to write the equation properly, but it's:

n! + n!/(n-1)! + n!/(n-2)! + ... + n!/1!

which is about 1.389e21 for 21 characters[1] compared to 2.433e18 for
20! so about 1,000 times larger (which I count as 3 orders of
magnitude).


1. Javascript can calculate the value for 19 (330,665,665,962,404,000
say 3.307e17) or 21 (138,879,579,704,209,670,000 say 1.389e21)
characters, but not 20. I could get a bigInt library onto it, but I
don't really care *that* much.

Incidentally, the function I used was:

/* Return an array of all factorials from 1 to n
* in array position 1 to n
*/
var calcFactorials = (function() {

// Remember the factorials calculated so far.
// Minimum initial value is [0].
// but can initialise with as many values as required,
// the more that are supplied the fewer that need
// to be calculated. Below is up to 9!
var result = [0,1,2,6,24,120,720,5040,40320,362880];

return function (n) {

// Only calculate more if haven't already done up to n
if (n > result.length) {
var i = result.length - 1;
var p = result || 1;

while (i++ < n) {
p = i * p;
result = p;
}
return result;

// If already calcuated up to n, just return those
} else {
return result.slice(0, ++n);
}
}
}());

/* Calculate how many permutations of any length can be
* generated from a set of n unique terms.
* Requires calcFatorials function.
*/
function numberOfPermutations(n) {
if (n < 1) return 0;
var facs = calcFactorials(n); // Array of factorials
var c = facs[n]; // c = n!
var r = c; // r = n!

while (--n) {
r += c / facs[n];
}
return r;
}

 

[Scott Sauyet]

I make it about 2.71828 times larger.  Unless I've gone wrong, if P(N)
is the number of permutations of all sub-strings of a string of length
N, then the ratio P(N)/N! tends to e as N increases.  I suppose it would
be "natural" to call that one order of magnitude, but not several.

I don't know how to write the equation properly, but it's:

  n! + n!/(n-1)! + n!/(n-2)! + ... + n!/1!

which is about 1.389e21 for 21 characters[1] compared to 2.433e18 for
20! so about 1,000 times larger (which I count as 3 orders of
magnitude).

That's a different question. The number of permutations of 21
characters is very different from the number of permutations of up to
20 characters.

That ratio, as Ben said, approaches Euler's constant, e, approximately
2.718281828459045. (Hence the joke about "natural", as e is the base
of the "natural logarithms.)

From your functions, it's simply the ratio

numberOfPermutations(20) / calcFactorials(20)[20]

BTW, in your calcFactorials function, you start with this:

var result = [0,1,2,6,24,120,720,5040,40320,362880];

but the factorial of 0 is for numerous good reasons generally taken to
be 1.

-- Scott

 

[RobG]

I don't know how to write the equation properly, but it's:

  n! + n!/(n-1)! + n!/(n-2)! + ... + n!/1!

which is about 1.389e21 for 21 characters[1] compared to 2.433e18 for
20! so about 1,000 times larger (which I count as 3 orders of
magnitude).

That's a different question.  The number of permutations of 21
characters is very different from the number of permutations of up to
20 characters.

That ratio, as Ben said, approaches Euler's constant, e, approximately
2.718281828459045.  (Hence the joke about "natural", as e is the base
of the "natural logarithms.)

From your functions, it's simply the ratio

    numberOfPermutations(20) / calcFactorials(20)[20]

I miscounted the places earlier:

21! = 5.1,09e19
x = 1.389e20

where x is the number of all permutations up to and including 21. And
yes, the ration is pretty close to 2.7 so my bad for guessing when I
should have made sure. Anyhow, they are all stupidly large numbers
where each represents s sequence of calculations.

BTW, in your calcFactorials function, you start with this:

  var result = [0,1,2,6,24,120,720,5040,40320,362880];

but the factorial of 0 is for numerous good reasons generally taken to
be 1.

Thanks, I'll fix that. It also tidies up some of my other calcs.

 

[Dr J R Stockton]

In comp.lang.javascript message <6a56e84f-3236-4485-a226-31d85de9818c@j1
4g2000prn.googlegroups.com>, Thu, 23 Jun 2011 01:58:53, RobG

1. Javascript can calculate the value for 19 (330,665,665,962,404,000
say 3.307e17) or 21 (138,879,579,704,209,670,000 say 1.389e21)
characters, but not 20. I could get a bigInt library onto it, but I
don't really care *that* much.

<http://www.merlyn.demon.co.uk/js-maths.htm#BF> gives, in under a minute
I think, 1e9! = 9.901322510555822e8565705522 - note the 'e'. My
longcalc.exe gets rather slow by 10000!, but it is exact.