ep_core/
random_permutation.rs

1// Copyright (c) 2019 Alain Brenzikofer
2// This file is part of Encointer
3//
4// Encointer is free software: you can redistribute it and/or modify
5// it under the terms of the GNU General Public License as published by
6// the Free Software Foundation, either version 3 of the License, or
7// (at your option) any later version.
8//
9// Encointer is distributed in the hope that it will be useful,
10// but WITHOUT ANY WARRANTY; without even the implied warranty of
11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12// GNU General Public License for more details.
13//
14// You should have received a copy of the GNU General Public License
15// along with Encointer.  If not, see <http://www.gnu.org/licenses/>.
16
17//! A simple trait that allows pseudo-random permutations on arbitrary `vec`s.
18
19use crate::RandomNumberGenerator;
20use sp_runtime::traits::Hash;
21
22#[cfg(not(feature = "std"))]
23use sp_std::vec::Vec;
24
25/// Pseudo-random permutation. It's as secure as the combination of the seed with which the
26/// RandomNumberGenerator is constructed and the hash function it uses to cycle the elements.
27pub trait RandomPermutation {
28	type Item;
29
30	/// Random permutation from an array of elements. This is guaranteed to return `Some` except
31	/// in the case that `self` is empty.
32	fn random_permutation<Hashing: Hash>(
33		self,
34		random: &mut RandomNumberGenerator<Hashing>,
35	) -> Option<Vec<Self::Item>>;
36}
37
38impl<T> RandomPermutation for Vec<T> {
39	type Item = T;
40
41	fn random_permutation<Hashing: Hash>(
42		self,
43		random: &mut RandomNumberGenerator<Hashing>,
44	) -> Option<Vec<T>> {
45		// Make it `mut`. Rust does not allow `mut self` as argument because the semantics for
46		// the caller is the same: the method consumes `self`.
47		let mut input = self;
48
49		if input.is_empty() {
50			None
51		} else {
52			let size = input.len();
53			let mut r = Vec::with_capacity(size);
54
55			for i in 1..=size {
56				// swap remove is O(1)
57				r.push(input.swap_remove(random.pick_usize(size - i)));
58			}
59			Some(r)
60		}
61	}
62}
63
64#[cfg(test)]
65mod tests {
66	use super::*;
67	use sp_runtime::traits::BlakeTwo256;
68
69	#[test]
70	fn random_permutation_works() {
71		let mut random_source =
72			RandomNumberGenerator::<BlakeTwo256>::new(BlakeTwo256::hash(b"my_seed"));
73		let mut random_source_2 =
74			RandomNumberGenerator::<BlakeTwo256>::new(BlakeTwo256::hash(b"my_seed2"));
75		let input = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
76
77		assert_eq!(
78			input.clone().random_permutation(&mut random_source),
79			Some(vec![5, 9, 7, 4, 6, 8, 2, 3, 1, 10])
80		);
81
82		// second time should yield other output
83		assert_eq!(
84			input.clone().random_permutation(&mut random_source),
85			Some(vec![9, 8, 3, 5, 6, 2, 10, 4, 7, 1])
86		);
87
88		// different seed, different output
89		assert_eq!(
90			input.random_permutation(&mut random_source_2),
91			Some(vec![1, 7, 8, 9, 2, 3, 10, 5, 4, 6])
92		);
93
94		assert_eq!(Vec::<u8>::new().random_permutation(&mut random_source_2), None)
95	}
96}
ep_core/random_permutation.rs

ep_core/
random_permutation.rs
