compound-factor-iter 概述

此包提供迭代器类型，用于遍历从组合多个离散因子的函数中所有可能的输出排列。

它是用来做什么的？例如？

想象你有一个潜在单词，表示为字母概率的集合。单词中的每个字母都是一个概率分布，其和为 1.0。所以第一个字母可能是 ['a'=70%, 'b'=30%]，以此类推。现在你想要找到最可能的单词，即字母概率的排列？

听起来很简单，只需对每个单独字母的概率列表进行排序，并取每个字母的第一个（也就是因子）。那么第二最可能的总体单词是什么？找到第二最可能的字母和最可能的字母之间的概率最小差异，并用那个字母替换。那么第1000个最可能的呢？嗯嗯嗯……？这就是这个包的作用。

用法

use compound_factor_iter::*;

fn idx_to_char(idx: usize) -> char {
    char::from_u32((idx+97) as u32).unwrap()
}

fn char_to_idx(c: char) -> usize {
    (c as usize) - 97
}

/// "bat", "cat", "hat", "bam", "cam", "ham"
let mut letter_probs = [[0.0; 26]; 3]; //3 letters, 26 possibilities each
letter_probs[0][char_to_idx('b')] = 0.4;
letter_probs[0][char_to_idx('c')] = 0.35;
letter_probs[0][char_to_idx('h')] = 0.25;
letter_probs[1][char_to_idx('a')] = 1.0;
letter_probs[2][char_to_idx('m')] = 0.35;
letter_probs[2][char_to_idx('t')] = 0.65;

let product_fn = |probs: &[f32]|{

    let mut new_prob = 1.0;
    for prob in probs.into_iter() {
        new_prob *= prob;
    }

    if new_prob > 0.0 {
        Some(new_prob)
    } else {
        None
    }
};

for (permutation, prob) in OrderedPermutationIter::new(letter_probs.iter(), &product_fn) {
    let word: String = permutation.into_iter().map(|idx| idx_to_char(idx)).collect();
    println!("permutation = {}, prob = {}", word, prob);
}

使用[ManhattanPermutationIter]或[RadixPermutationIter]的方式完全相同。

for (permutation, prob) in ManhattanPermutationIter::new(letter_probs.iter(), &product_fn) {
    let word: String = permutation.into_iter().map(|idx| idx_to_char(idx)).collect();
    println!("permutation = {}, prob = {}", word, prob);
}

单调性要求

此包中的迭代器可用于多种以离散值作为输入的函数，但必须满足一个条件：任何输入因子的值增加必须导致组合函数的输出值增加。换句话说，不允许有负面影响的因素。

为什么有三个不同的迭代器？

这三种迭代器类型具有完全相同的接口，可以互换使用，但它们的性能和品质特性却大相径庭。

OrderedPermutationIter

有序排列迭代器[OrderedPermutationIter]保证按照从高到低的顺序返回结果。然而，它可能非常昂贵，因为它需要在每个步骤中调用组合函数闭包，潜在地需要调用combination_fn，次数达到n*2^n，其中n是因子数量。

由于成本，有序排列迭代器仅适用于无法接受无序结果的场景。

曼哈顿排列迭代器

曼哈顿排列迭代器[ManhattanPermutationIter]是一个固定成本的迭代器，它使用简单的启发式算法系统地从已知的最佳排列向外探索。与有序排列迭代器不同，曼哈顿排列迭代器可能返回无序的结果，但是启发式算法确保随着迭代的进行，结果主要呈现下降趋势。

“曼哈顿”这个词来源于排列尝试的顺序是由其与单个最佳排列的曼哈顿距离确定的。

基数排列迭代器

基数排列迭代器[RadixPermutationIter]是另一个作为混合基数数空间中计数器的固定成本迭代器。

曼哈顿排列迭代器通常会产生更均匀的因子空间覆盖，而基数排列迭代器则在小区间内提供更有序的序列。当某些因子对函数结果的影响远大于其他因子时，[基数排列迭代器]是合适的。这可能是由于函数本身或输入因子值造成的。

建议尝试两种固定成本迭代器，以确定最适合您情况的最佳迭代器。例如，在search_dict_test（来自tests.rs文件）中，曼哈顿排列迭代器可以在32K次迭代中从字典中找到目标单词，而基数排列迭代器则需要1.8M次迭代。然而，在non_multiplicative_fn_test中，基数排列迭代器产生的序列与真实情况更吻合，而曼哈顿排列迭代器则不是。

字母分布功能

通过启用--features letter_distribution功能，可以得到一个方便的对象来表示字母分布，就像上面示例中描述的那样。这在许多测试中都被使用。

更多示例

更多示例可以通过查看tests.rs文件获得。

查看search_dict_test()函数，了解使用letter_distribution的示例。

未来工作

• 可逆选项。目前所有迭代器都是从最高值迭代到最低值。在某些情况下，可能希望从最低值迭代到最高值。