Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit a4896cf

Browse filesBrowse files
make-github-pseudonymous-againmake-github-pseudonymous-again
committed
✨ feat(shuffled): First draft.
This allows to shuffle iterables while consuming them. Fixes #59.
1 parent e26ca00 commit a4896cf
Copy full SHA for a4896cf

File tree

6 files changed

+123
-4
lines changed
Filter options

6 files changed

+123
-4
lines changed

‎README.md

Copy file name to clipboardExpand all lines: README.md
+4Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,10 @@ Randomness algorithms for JavaScript.
1212
See [docs](https://aureooms.github.io/js-random).
1313
Parent is [@aureooms/js-algorithms](https://aureooms.github.io/js-algorithms).
1414

15+
> :warning: Depending on your environment, the code may require
16+
> `regeneratorRuntime` to be defined, for instance by importing
17+
> [regenerator-runtime/runtime](https://www.npmjs.com/package/regenerator-runtime).
18+
1519
```js
1620
import {
1721
randint , // randint(i, j) -> [i, j[ \cap ZZ

‎doc/manual/usage.md

Copy file name to clipboard
+7-4Lines changed: 7 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,9 @@
11
# Usage
2-
The code needs a ES2015+ polyfill to work, for example
3-
[regenerator-runtime/runtime](https://babeljs.io/docs/usage/polyfill).
2+
3+
> :warning: Depending on your environment, the code may require
4+
> `regeneratorRuntime` to be defined, for instance by importing
5+
> [regenerator-runtime/runtime](https://www.npmjs.com/package/regenerator-runtime).
6+
47
```js
58
require( 'regenerator-runtime/runtime' ) ;
69
// or
@@ -9,7 +12,7 @@ import 'regenerator-runtime/runtime.js' ;
912

1013
Then
1114
```js
12-
const random = require( '@aureooms/js-random' ) ;
15+
const { ... } = require( '@aureooms/js-random' ) ;
1316
// or
14-
import * as random from '@aureooms/js-random' ;
17+
import { ... } from '@aureooms/js-random' ;
1518
```

‎src/api/shuffled.js

Copy file name to clipboard
+13Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
import _fisheryates_inside_out from '../kernel/_fisheryates_inside_out.js';
2+
import randint from './randint.js';
3+
4+
/**
5+
* Given an input iterable, constructs an array containing the elements of the
6+
* input shuffled uniformly at random.
7+
*
8+
* @function
9+
* @param {Iterable} iterable The input iterable.
10+
* @return {Array} The constructed array.
11+
*/
12+
const shuffled = _fisheryates_inside_out(randint);
13+
export default shuffled;

‎src/index.js

Copy file name to clipboardExpand all lines: src/index.js
+2Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,8 +5,10 @@ export {default as random} from './api/random.js';
55
export {default as randrange} from './api/randrange.js';
66
export {default as sample} from './api/sample.js';
77
export {default as shuffle} from './api/shuffle.js';
8+
export {default as shuffled} from './api/shuffled.js';
89
export {default as _choice} from './kernel/_choice.js';
910
export {default as _fisheryates} from './kernel/_fisheryates.js';
11+
export {default as _fisheryates_inside_out} from './kernel/_fisheryates_inside_out.js';
1012
export {default as _randfloat} from './kernel/_randfloat.js';
1113
export {default as _randint} from './kernel/_randint.js';
1214
export {default as _shuffle} from './kernel/_shuffle.js';

‎src/kernel/_fisheryates_inside_out.js

Copy file name to clipboard
+62Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
/**
2+
* Shuffle elements of an iterable using an inside-out implementation of the
3+
* Fisher-Yates method.
4+
*
5+
* One can observe that if the input contains n elements, the loop has exactly
6+
* n! possible outcomes: one for the first iteration, two for the second, three
7+
* for the third, etc., the number of outcomes of a loop being the product of
8+
* the number of outcomes for each iteration. Given a perfect randint function,
9+
* each iteration's outcomes are equally likely, and independent of other
10+
* iterations outcomes. The proof below shows that these outcomes are
11+
* distinct.
12+
*
13+
* To see that this method yields the correct result (assume perfect randint):
14+
* 1. Observe that it is correct when the input is empty.
15+
* 2. By induction:
16+
* - Induction hypothesis: assume it is correct when the input consists of
17+
* n elements.
18+
* - We almost insert the (n+1)th element at one of the n+1 possible
19+
* insertion position in the output array. Almost because we move the
20+
* element that is at the insertion position at the end instead of
21+
* shifting the elements right of the insertion position to make room for
22+
* the inserted element.
23+
* - Ideally, since we inserted the last element at one of the n+1
24+
* positions, we would like that the elements inserted earlier form one
25+
* of n! permutations uniformly at random after moving the element under
26+
* the insertion position. This is true because the permutations that we
27+
* obtain after this move are in one-to-one correspondance with the n!
28+
* distinct permutations that can be obtained before the move. These are
29+
* equally likely to be produced by the induction hypothesis.
30+
*
31+
* @param {Function} randint The randint function.
32+
* @return {Function} The sampling function.
33+
*/
34+
const _fisheryates_inside_out = (randint) => {
35+
/**
36+
* Given an input iterable, constructs an array containing the elements of
37+
* the input shuffled uniformly at random.
38+
*
39+
* @param {Iterable} iterable The input iterable.
40+
* @param {Array} [output=[]] The constructed array.
41+
* @return {Array} The constructed array.
42+
*/
43+
const shuffled = (iterable, output = []) => {
44+
let n = 0;
45+
for (const item of iterable) {
46+
const i = randint(-1, n);
47+
if (i === -1) output.push(item);
48+
else {
49+
output.push(output[i]);
50+
output[i] = item;
51+
}
52+
53+
++n;
54+
}
55+
56+
return output;
57+
};
58+
59+
return shuffled;
60+
};
61+
62+
export default _fisheryates_inside_out;

‎test/src/shuffled.js

Copy file name to clipboard
+35Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
import test from 'ava';
2+
import {shuffled, _fisheryates_inside_out, randint} from '../../src/index.js';
3+
4+
import {list, range, sorted} from '@aureooms/js-itertools';
5+
import {increasing} from '@aureooms/js-compare';
6+
7+
const macro = (t, _, shuffle, i, j) => {
8+
const input = list(range(i, j));
9+
const output = shuffled(range(i, j));
10+
t.is(output.length, input.length);
11+
t.deepEqual(sorted(increasing, output), sorted(increasing, input));
12+
};
13+
14+
macro.title = (title, shuffle_name, _, i, j) =>
15+
title || `[${n}] shuffled ( ${shuffle_name}, ${i}, ${j} )`;
16+
17+
const n = 100;
18+
19+
const params = [
20+
[0, n],
21+
[20, n],
22+
[0, n - 20],
23+
[10, n - 10],
24+
];
25+
26+
const algorithms = [
27+
['inside-out Fisher-Yates', _fisheryates_inside_out(randint)],
28+
['API', shuffled],
29+
];
30+
31+
for (const [name, algorithm] of algorithms) {
32+
for (const [i, j] of params) {
33+
test(macro, name, algorithm, i, j);
34+
}
35+
}

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.