Subset Sum(dpss)

这是一个使用动态规划计算子集和问题的 Rust 实现。它解决子集和问题并返回一组分解整数。它还可以匹配两个向量的对应数字，用于账目核对。

欢迎任何反馈！

有四种方式使用此程序。

• 命令行界面🖥️

• Rust🦀

• Web🌎 (这是最简单的方式。)

• Python🐍

  在 Python 中，这里有一个可以直接在 Google Colab 上运行的现成示例。 https://colab.research.google.com/github/europeanplaice/subset_sum/blob/main/python/python_subset_sum.ipynb

它有两个方法。

• find_subset
  • 从数组中找到一个子集。
• 序列匹配器
  • 找到两个数组之间的子集和关系。解决多个子集子问题。

dpss 是 dynamic programming subset sum 的缩写。

链接

命令行界面

安装

二进制文件提供在 版本 页面。当你下载其中之一时，请手动将其添加到你的 PATH 中。

用法

子集和

首先，你需要准备一个包含一组整数的文本文件，如下所示

1
2
-3
4
5

并将其保存在任何位置。

然后，使用文本文件的路径和目标总和调用 subset_sum。

示例

调用 subset_sum.exe num_set.txt 3 3
可执行文件名 subset_sum.exe 将与您选择的名称不同。请根据您的环境更改此示例。第二个参数是目标总和。第三个参数是组合的最大长度。

在这个例子中，输出为
[[2, 1], [4, -3, 2], [5, -3, 1]]

序列匹配器

arr1.txt

1980
2980
3500
4000
1050

arr2.txt

1950
2900
30
80
3300
200
3980
1050
20

调用 subset_sum.exe arr1.txt arr2.txt 100 100 10 false false

概要

[executable] [keys text file path] [targets text file path] [max key length] [max target length] [the maximum number of answers] [boolean to use all keys] [boolean to use all targets]

• max_key_length 用于限制所选键中的值的数量。
• 如果 max_key_length 为 3，则答案的长度最多为 3，例如 [1980 + 2980 + 3500], [1050]
• max_target_length 对于目标与 max_key_length 相同。
• 最大答案数量 指定了最大模式数。
• 如果 use_all_keys 为真，则答案必须包含键的所有元素。
• 如果 use_all_targets 为真，则答案必须包含目标的所有元素。
• 当 use_all_keys 和 use_all_targets 都为真时，键和目标的和必须相同。

在这个例子中，输出为

pattern 1  => [(Sum(1050) -> keys:[1050] == targets:[1050])],
               keys remainder    : 1980, 2980, 3500, 4000
               targets remainder : 20, 30, 80, 200, 1950, 2900, 3300, 3980

pattern 2  => [(Sum(1050) -> keys:[1050] == targets:[1050])
               (Sum(12460) -> keys:[1980 + 2980 + 3500 + 4000] == targets:[20 + 30 + 80 + 200 + 1950 + 2900 + 3300 + 3980])],
               keys remainder    :
               targets remainder :

pattern 3  => [(Sum(3030) -> keys:[1050 + 1980] == targets:[30 + 1050 + 1950])],
               keys remainder    : 2980, 3500, 4000
               targets remainder : 20, 80, 200, 2900, 3300, 3980

pattern 4  => [(Sum(3030) -> keys:[1050 + 1980] == targets:[30 + 1050 + 1950])
               (Sum(10480) -> keys:[2980 + 3500 + 4000] == targets:[20 + 80 + 200 + 2900 + 3300 + 3980])],
               keys remainder    :
               targets remainder :

pattern 5  => [(Sum(13510) -> keys:[1050 + 1980 + 2980 + 3500 + 4000] == targets:[20 + 30 + 80 + 200 + 1050 + 1950 + 2900 + 3300 + 3980])],      
               keys remainder    :
               targets remainder :

pattern 6  => [(Sum(1980) -> keys:[1980] == targets:[30 + 1950])],
               keys remainder    : 1050, 2980, 3500, 4000
               targets remainder : 20, 80, 200, 1050, 2900, 3300, 3980

pattern 7  => [(Sum(2980) -> keys:[2980] == targets:[80 + 2900])],
               keys remainder    : 1050, 1980, 3500, 4000
               targets remainder : 20, 30, 200, 1050, 1950, 3300, 3980

pattern 8  => [(Sum(2980) -> keys:[2980] == targets:[80 + 2900])
               (Sum(10530) -> keys:[1050 + 1980 + 3500 + 4000] == targets:[20 + 30 + 200 + 1050 + 1950 + 3300 + 3980])],
               keys remainder    :
               targets remainder :

pattern 9  => [(Sum(3500) -> keys:[3500] == targets:[200 + 3300])],
               keys remainder    : 1050, 1980, 2980, 4000
               targets remainder : 20, 30, 80, 1050, 1950, 2900, 3980

pattern 10 => [(Sum(3500) -> keys:[3500] == targets:[200 + 3300])
               (Sum(10010) -> keys:[1050 + 1980 + 2980 + 4000] == targets:[20 + 30 + 80 + 1050 + 1950 + 2900 + 3980])],
               keys remainder    :
               targets remainder :

在 Python 中使用

安装

pip install dpss

用法

find_subset

import inspect
import dpss
help(dpss.find_subset)

>>> find_subset(arr, value, max_length, /)
>>>     Finds subsets sum of a target value. It can accept negative values.
>>>     # Arguments
>>>     * `arr` - An array.
>>>     * `value` - The value to the sum of the subset comes.
>>>     * `max_length` - The maximum length of combinations of the answer.

print(dpss.find_subset([1, -2, 3, 4, 5], 2, 3))

>>> [[4, -2], [3, -2, 1]]

sequence_matcher

help(dpss.sequence_matcher)

>>> sequence_matcher(keys, targets, max_key_length, max_target_length /)
>>>     Finds the integers from two vectors that sum to the same value.
>>>     This method assumes that the two vectors have Many-to-Many relationships.
>>>     Each integer of the `keys` vector corresponds to the multiple integers of the `targets` vector.
>>>     With this method, we can find some combinations of the integers.
>>>
>>>     To avoid combinatorial explosion, some parameters need to be set.
>>>     `max_key_length` is used to restrict the number of values in keys chosen.
>>>     If `max_key_length` is 3, an answer's length is at most 3, such as `[1980 + 2980 + 3500], [1050]`
>>>     `max_target_length` is the same as `max_key_length` for targets.
>>>     `n_candidates` specifies the maximum number of patterns.
>>>     If `use_all_keys` is true, an answer must contain all the elements of the keys.
>>>     If `use_all_targets` is true, an answer must contain all the elements of the targets.
>>>     When both `use_all_keys` and `use_all_targets` are true, the sum of the keys and the targets must be the same.
>>>
>>>     # Arguments
>>>     * `keys` - An array.
>>>     * `targets` - An array.
>>>     * `max_key_length` - An integer.
>>>     * `max_target_length` - An integer.
>>>     * `n_candidates` - An integer.
>>>     * `use_all_keys` - Boolean.
>>>     * `use_all_targets` - Boolean.

a = dpss.sequence_matcher(
        [1980, 2980, 3500, 4000, 1050],
        [1950, 2900, 30, 80, 3300, 200, 3980, 1050, 20], 10, 10, 10, True, True)
print(dpss.sequence_matcher_formatter(a))

pattern 1  => [(Sum(1050) -> keys:[1050] == targets:[1050])
               (Sum(12460) -> keys:[1980 + 2980 + 3500 + 4000] == targets:[20 + 30 + 80 + 200 + 1950 + 2900 + 3300 + 3980])],
               keys remainder    : 
               targets remainder : 

pattern 2  => [(Sum(3030) -> keys:[1050 + 1980] == targets:[20 + 30 + 80 + 2900])
               (Sum(10480) -> keys:[2980 + 3500 + 4000] == targets:[200 + 1050 + 1950 + 3300 + 3980])],
               keys remainder    : 
               targets remainder : 

pattern 3  => [(Sum(3030) -> keys:[1050 + 1980] == targets:[30 + 1050 + 1950])
               (Sum(10480) -> keys:[2980 + 3500 + 4000] == targets:[20 + 80 + 200 + 2900 + 3300 + 3980])],
               keys remainder    : 
               targets remainder : 

pattern 4  => [(Sum(13510) -> keys:[1050 + 1980 + 2980 + 3500 + 4000] == targets:[20 + 30 + 80 + 200 + 1050 + 1950 + 2900 + 3300 + 3980])],
               keys remainder    : 
               targets remainder : 

pattern 5  => [(Sum(4030) -> keys:[1050 + 2980] == targets:[80 + 1050 + 2900])
               (Sum(9480) -> keys:[1980 + 3500 + 4000] == targets:[20 + 30 + 200 + 1950 + 3300 + 3980])],
               keys remainder    : 
               targets remainder : 

pattern 6  => [(Sum(1980) -> keys:[1980] == targets:[30 + 1950])
               (Sum(11530) -> keys:[1050 + 2980 + 3500 + 4000] == targets:[20 + 80 + 200 + 1050 + 2900 + 3300 + 3980])],
               keys remainder    : 
               targets remainder : 

pattern 7  => [(Sum(2980) -> keys:[2980] == targets:[80 + 2900])
               (Sum(10530) -> keys:[1050 + 1980 + 3500 + 4000] == targets:[20 + 30 + 200 + 1050 + 1950 + 3300 + 3980])],
               keys remainder    : 
               targets remainder : 

pattern 8  => [(Sum(3500) -> keys:[3500] == targets:[200 + 3300])
               (Sum(10010) -> keys:[1050 + 1980 + 2980 + 4000] == targets:[20 + 30 + 80 + 1050 + 1950 + 2900 + 3980])],
               keys remainder    : 
               targets remainder : 

pattern 9  => [(Sum(4000) -> keys:[4000] == targets:[20 + 30 + 1050 + 2900])
               (Sum(9510) -> keys:[1050 + 1980 + 2980 + 3500] == targets:[80 + 200 + 1950 + 3300 + 3980])],
               keys remainder    : 
               targets remainder : 

pattern 10 => [(Sum(4000) -> keys:[4000] == targets:[20 + 3980])
               (Sum(9510) -> keys:[1050 + 1980 + 2980 + 3500] == targets:[30 + 80 + 200 + 1050 + 1950 + 2900 + 3300])],
               keys remainder    : 
               targets remainder : 

在 Rust 中使用

请检查 https://crates.io/crates/subset_sum。

Cargo.toml

[dependencies]
dpss = { version = "(version)", package = "subset_sum" }

查找子集

main.rs

use dpss::dp::find_subset;

fn main() {
    let result = find_subset(vec![1, 2, 3, 4, 5], 6, 3);
    println!("{:?}", result);
}

输出

[[3, 2, 1], [4, 2], [5, 1]]

序列匹配器

main.rs

use dpss::dp::sequence_matcher;
use dpss::dp::sequence_matcher_formatter;

fn main() {
    let result = sequence_matcher(&mut vec![1980, 2980, 3500, 4000, 1050], &mut vec![1950, 2900, 30, 80, 3300, 200, 3980, 1050, 20], 10, 10, 10, true, true);
    println!("{}", sequence_matcher_formatter(result));
}

输出

pattern 1  => [(Sum(1050) -> keys:[1050] == targets:[1050])
               (Sum(12460) -> keys:[1980 + 2980 + 3500 + 4000] == targets:[20 + 30 + 80 + 200 + 1950 + 2900 + 3300 + 3980])],
               keys remainder    : 
               targets remainder : 

pattern 2  => [(Sum(3030) -> keys:[1050 + 1980] == targets:[20 + 30 + 80 + 2900])
               (Sum(10480) -> keys:[2980 + 3500 + 4000] == targets:[200 + 1050 + 1950 + 3300 + 3980])],
               keys remainder    : 
               targets remainder : 

pattern 3  => [(Sum(3030) -> keys:[1050 + 1980] == targets:[30 + 1050 + 1950])
               (Sum(10480) -> keys:[2980 + 3500 + 4000] == targets:[20 + 80 + 200 + 2900 + 3300 + 3980])],
               keys remainder    : 
               targets remainder : 

pattern 4  => [(Sum(13510) -> keys:[1050 + 1980 + 2980 + 3500 + 4000] == targets:[20 + 30 + 80 + 200 + 1050 + 1950 + 2900 + 3300 + 3980])],
               keys remainder    : 
               targets remainder : 

pattern 5  => [(Sum(4030) -> keys:[1050 + 2980] == targets:[80 + 1050 + 2900])
               (Sum(9480) -> keys:[1980 + 3500 + 4000] == targets:[20 + 30 + 200 + 1950 + 3300 + 3980])],
               keys remainder    : 
               targets remainder : 

pattern 6  => [(Sum(1980) -> keys:[1980] == targets:[30 + 1950])
               (Sum(11530) -> keys:[1050 + 2980 + 3500 + 4000] == targets:[20 + 80 + 200 + 1050 + 2900 + 3300 + 3980])],
               keys remainder    : 
               targets remainder : 

pattern 7  => [(Sum(2980) -> keys:[2980] == targets:[80 + 2900])
               (Sum(10530) -> keys:[1050 + 1980 + 3500 + 4000] == targets:[20 + 30 + 200 + 1050 + 1950 + 3300 + 3980])],
               keys remainder    : 
               targets remainder : 

pattern 8  => [(Sum(3500) -> keys:[3500] == targets:[200 + 3300])
               (Sum(10010) -> keys:[1050 + 1980 + 2980 + 4000] == targets:[20 + 30 + 80 + 1050 + 1950 + 2900 + 3980])],
               keys remainder    : 
               targets remainder : 

pattern 9  => [(Sum(4000) -> keys:[4000] == targets:[20 + 30 + 1050 + 2900])
               (Sum(9510) -> keys:[1050 + 1980 + 2980 + 3500] == targets:[80 + 200 + 1950 + 3300 + 3980])],
               keys remainder    : 
               targets remainder : 

pattern 10 => [(Sum(4000) -> keys:[4000] == targets:[20 + 3980])
               (Sum(9510) -> keys:[1050 + 1980 + 2980 + 3500] == targets:[30 + 80 + 200 + 1050 + 1950 + 2900 + 3300])],
               keys remainder    : 
               targets remainder :