Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.javascript > #27948 > unrolled thread

permuting a JS vector

Back to article view | Back to comp.lang.javascript

Contents

  permuting a JS vector dr.mtarver@gmail.com - 2015-05-31 11:45 -0700
    Re: permuting a JS vector Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-05-31 20:27 +0100
      Re: permuting a JS vector dr.mtarver@gmail.com - 2015-05-31 13:09 -0700
        Re: permuting a JS vector Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-05-31 22:42 +0100
    Re: permuting a JS vector wolfgang zeidler <invalid@invalid.invalid> - 2015-06-01 20:33 +0200
    Re: permuting a JS vector Scott Sauyet <scott.sauyet@gmail.com> - 2015-06-05 13:12 -0700

#27948 — permuting a JS vector

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://repl.it/ with TypeError: recurse.push is not a function

Solutions welcome.

Mark

[toc] | [next] | [standalone]

#27949

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://repl.it/ 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.

[toc] | [prev] | [next] | [standalone]

#27950

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://repl.it/ 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

[toc] | [prev] | [next] | [standalone]

#27951

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/Array/push

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#27953

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://repl.it/ 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

[toc] | [prev] | [next] | [standalone]

#27996

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://repl.it/ 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/rK3/1>.)

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.javascript

csiph-web