[lnkForumImage]
TotalShareware - Download Free Software

Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.javascript

permuting a JS vector

Mark Tarver

5/31/2015 6:46:00 PM

function random_n (n) {
var r = Math.round(n * Math.random());
return r;}

function remove_nth (n, vector) {
var before = vector.slice(0,n);
var after = vector.slice(n+1,vector.length);
var result = before.concat(after);
return result;}

function rperm (vector) {
if (vector.length == 0)
{return []}
else
{var n = random_n(vector.length);
var x = vector[n];
var newvector = remove_nth(n, vector);
var recurse = rperm(newvector);
var result = recurse.push(x);
return result} }

var numbers = [1,2,3];
var perm = rperm(numbers);
console.log(perm);

It fails on https:... with TypeError: recurse.push is not a function

Solutions welcome.

Mark
5 Answers

Ben Bacarisse

5/31/2015 7:27:00 PM

0

dr.mtarver@gmail.com writes:

> function random_n (n) {
> var r = Math.round(n * Math.random());
> return r;}
>
> function remove_nth (n, vector) {
> var before = vector.slice(0,n);
> var after = vector.slice(n+1,vector.length);
> var result = before.concat(after);
> return result;}
>
> function rperm (vector) {
> if (vector.length == 0)
> {return []}
> else
> {var n = random_n(vector.length);
> var x = vector[n];
> var newvector = remove_nth(n, vector);
> var recurse = rperm(newvector);
> var result = recurse.push(x);
> return result} }
>
> var numbers = [1,2,3];
> var perm = rperm(numbers);
> console.log(perm);
>
> It fails on https:... with TypeError: recurse.push is not a function
>
> Solutions welcome.

Some pointers: your random_n function should use floor not round. You
can remove an array element using a single call to splice (though you
may need to copy the array at the top level, depending on the
requirements you have). The push function returns the new array length,
not an array. This last one is why you get the error.

--
Ben.

Mark Tarver

5/31/2015 8:10:00 PM

0

On Sunday, May 31, 2015 at 8:27:22 PM UTC+1, Ben Bacarisse wrote:
> dr.mtarver@gmail.com writes:
>
> > function random_n (n) {
> > var r = Math.round(n * Math.random());
> > return r;}
> >
> > function remove_nth (n, vector) {
> > var before = vector.slice(0,n);
> > var after = vector.slice(n+1,vector.length);
> > var result = before.concat(after);
> > return result;}
> >
> > function rperm (vector) {
> > if (vector.length == 0)
> > {return []}
> > else
> > {var n = random_n(vector.length);
> > var x = vector[n];
> > var newvector = remove_nth(n, vector);
> > var recurse = rperm(newvector);
> > var result = recurse.push(x);
> > return result} }
> >
> > var numbers = [1,2,3];
> > var perm = rperm(numbers);
> > console.log(perm);
> >
> > It fails on https:... with TypeError: recurse.push is not a function
> >
> > Solutions welcome.
>
> Some pointers: your random_n function should use floor not round. You
> can remove an array element using a single call to splice (though you
> may need to copy the array at the top level, depending on the
> requirements you have). The push function returns the new array length,
> not an array. This last one is why you get the error.
>
> --
> Ben.

ah - a side-effect function then - that mutates an array but returns number?

Mark

Ben Bacarisse

5/31/2015 9:43:00 PM

0

dr.mtarver@gmail.com writes:

> On Sunday, May 31, 2015 at 8:27:22 PM UTC+1, Ben Bacarisse wrote:
<snip>
>>[...] The push function returns the new array length,
>> not an array. This last one is why you get the error.
>>
> ah - a side-effect function then - that mutates an array but returns
> number?

Yes. You'll need a reference if you are learning JavaScript as you
can't really guess. For example:

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/...

--
Ben.

Dave \Crash\ Dummy

6/1/2015 6:34:00 PM

0

dr.mtarver@gmail.com wrote:
> function random_n (n) {
> var r = Math.round(n * Math.random());
> return r;}
>
> function remove_nth (n, vector) {
> var before = vector.slice(0,n);
> var after = vector.slice(n+1,vector.length);
> var result = before.concat(after);
> return result;}
>
> function rperm (vector) {
> if (vector.length == 0)
> {return []}
> else
> {var n = random_n(vector.length);
> var x = vector[n];
> var newvector = remove_nth(n, vector);
> var recurse = rperm(newvector);
> var result = recurse.push(x);
> return result} }
>
> var numbers = [1,2,3];
> var perm = rperm(numbers);
> console.log(perm);
>
> It fails on https:... with TypeError: recurse.push is not a function
>
> Solutions welcome.
>
> Mark
>

You didn't say
whether you *want* to write a permutation function
or you only *need* a permutation function.

In the second case maybe the following lines will be helpful.


<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/transitional.dtd...
<html><head><title>all_perm</title>
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
<style type="text/css">
* { font-family:"Courier New",Courier,monospace; white-space:pre; }
body { background-color:white; color:black; font-size:9pt; }
table { border:thin solid black; border-spacing:2px; margin-bottom:25px; }
td,th { text-align:right; padding-left:8px; padding-right:8px; }
</style>
<script type="text/javascript">
function perm ( es , n ) {
var ex = es.length - 1
if ( ex < 1 ) return es
var fk = [ 1 ]
var i
for ( i = 1 ; i <= ex ; ) fk.push ( fk [i-1] * ++i )
var vl = n % fk [ex]
if ( vl < 0 ) vl += fk [ex]
var s = ''
for ( i = ex ; i ; ) {
var ps = Math.floor ( vl / fk [--i] )
vl -= ps * fk [i]
s += es.charAt ( ps )
es = es.substr ( 0 , ps ) + es.substr ( ps + 1 )
}
return s + es
}
function inv_perm ( p0 , p1 ) {
if ( p0.length != p1.length ) return - 1
var ex = p0.length - 2
var fk = [ 1 ]
var i
for ( i = 1 ; i <= ex ; ) fk.push ( fk [i-1] * ++i )
fk.reverse ()
var res = 0
for ( i = 0 ; i <= ex ; i++ ) {
var ps = p0.indexOf ( p1.charAt ( i ) )
if ( ps < 0 ) return - 2 - i
if ( ps ) res += ps * fk [i]
p0 = p0.substr ( 0 , ps ) + p0.substr ( ps + 1 )
}
return res
}
function test ( es , m ) {
var a = []
for ( var i = - 1 ; i <= m ; i++ ) {
var p = perm ( es , i )
var v = inv_perm ( es , p )
if ( v != i && i > - 1 && i < m ) alert ( es + ' : ' + i )
a.push ( i + '</td><td>' + p + '</td><td>' + v )
}
document.write ( '<table><tr><td>' + a.join ( '</td></tr><tr><td>' )
+ '</td></tr></table>' )
}
</script>
</head><body><pre>
Bijektive Abbildung zwischen ...
.... den Zahlen von 0 bis Fakultät ( n ) - 1 und
.... den Permutationen eines Strings mit n Zeichen

function perm ( string , index_der_permutation ) --&gt; permutation
function inv_perm ( string , permutation ) --&gt; index_der_permutation
</pre>
<script type="text/javascript">
test ( 'xy' , 2 )
test ( '123' , 6 )
test ( 'abcd' , 24 )
test ( '12345' , 120 )
</script>
</body></html>

--
wzwz.de/mail

Scott Sauyet

6/5/2015 8:12:00 PM

0

dr.mtarver@gmail.com wrote:

> [ ... some helpers deleted ... ]
> function rperm (vector) {
> if (vector.length == 0)
> {return []}
> else
> {var n = random_n(vector.length);
> var x = vector[n];
> var newvector = remove_nth(n, vector);
> var recurse = rperm(newvector);
> var result = recurse.push(x);
> return result} }
>
> It fails on https:... with TypeError: recurse.push is not a
> function

Ben Bacarisse pointed out some issues with this. Perhaps the biggest one
issue is that, if you want to use this for longer lists, you will quickly
run into the recursion depth limits of the various implementations. There
is no tail-call optimization in JS (not that this version is prepared for
it.) So recursion is sometimes useful, but less useful than in languages
designed to handle it well.

However, if you want to do it recursively, with an algorithm like that,
here is what I would suggest is a somewhat more idiomatic way to do so:

function perm(ls) {
if (ls.length === 0) {
return [];
}
var n = Math.floor(ls.length * Math.random());
var beginning = ls.slice(0, n).concat(ls.slice(n + 1));
var end = ls[n];
return perm(beginning).concat(end)
}

(Also at <http://repl.it....)

Note that I've inlined your two helper functions. If they are useful
elsewhere, of course they might be called out separately, but they can
be written as they are here, as one-liners, so it seemed simpler to
just include them in the main function.

HTH,

-- Scott