gistfile1.txt

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