Make sure .sample()'s result is randomized in more cases (#302)
Samples which retain elements from early in the input would have those
elements in the same order as the input. As the sample size approaches
the size of the input, the ordering was more noticeably correlated to the
input order.
Use random indexes for the initial unconditionally added elements before
the later elements are selected into random indexes. This allows the
output order to be consistently uncorrelated with the input order, even
for samples of the entire input.
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 7f56df0..c27f014 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,6 +1,7 @@
## 1.19.0-wip
- Adds `shuffled` to `IterableExtension`.
+- Shuffle `IterableExtension.sample` results.
## 1.18.0
diff --git a/lib/src/iterable_extensions.dart b/lib/src/iterable_extensions.dart
index 6e0be3c..7d7b2e0 100644
--- a/lib/src/iterable_extensions.dart
+++ b/lib/src/iterable_extensions.dart
@@ -32,15 +32,22 @@
RangeError.checkNotNegative(count, 'count');
var iterator = this.iterator;
var chosen = <T>[];
- for (var i = 0; i < count; i++) {
+ random ??= Random();
+ while (chosen.length < count) {
if (iterator.moveNext()) {
- chosen.add(iterator.current);
+ var nextElement = iterator.current;
+ var position = random.nextInt(chosen.length + 1);
+ if (position == chosen.length) {
+ chosen.add(nextElement);
+ } else {
+ chosen.add(chosen[position]);
+ chosen[position] = nextElement;
+ }
} else {
return chosen;
}
}
var index = count;
- random ??= Random();
while (iterator.moveNext()) {
index++;
var position = random.nextInt(index);
diff --git a/test/extensions_test.dart b/test/extensions_test.dart
index d7a59a0..229d6e2 100644
--- a/test/extensions_test.dart
+++ b/test/extensions_test.dart
@@ -1175,6 +1175,31 @@
expect(other, some);
}
});
+ group('shuffles results', () {
+ late Random random;
+ late Iterable<int> input;
+ setUp(() async {
+ input = iterable([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
+ random = Random(12345);
+ });
+ test('for partial samples of input', () {
+ var result = input.sample(9, random);
+ expect(result.length, 9);
+ expect(result.isSorted(cmpInt), isFalse);
+ });
+ test('for complete samples of input', () {
+ var result = input.sample(10, random);
+ expect(result.length, 10);
+ expect(result.isSorted(cmpInt), isFalse);
+ expect(UnorderedIterableEquality().equals(input, result), isTrue);
+ });
+ test('for overlengthed samples of input', () {
+ var result = input.sample(20, random);
+ expect(result.length, 10);
+ expect(result.isSorted(cmpInt), isFalse);
+ expect(UnorderedIterableEquality().equals(input, result), isTrue);
+ });
+ });
});
group('.elementAtOrNull', () {
test('empty', () async {
