返回所有排列的函数

Question

我想创建一个函数来返回一个序列的所有排列。我从 Rosetta Code 中拿了一个例子，并试图用 Rust 编写它，但它不起作用。当我尝试修复它时，我要么导致溢出，要么再次破坏它。这段代码有一个算术溢出错误：

fn permutations_(sequence: Vec<i32>) -> Vec<Vec<i32>> {
    if sequence.len() == 0 {
        let x: Vec<Vec<i32>> = vec![vec![]];
        return x
    }

    let mut result: Vec<Vec<i32>> = Vec::new();

    for (i, item) in permutations_(to_vec(&sequence[0..sequence.len() - 1])).iter().enumerate() {

        let mut n = reverse(&(0..item.len() + 1).collect::<Vec<usize>>());

        if i % 2 != 0 {
            n = (0..item.len() + 1).collect::<Vec<usize>>();
        }

        for k in n {
            let mut items = Vec::new();

            for x in &item[0..k] {
                items.push(*x);
            }

            items.push(item[item.len() - 1]);

            for x in &item[k..item.len()] {
                items.push(*x);
            }

            result.push(items);
        }
    }

    result
}

如果有更好的方法来做到这一点，我想知道，否则我需要关于如何解决这个问题的想法。

Answer 1

看一看permutohedron板条箱，它可以满足您的需求。看看它的基准测试或测试，看看你可以如何使用它。

基本上，您将 a&mut数据用于 a 的构造Heap，然后您可以调用next_permutation()它以获取Option对置换数据的可变引用。这是一个Option使None能信号，有没有剩余的排列。请注意，Heap也实现了Iterator，因此您也可以使用for permutation in heap { ... }。