Add permutations generator #172
Conversation
|
|
||
| Returns a permutation of the specified *source* object (or array) using the specified iterable of *keys*. The returned array contains the corresponding property of the source object for each key in *keys*, in order. For example: |
There was a problem hiding this comment.
This is really good. No detail of the original documentation was lost here. Nice work!
|
|
||
| Returns a permutation of the specified *source* object (or array) using the specified iterable of *keys*. The returned array contains the corresponding property of the source object for each key in *keys*, in order. For example: | ||
| Returns a generator of permutations or a single permutation of the specified *source* object (or array). |
There was a problem hiding this comment.
| Returns a generator of permutations or a single permutation of the specified *source* object (or array). | |
| Returns a single permutation (if *keys* is specified) or a generator of all possible permutations (if *keys* is omitted) of the specified *source* object (or array). |
This language "Returns a generator of permutations or a single permutation of the specified source object (or array)." is ambiguous in terms of "a generator of" possibly being associated with "a single permutation". Meaning, one could interpret this sentence as saying that it returns a generator with a single permutation. To solve this, I suggest to reverse the order, so the generator concept is only introduced in association with the notion of "all possible permutations" (another level of detail I've suggested here). I also suggest that this first line of documentation make it clear the conditions with which either case will happen, so I've included those in parentheses.
It might make sense to also flip the more detailed content to match this ordering, so first
If keys is specified then...
then later
If keys is omitted then...
This would have the additional benefit of backwards compatibility at the documentation level. Meaning, if someone is used to seeing the old content, then let's give them the old content first, then the new content after that.
| } | ||
| } | ||
|
|
||
| // Based on https://github.com/google/guava/blob/f4b3f611c4e49ecaded58dcb49262f55e56a3322/guava/src/com/google/common/collect/Collections2.java#L622-L683 |
There was a problem hiding this comment.
Maybe this link can be moved into the docs?
There was a problem hiding this comment.
Something like.
This implementation was inspired by the permute algorithm in Guava Collections.
| } | ||
|
|
||
| // Based on https://github.com/google/guava/blob/f4b3f611c4e49ecaded58dcb49262f55e56a3322/guava/src/com/google/common/collect/Collections2.java#L622-L683 | ||
| // Apache-2.0 License, Copyright (C) 2008 The Guava Authors. |
There was a problem hiding this comment.
Confusion on licensing here. Not sure how to address, but this comment is super confusing. Does it override the licence for the overall library? Is this code dual licensed with both the library license and this licence here in the comment? I suggest to remove this comment, and somehow come to terms with the fact that you are re-licensing this code/algorithm by submitting this PR.
The original license does not apply to a JavaScript port, I don't think.
|
|
||
| function count(values) { | ||
| let count = 0; | ||
| // eslint-disable-next-line no-unused-vars |
There was a problem hiding this comment.
There must be a way to do this without unused vars?
| @@ -1,6 +1,104 @@ | |||
| const tape = require("tape-await"); | |||
| const d3 = require("../"); | |||
|
|
|||
| //#region Based on https://github.com/google/guava/blob/f4b3f611c4e49ecaded58dcb49262f55e56a3322/guava-tests/test/com/google/common/collect/Collections2Test.java | |||
|
|
|||
| tape("permute(…) permutes zero values", (test) => { | |||
|
We don’t want d3.permute to have a radically different semantics if only a single argument is passed. That’s very confusing. So, this needs a new name. I propose d3.permutations. I’m not sure I see this function reaching the bar of usefulness to merit inclusion in this library. Do you have some practical, applied examples? Given that this is derived from third-party code rather than an original contribution, this would require including the Google Collections Apache license. Also, that algorithm is a little complicated, and is it worth the complexity? I feel it would be simpler and easier to write a fresh implementation of the simpler Heap’s algorithm such as function* permutations(array) {
array = Array.from(array); // defensive copy and convert to array
let i = 0, n = array.length, index = new Uint32Array(n).fill(0);
yield array.slice(); // defensive copy
while (i < n) {
let j = index[i];
if (j < i) {
if ((i & 1) === 0) j = 0;
let t = array[j];
array[j] = array[i];
array[i] = t;
yield array.slice(); // defensive copy
++index[i];
i = 0;
} else {
index[i] = 0;
++i;
}
}
}I guess if it’s that small, there’s not much harm in including it… but I’d still appreciate some applied examples. Another consideration is whether we want to implement an optional r argument, and a d3.combinations method at the same time. For reference, here’s a port of itertools by Jacob Rus, and the Python itertools API reference for itertools.permutations and itertools.combinations. Of course if we’re going to base on implementation on Python’s itertools then we’ll likewise need to add a copy of the PSF license. |
Closes #171.