Function unsafe_x_permutation

pub unsafe fn unsafe_x_permutation<'a, T>(
    d: &'a [T],
    result: *mut [&'a T],
    t: impl FnMut(&[&T]) -> bool,
    cb: impl FnMut(),
)

A lexicographic ordered permutation based on “Algoritm X” published by Donald E. Knuth. page 20.

If order is not important, consider using heap permutation function instead. This function is 3 times slower than heap heap permutation in uncontroll test environment.

The algorithm work by simulate tree traversal where some branch can be skip altogether. This is archive by provided t function that take slice of partial result as parameter. If the partial result needed to be skip, return false. Otherwise, return true and the algorithm will call this function again when the branch is descended deeper. For example: First call to t may contain [1]. If t return true, it will be called again with [1, 2]. If it return true, and there’s leaf node, cb will be called with [1, 2]. On the other hand, if t is called with [1, 3] and it return false, it won’t call the callback. If t is called with [4] and it return false, it won’t try to traverse deeper even if there’re [4, 5], or [4, 6]. It will skip altogether and call t with [7]. The process goes on until every branch is traversed.

Example

See x_permutation document for example. It’s the same except the way it return result.

Parameters

• d : &[T] - A data to get a permutation.
• result : *mut [&T] - A result container. The result will be overwritten on each call to callback.
• t : FnMut(&[&T]) -> bool - A function for checking whether to traverse the branch. It shall return true if the branch need to be traversed.
• cb : FnMut() - A callback function that notify caller that new result is available.

Safety

This function is unsafe to used. This function store result into raw pointer thus all unsafe Rust condition may applied. For example, it may seg fault if pointer is invalid. It may cause datarace. It may leak memory.

Rationale

This function permit sharing data to other without cost by sacrifice the safety. For safely share result in single thread, consider using x_permutation_cell. For safely share result in multi-threads, consider using x_permutation_sync. Both functions have some cost due to additional safety check.