Skip to content

Instantly share code, notes, and snippets.

Created Oct 8, 2013
Embed
What would you like to do?
Subject: [PATCH] std::vec: Replace each_permutation with a Permutations
iterator
let mut v = [1, 2, 3];
for perm in Permutations::new(v) {
// yields 1 2 3 | 1 3 2 | 3 1 2 | 3 2 1 | 2 3 1 | 2 1 3
}
The Permutations iterator is in-place, which is basically the only way
to match the efficiency of each_permutation, which passed a slice to the
same backing vector each time.
each_permutation did however clone all the elements for each iteration,
which we avoid here by using a much smarter order of permutations.
---
src/libstd/vec.rs | 301 ++++++++++++++++++++++++++++++++----------------------
1 file changed, 181 insertions(+), 120 deletions(-)
diff --git a/src/libstd/vec.rs b/src/libstd/vec.rs
index 4cc5c4f..b7b8fde 100644
--- a/src/libstd/vec.rs
+++ b/src/libstd/vec.rs
@@ -426,56 +426,128 @@ pub fn unzip<T,U>(v: ~[(T, U)]) -> (~[T], ~[U]) {
(ts, us)
}
-/**
- * Iterate over all permutations of vector `v`.
- *
- * Permutations are produced in lexicographic order with respect to the order
- * of elements in `v` (so if `v` is sorted then the permutations are
- * lexicographically sorted).
- *
- * The total number of permutations produced is `v.len()!`. If `v` contains
- * repeated elements, then some permutations are repeated.
- *
- * See [Algorithms to generate
- * permutations](http://en.wikipedia.org/wiki/Permutation).
- *
- * # Arguments
- *
- * * `values` - A vector of values from which the permutations are
- * chosen
- *
- * * `fun` - The function to iterate over the combinations
- */
-pub fn each_permutation<T:Clone>(values: &[T], fun: &fn(perm : &[T]) -> bool) -> bool {
- let length = values.len();
- let mut permutation = vec::from_fn(length, |i| values[i].clone());
- if length <= 1 {
- fun(permutation);
- return true;
- }
- let mut indices = vec::from_fn(length, |i| i);
- loop {
- if !fun(permutation) { return true; }
- // find largest k such that indices[k] < indices[k+1]
- // if no such k exists, all permutations have been generated
- let mut k = length - 2;
- while k > 0 && indices[k] >= indices[k+1] {
- k -= 1;
- }
- if k == 0 && indices[0] > indices[1] { return true; }
- // find largest l such that indices[k] < indices[l]
- // k+1 is guaranteed to be such
- let mut l = length - 1;
- while indices[k] >= indices[l] {
- l -= 1;
- }
- // swap indices[k] and indices[l]; sort indices[k+1..]
- // (they're just reversed)
- indices.swap(k, l);
- indices.mut_slice(k+1, length).reverse();
- // fixup permutation based on indices
- for i in range(k, length) {
- permutation[i] = values[indices[i]].clone();
+/// An Iterator that yields the element swaps needed to produce
+/// a sequence of all possible permutations for an indexed sequence of
+/// elements. Each permutation is only a single swap apart.
+///
+/// The Steinhaus–Johnson–Trotter algorithm is used.
+///
+/// Generates even and odd permutations alternatingly.
+///
+/// After the last generated swap, (0, 1) will return the sequence
+/// to its initial order.
+///
+/// http://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm
+pub struct ElementSwaps {
+ priv sdir: ~[SizeDirection],
+}
+
+impl ElementSwaps {
+ /// Create an `ElementSwaps` iterator for a sequence of `length` elements
+ pub fn new(length: uint) -> ElementSwaps {
+ // Initialize `sdir` with a direction that position should move in
+ // (all negative at the beginning) and the `size` of the
+ // element (equal to the original index).
+ ElementSwaps{
+ sdir: range(0, length)
+ .map(|i| SizeDirection{ size: i, dir: Neg })
+ .to_owned_vec()
+ }
+ }
+}
+
+enum Direction { Pos, Neg }
+
+/// An Index and Direction together
+struct SizeDirection {
+ size: uint,
+ dir: Direction,
+}
+
+impl Iterator<(uint, uint)> for ElementSwaps {
+ #[inline]
+ fn next(&mut self) -> Option<(uint, uint)> {
+ fn new_pos(i: uint, s: Direction) -> uint {
+ i + match s { Pos => 1, Neg => -1 }
+ }
+
+ // Find the index of the largest mobile element:
+ // The direction should point into the vector, and the
+ // swap should be with a smaller `size` element.
+ let max = self.sdir.iter().map(|&x| x).enumerate()
+ .filter(|&(i, sd)|
+ new_pos(i, sd.dir) < self.sdir.len() &&
+ self.sdir[new_pos(i, sd.dir)].size < sd.size)
+ .max_by(|&(_, sd)| sd.size);
+ match max {
+ None => None,
+ Some((i, sd)) => {
+ let j = new_pos(i, sd.dir);
+ self.sdir.swap(i, j);
+
+ // Swap the direction of each larger SizeDirection
+ for x in self.sdir.mut_iter() {
+ if x.size > sd.size {
+ x.dir = match x.dir { Pos => Neg, Neg => Pos };
+ }
+ }
+ Some((i, j))
+ }
+ }
+ }
+}
+
+/// An Iterator that uses `ElementSwaps` to iterate through
+/// all possible permutations of a vector, in place.
+///
+/// The first iteration yields the vector as it was,
+/// then each successive element is the vector with one
+/// swap applied.
+///
+/// When the iterator is exhausted, the vector is swapped one
+/// final time to return into its initial order.
+///
+/// Generates even and odd permutations alternatingly.
+pub struct Permutations<'self, T> {
+ priv swaps: ElementSwaps,
+ priv v: &'self mut [T],
+ priv first: bool,
+ priv done: bool,
+}
+
+impl<'self, T> Permutations<'self, T> {
+ /// Create a `Permutations` iterator, that will take the vector `v`
+ /// and modify it in place for each iteration, each time to
+ /// a new permutation.
+ pub fn new(v: &'self mut [T]) -> Permutations<'self, T> {
+ Permutations{
+ swaps: ElementSwaps::new(v.len()),
+ v: v,
+ first: true,
+ done: false
+ }
+ }
+}
+
+impl<'self, T> Iterator<&'self [T]> for Permutations<'self, T> {
+ #[inline]
+ fn next(&mut self) -> Option<&'self [T]> {
+ if self.first {
+ self.first = false;
+ return Some(self.v.as_slice())
+ }
+ match self.swaps.next() {
+ None => {
+ if !self.done && self.v.len() > 1 {
+ self.v.swap(0, 1)
+ }
+ self.done = true;
+ None
+ },
+ Some((a, b)) => {
+ self.v.swap(a, b);
+ Some(self.v.as_slice())
+ }
}
}
}
@@ -2866,28 +2938,6 @@ mod tests {
}
#[test]
- fn test_each_permutation() {
- let mut results: ~[~[int]];
-
- results = ~[];
- do each_permutation([]) |v| { results.push(v.to_owned()); true };
- assert_eq!(results, ~[~[]]);
-
- results = ~[];
- do each_permutation([7]) |v| { results.push(v.to_owned()); true };
- assert_eq!(results, ~[~[7]]);
-
- results = ~[];
- do each_permutation([1,1]) |v| { results.push(v.to_owned()); true };
- assert_eq!(results, ~[~[1,1],~[1,1]]);
-
- results = ~[];
- do each_permutation([5,2,0]) |v| { results.push(v.to_owned()); true };
- assert!(results ==
- ~[~[5,2,0],~[5,0,2],~[2,5,0],~[2,0,5],~[0,5,2],~[0,2,5]]);
- }
-
- #[test]
fn test_zip_unzip() {
let z1 = ~[(1, 4), (2, 5), (3, 6)];
@@ -2899,6 +2949,62 @@ mod tests {
}
#[test]
+ fn test_permutations() {
+ use hashmap;
+ {
+ let mut v: [int, ..0] = [];
+ let mut it = Permutations::new(v);
+ assert_eq!(it.next(), Some(&[]));
+ assert_eq!(it.next(), None);
+ }
+ {
+ let mut v = [~"Hello"];
+ let mut it = Permutations::new(v);
+ assert_eq!(it.next(), Some(&[~"Hello"]));
+ assert_eq!(it.next(), None);
+ }
+ {
+ let mut v = [@1, @2];
+ let mut it = Permutations::new(v);
+ assert_eq!(it.next(), Some(&[@1, @2]));
+ assert_eq!(it.next(), Some(&[@2, @1]));
+ assert_eq!(it.next(), None);
+ assert_eq!(v, [@1, @2]);
+ }
+ {
+ let mut v = [1, 2, 3];
+ let mut it = Permutations::new(v);
+ assert_eq!(it.next(), Some(&[1,2,3]));
+ assert_eq!(it.next(), Some(&[1,3,2]));
+ assert_eq!(it.next(), Some(&[3,1,2]));
+ assert_eq!(it.next(), Some(&[3,2,1]));
+ assert_eq!(it.next(), Some(&[2,3,1]));
+ assert_eq!(it.next(), Some(&[2,1,3]));
+ assert_eq!(it.next(), None);
+ assert_eq!(v, [1, 2, 3]);
+ assert_eq!(it.next(), None);
+ assert_eq!(v, [1, 2, 3]);
+ }
+ {
+ // check that we have N! unique permutations
+ let mut set = hashmap::HashSet::new();
+ let mut v = ['A', 'B', 'C', 'D', 'E', 'F'];
+ set.extend(&mut Permutations::new(v));
+ assert_eq!(set.len(), 2 * 3 * 4 * 5 * 6);
+ }
+
+ {
+ // check that we have N!/2 unique permutations
+ // because there is one duplicated element
+ let mut set = hashmap::HashSet::new();
+ let mut v = [('A',1), ('A', 2), ('B', 1), ('B', 2), ('B', 2)];
+ assert_eq!(Permutations::new(v).len(), 2 * 3 * 4 * 5);
+ set.extend(&mut Permutations::new(v));
+ assert_eq!(set.len(), 2 * 3 * 4 * 5 / 2);
+ }
+ }
+
+ #[test]
fn test_position_elem() {
assert!([].position_elem(&1).is_none());
@@ -3191,15 +3297,14 @@ mod tests {
#[test]
#[should_fail]
fn test_permute_fail() {
- let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
+ let mut v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
let mut i = 0;
- do each_permutation(v) |_elt| {
+ for _ in Permutations::new(v) {
if i == 2 {
fail!()
}
i += 1;
- true
- };
+ }
}
#[test]
@@ -3512,50 +3617,6 @@ mod tests {
}
#[test]
- fn test_permutations0() {
- let values = [];
- let mut v : ~[~[int]] = ~[];
- do each_permutation(values) |p| {
- v.push(p.to_owned());
- true
- };
- assert_eq!(v, ~[~[]]);
- }
-
- #[test]
- fn test_permutations1() {
- let values = [1];
- let mut v : ~[~[int]] = ~[];
- do each_permutation(values) |p| {
- v.push(p.to_owned());
- true
- };
- assert_eq!(v, ~[~[1]]);
- }
-
- #[test]
- fn test_permutations2() {
- let values = [1,2];
- let mut v : ~[~[int]] = ~[];
- do each_permutation(values) |p| {
- v.push(p.to_owned());
- true
- };
- assert_eq!(v, ~[~[1,2],~[2,1]]);
- }
-
- #[test]
- fn test_permutations3() {
- let values = [1,2,3];
- let mut v : ~[~[int]] = ~[];
- do each_permutation(values) |p| {
- v.push(p.to_owned());
- true
- };
- assert_eq!(v, ~[~[1,2,3],~[1,3,2],~[2,1,3],~[2,3,1],~[3,1,2],~[3,2,1]]);
- }
-
- #[test]
fn test_vec_zero() {
use num::Zero;
macro_rules! t (
--
1.8.9
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment