libreda-logic 0.0.3

// SPDX-FileCopyrightText: 2022 Thomas Kramer <code@tkramer.ch>
//
// SPDX-License-Identifier: AGPL-3.0-or-later

//! Helpers for iterating through all permutations of `n` elements by swapping exactly two elements in each step.
//!
//! The generated permutations form a 'gray code', each neighbouring permutations differ in the minimal amount possible.
//! Implements Shimon Even's algorithm.

use smallvec::SmallVec;

/// Generate a sequence of element swaps which cycles through all permutations of `n` elements.
///
/// # References
/// * Shimon Even's algorithm
pub fn permutation_swaps(n: usize) -> PermutationSwaps {
    let mut swaps = permutation_swaps_cyclic(n);
    // Skip the last swap:
    swaps.remaining_length = swaps.remaining_length.saturating_sub(1);

    swaps
}

/// Generate a sequence of element swaps which cycles through all permutations of `n` elements
/// and leads to the original element again.
///
/// # References
/// * Shimon Even's algorithm
pub fn permutation_swaps_cyclic(n: usize) -> PermutationSwaps {
    // First element has no direction, all others have negative direction.
    let elements = (0..n)
        .map(|i| Element {
            id: i as u8,
            direction: if i == 0 {
                Direction::None
            } else {
                Direction::Down
            },
        })
        .collect();

    let num_permutations: usize = (1..n + 1).product();

    PermutationSwaps {
        state: elements,
        remaining_length: num_permutations,
    }
}

/// Iterator over swap-indices which step through all permutations of `n` elements.
#[derive(Clone)]
pub struct PermutationSwaps {
    state: SmallVec<[Element; 16]>,
    remaining_length: usize,
}

impl Iterator for PermutationSwaps {
    type Item = (usize, usize);

    fn next(&mut self) -> Option<Self::Item> {
        let elements = &mut self.state;
        let n = elements.len();

        // Find greatest element with non-zero direction.
        if let Some((idx, greatest_nonzero)) = elements
            .iter()
            .enumerate()
            .filter(|(_pos, e)| e.direction != Direction::None)
            .max_by_key(|(_pos, e)| e.id)
        {
            assert!(self.remaining_length > 0);

            let output; // Store the swap indices which are returned in this iteration.

            let chosen_id = greatest_nonzero.id;
            let move_direction = greatest_nonzero.direction.to_isize();

            // Swap with the element in the indicated direction.
            let chosen_index = {
                let other_idx = ((idx as isize) + move_direction) as usize; // Index of the element in the indicated direction.
                elements.swap(idx, other_idx);
                // Store swap.
                output = (idx, other_idx);
                other_idx
            };

            {
                // "If this causes the chosen element to reach the first or last position within the permutation,
                // or if the next element in the same direction is greater than the chosen element,
                // the direction of the chosen element is set to zero"
                let reached_end = chosen_index == 0 || chosen_index == n - 1;
                let next_index = ((chosen_index as isize) + move_direction) as usize;
                let next_element_is_greater = || elements[next_index].id > chosen_id;
                if reached_end || next_element_is_greater() {
                    elements[chosen_index].direction = Direction::None;
                }
            }

            // For each element greater than the chosen set the direction of motion towards the chosen element.
            elements
                .iter_mut()
                .enumerate()
                .filter(|(_i, e)| e.id > chosen_id)
                .for_each(|(i, e)| {
                    let direction_towards_chosen =
                        ((chosen_index as isize) - (i as isize)).signum();
                    e.direction = Direction::from_isize(direction_towards_chosen);
                });

            self.remaining_length -= 1;
            Some(output)
        } else {
            assert!(self.remaining_length <= 1);
            if self.remaining_length == 1 {
                // Append a last swap. It permutes the elements back to the original state.
                // TODO: This could be solved in a neater way probably.
                self.remaining_length -= 1;
                Some((0, 1))
            } else {
                // Iterator is finished.
                None
            }
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.remaining_length, Some(self.remaining_length))
    }
}

/// Motion direction of an element.
#[derive(Clone, PartialEq, Eq)]
enum Direction {
    /// Not marked as moving.
    None,
    /// Move to lower indices.
    Down,
    /// Move to higher indices.
    Up,
}

impl Direction {
    fn to_isize(&self) -> isize {
        match self {
            Direction::None => 0,
            Direction::Down => -1,
            Direction::Up => 1,
        }
    }

    fn from_isize(d: isize) -> Self {
        match d {
            -1 => Direction::Down,
            0 => Direction::None,
            1 => Direction::Up,
            _ => panic!("invalid value for direction"),
        }
    }
}

/// Element in the permuted array.
#[derive(Clone)]
struct Element {
    /// Original index of the element in the array.
    /// An `u8` can be used because 255! is already so large that it is completely unfeasible to generate all permutations of 255 elements anyway.
    id: u8,
    /// Indicated motion direction.
    direction: Direction,
}

#[test]
fn test_shimon_even_algorithm() {
    let mut arr = [1, 2, 3, 4, 5, 6];

    let num_permutations: usize = (1..arr.len() + 1).product();

    let mut all_elements = std::collections::HashSet::new();
    all_elements.insert(arr.clone());

    let swaps = permutation_swaps(arr.len());
    for (i, j) in swaps {
        arr.swap(i, j);
        all_elements.insert(arr.clone());
    }

    assert_eq!(all_elements.len(), num_permutations);
}

#[test]
fn test_permutation_swaps_cyclic() {
    let mut arr = [1, 2, 3, 4, 5];
    let swaps = permutation_swaps_cyclic(arr.len());
    for (i, j) in swaps {
        arr.swap(i, j);
    }
    assert_eq!(arr, [1, 2, 3, 4, 5]);
}