具有可变长度计数的Rust迭代工具组合

nkhmeac6  于 2022-11-24  发布在  其他
关注(0)|答案(2)|浏览(132)

我想计算一个向量的组合。
我可以使用itertools::Itertools:combinations特征轻松地做到这一点,如下所示:

vec![1, 2, 3].iter().combinations(2).for_each(|x| {
    println!("{:?}", x);
});

但是我想指定组合长度以及这些长度的计数。

values = [0, 1, 2, 3, 4]

# 1 group with a length of 3 and 1 group with a length of 2
len_counts = { 3: 1, 2: 1 }

combinations = [
    [{0, 1, 2}, {3, 4}]
    [{0, 1, 3}, {2, 4}]
    [{0, 1, 4}, {2, 3}]
    [{0, 2, 3}, {1, 4}]
    [{0, 2, 4}, {1, 3}]
    [{0, 3, 4}, {1, 2}]
    [{1, 2, 3}, {0, 4}]
    [{1, 2, 4}, {0, 3}]
    [{1, 3, 4}, {0, 2}]
    [{2, 3, 4}, {0, 1}]
]

我希望它是惰性加载和尽可能干净。我试图得到这个输出了一段时间,但不能成功。任何帮助是感激。
编辑:用于表示变量的组合和数据结构的顺序并不重要。

bweufnob

bweufnob1#

经过一堆的思考,我很遗憾地不能拿出一个干净和容易的解决方案。
尽管如此,我还是想出了一个解决办法:)虽然这里很乱,但我担心:D
第一个

gcuhipw9

gcuhipw92#

听起来你想要做的是将一系列n项划分成m集合,每个集合都有一个预定义的长度。你可以使用递归方法来实现这一点:
给定一系列长度lengths和所需的事物列表items

  • 首先检查lengths是否为空,如果是,则产生空列表并停止
  • lengths弹出第一个长度并将其存储在current_length
  • 对于具有长度x1M9N1x的x1M8N1x的每个组合x1M7N1x,执行:

1.生成新列表remaining_items,其中包含items中未包含在combination中的所有项

  • 使用参数lengthsremaining_items递归调用此函数,并对每个结果rest执行以下操作:
  • 产生前置combinationrest

这将给予你一个生成器,它将产生所需的结果,没有任何重复。
如果您可以每晚使用rust和itertools库,则实现如下:

#![feature(generators, generator_trait)]

use std::{ops::Generator, iter::FromIterator, pin::Pin};
use std::ops::GeneratorState;
use itertools::Itertools;

fn partition_series(sizes: Vec<usize>, items: Vec<u64>) -> impl Iterator<Item = Vec<Vec<u64>>> {
    GeneratorToIterator(move || {
        if sizes.len() == 0 {
            yield vec![];
            return;
        }
        
        let current_size = sizes[0];
        for combination in items.clone().into_iter().combinations(current_size) {
            let remaining_items: Vec<u64> = items
                .clone()
                .into_iter()
                .filter(|n| !combination.contains(n))
                .collect();

            let inner_generator: Box<dyn Iterator<Item = Vec<Vec<u64>>>> = Box::new(partition_series(sizes[1..].into(), remaining_items));
            for mut rest in inner_generator {
                rest.insert(0, combination.clone());
                yield rest;
            } 
        }
    })
}

struct GeneratorToIterator<G>(G);

impl<G> Iterator for GeneratorToIterator<G>
where
    G: Generator<Return = ()>,
{
    type Item = G::Yield;

    fn next(&mut self) -> Option<Self::Item> {
        let me = unsafe { Pin::new_unchecked(&mut self.0) };
        match me.resume(()) {
            GeneratorState::Yielded(x) => Some(x),
            GeneratorState::Complete(_) => None,
        }
    }
}

您可以通过以下方式调用从0到n的一系列数字:

fn main() {
    let sizes = vec![3, 2];
    let total_size = sizes.iter().sum::<usize>() as u64;
    let numbers = Vec::from_iter(0..total_size);
    for combination in partition_series(sizes, numbers) {
        println!("{:?}", combination);
    }
}

这将产生以下输出:

[[0, 1, 2], [3, 4]]
[[0, 1, 3], [2, 4]]
[[0, 1, 4], [2, 3]]
[[0, 2, 3], [1, 4]]
[[0, 2, 4], [1, 3]]
[[0, 3, 4], [1, 2]]
[[1, 2, 3], [0, 4]]
[[1, 2, 4], [0, 3]]
[[1, 3, 4], [0, 2]]
[[2, 3, 4], [0, 1]]

由于rust的实现可能有点难以理解,因为有些笨拙的生成器人体工程学,下面是一个python实现:

from typing import Iterable, List
from itertools import combinations

def main():
    for combination in generate_next([2, 2, 1]):
        print(combination)

def generate_next(sizes: List[int]) -> Iterable[List[List[int]]]:
    total_size = sum(sizes)
    numbers = list(range(total_size))
    yield from generate_next_internal(sizes, numbers)

def generate_next_internal(sizes: List[int], remaining: List[int]) -> Iterable[List[List[int]]]:
    if len(sizes) == 0:
        yield []
        return

    current_size = sizes.pop(0)

    for combination in combinations(list(remaining), current_size):
        new_remaining = [i for i in remaining if i not in combination]
        for rest in generate_next_internal(list(sizes), new_remaining):
            rest.insert(0, list(combination))
            yield rest


if __name__ == '__main__':
    main()

相关问题