https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Sattolo's_algorithm

There is an error with this repository's Renovate configuration that needs to be fixed. As a precaution, Renovate will stop PRs until it is resolved.

Error type: undefined. Note: this is a nested preset so please contact the preset author if you are unable to fix it yourself.

This issue provides visibility into Renovate updates and their statuses. Learn more

Open

These updates have all been created already. Click a checkbox below to force a retry/rebase of any.

• ⬆️ deps: Upgrade dependency xo to v0.45.0

• Check this box to trigger a request for Renovate to run again on this repository

It is possible to implement a bitreversal generator in O(n) time using half the space requirement of the bitreversal array constructor currently implemented.

A first idea is to call bitreversal( n ) which will generate an array of size n and then yield the different values of bitreversal( 2n ) from this list.

let sigma = bitreversalarray( n ) ;
for ( s of sigma ) yield s << 1 ;
for ( s of sigma ) yield s << 1 + 1 ;

A second idea is to go for a full generator implementation using a FIFO queue. Note that the recursion stack uses an additional O(log n) space.

let queue = new Queue( ) ;
for ( s of bitreversal( n ) ) yield queue.put( s << 1 ) ;
for ( let i = 0 ; i < n ; ++i ) yield queue.get( ) + 1 ;

Finally, it is possible to implement a bitreversal generator running in O(n log n) time and using O(log n) space.

for ( s of bitreversal( n ) ) yield s << 1 ;
for ( s of bitreversal( n ) ) yield s << 1 + 1 ;