arrays - 查找数组组合的中点

Question

我有一个在 Rust 中实现 Iterator 的结构(尽管这个问题可以适用于任何语言)来计算数组的组合。迭代器是用一个初始数组创建的，该数组定义了数组中每个条目的最大值。迭代器的实际代码仍在进行中，因此可能有很多地方可以改进。

例如，如果我使用 Combo::new() 函数创建一个 Combo，并且我给出 set_max 数组，[4,3,2,1]，然后迭代器将生成长度为 4 的数组的所有组合，使得没有条目超过 set_max 中给定的条目。

因此，生成的第一个数组是[0,0,0,1]，然后是[0,0,1,0]，[0,0,1,1], [0,0,2,0], [0,0,2,1], [0,1,0,0] 等。本质上，它一次递增一个条目，直到条目用完为止。然后它会重置它并开始一次递增两个条目。

我希望这个迭代器在某个时候实现 rayon::ParallelIterator，但首先，我相信我需要一种方法将组合的计算分成两半。

如何找到迭代器的中间点，以便将其分成两部分？

找到这个中点后，我对实现拆分函数有了一些想法:添加一个 set_min 数组，该数组指定一个起点，从该起点开始递增条目。但问题的重点是如何找到一般的中点。

#[derive(Clone)]
pub struct Combos {
    pub set_max: Vec<usize>,
    set_current: Vec<usize>,
    size: usize,
}

impl Combos {
    pub fn new(set_max: Vec<usize>) -> Combos {
        Combos {
            set_current: vec![0; set_max.len()],
            size: set_max.iter().fold(1, |acc, x| (x + 1) * acc) - 1,
            set_max: set_max,
        }
    }

    fn increment_combo(&self, length: usize, combo: &[usize]) -> Vec<usize> {
        if let Some(last) = combo.last() {
            if *last == self.set_max[length - 1] {
                let mut v = self.increment_combo(length - 1, &combo[..length - 1]);
                v.push(0);
                return v
            } else {
                let mut v = combo.to_vec();
                v[length - 1] = last + 1;
                return v
            }
        } else {
            return Vec::new()
        }
    }
}

impl Iterator for Combos {
    type Item=Vec<usize>;

    fn next(&mut self) -> Option<Vec<usize>> {
        if self.set_current == self.set_max {
            return None
        }

        self.set_current = self.increment_combo(self.set_max.len(), &self.set_current);
        return Some(self.set_current.clone())
    }
}

Answer 1

只需将数组的第一个值减半即可将操作减半，因为第一个值是算法中最后递增的值(最重要的值):

[4, 3, 2, 1]

可以这样剪:

first part:  [0, 3, 2, 1] -> [1, 3, 2, 1]
second part: [2, 3, 2, 1] -> [3, 3, 2, 1]

因此，这很容易将您的算法减半:使用 [2, 3, 2, 1] 调用第一部分，使用 [4, 3, 2] 调用第二部分, 1] 开头为:[2, 0, 0, 0]。