Module aoc_search::permutations

source ·
Expand description

Generate permutations of usize from 0 .. len.

The main functionality is provided by the PermutationsHelper struct.

Designed to be used with a indexed list of items of which to generate permutations, eg in a Vec or similar. Provide the number of items when calling PermutationsHelper::new, then call next in a loop, aborting if it returns false. After calling next, the indexes are available by treating this struct as a slice via the Deref trait.

Examples

Basic usage:

let mut perms_helper = PermutationsHelper::new (2);
assert_eq! (true, perms_helper.next ());
assert_eq! (& [0, 1], & * perms_helper);
assert_eq! (true, perms_helper.next ());
assert_eq! (& [1, 0], & * perms_helper);
assert_eq! (false, perms_helper.next ());

This struct doesn’t implement Iterator so that we avoid allocating a Vec or similar for every iteration. It can easily be wrapped as one if needed:

let mut perms_helper = PermutationsHelper::new (2);
let mut perms_iter = iter::from_fn (move ||
  perms_helper.next ().then (|| perms_helper.to_vec ()));
assert_eq! (Some (vec! [0, 1]), perms_iter.next ());
assert_eq! (Some (vec! [1, 0]), perms_iter.next ());
assert_eq! (None, perms_iter.next ());

A more typical example is generating permutations of indexes into a Vec, performing a calculation based on the items in that order, and finally performing some type of search or aggregation over the results:

let items = vec! [ 49_u64, 93, 51, 45, 26, 73, 20, 80 ];
let mut perms_helper = PermutationsHelper::new (items.len ());
let calc_iter = iter::from_fn (move ||
  perms_helper.next ().then (|| perms_helper.iter ()
    .map (|& idx| items [idx])
    .fold (0, |sum, item| sum * 100 + item)));
assert_eq! (9380735149452620, calc_iter.clone ().max ().unwrap ());
assert_eq! (2026454951738093, calc_iter.clone ().min ().unwrap ());

Algorithm

This implements a “classic” algorithm described on Wikipedia, which produces results in lexicographical order. The alogirthm starts with the items in order, then applies the following steps to generate subsequent iterations:

  • Find the highest index idx_0 where items [idx_0] < items [idx_0 + 1]
  • Find the highest index idx_1 where idx_0 < idx_1 && items [idx_0] < items [idx_1]
  • Swap items [idx_0] and items [idx_1]
  • Reverse the order of items [idx_0 + 1 .. ]

Structs