Subset Sum(dpss)

Downloads PyPI - Downloads Crates.io Crates.io (recent) GitHub all releases GitHub Repo stars

This is a Rust implementation that calculates subset sum problem using dynamic programming. It solves subset sum problem and returns a set of decomposed integers. It also can match corresponding numbers from two vectors and be used for Account reconciliation.

There are three ways to use this program. * CLI * Rust * Python

And it has three methods.

dpss is short for dynamic programming subset sum.

Links

|Name|URL| |--|--| |github|https://github.com/europeanplaice/subsetsum| |crates.io|https://crates.io/crates/subsetsum| |docs.rs|https://docs.rs/subset_sum/latest/dpss/| |pypi|https://pypi.org/project/dpss/|

CLI

Installation

Binary files are provided on the Releases page. When you download one of these, please add it to your PATH manually.

Usage

Subset sum

First, you need to prepare a text file containing a set of integers like this 1 2 -3 4 5 and save it at any place.

Second, call subset_sum with the path of the text file and the target sum.

Example

Call subset_sum.exe num_set.txt 3
The executable's name subset_sum.exe would be different from your choice. Change this example along with your environment.

In this example, the output is
[[2, 1], [4, -3, 2], [5, -3, 1]]

Sequence Matcher (One-to-Many)

key.txt 3 5 7

targets.txt 1 5 -3 4 5 3

Call subset_sum.exe key.txt targets.txt

In this example, the output is
[([3], 3), ([5], 5), ([5, 4, -3, 1], 7)] [([3], 3), ([4, 1], 5), ([5, 5, -3], 7)] [([5, -3, 1], 3), ([5], 5), ([3, 4], 7)]

Sequence Matcher (Many-to-Many)

arr1.txt 1980 2980 3500 4000 1050

arr2.txt 1950 2900 30 80 3300 200 3980 1050 20

Call subset_sum.exe arr1.txt arr2.txt m2m

In this example, the output is
[([20, 30, 1050, 2900], [4000]), ([200, 3300], [3500]), ([80, 1950, 3980], [1050, 1980, 2980])] [([20, 3980], [4000]), ([80, 2900], [2980]), ([30, 1950], [1980]), ([1050], [1050]), ([200, 3300], [3500])] [([20, 3980], [4000]), ([80, 2900], [2980]), ([1050], [1050]), ([30, 1950], [1980]), ([200, 3300], [3500])] [([20, 3980], [4000]), ([200, 3300], [3500]), ([80, 2900], [2980]), ([1050], [1050]), ([30, 1950], [1980])] [([30, 1950], [1980]), ([80, 2900], [2980]), ([20, 3980], [4000]), ([200, 3300], [3500]), ([1050], [1050])] [([30, 1950], [1980]), ([80, 2900], [2980]), ([200, 3300], [3500]), ([20, 3980], [4000]), ([1050], [1050])] [([30, 1950], [1980]), ([80, 2900], [2980]), ([1050], [1050]), ([20, 3980], [4000]), ([200, 3300], [3500])] [([80, 2900], [2980]), ([20, 3980], [4000]), ([1050], [1050]), ([200, 3300], [3500]), ([30, 1950], [1980])] [([80, 2900], [2980]), ([1050], [1050]), ([30, 1950], [1980]), ([20, 3980], [4000]), ([200, 3300], [3500])] [([200, 3300], [3500]), ([20, 30, 1050, 2900], [4000]), ([80, 1950, 3980], [1050, 1980, 2980])] [([200, 3300], [3500]), ([20, 3980], [4000]), ([80, 2900], [2980]), ([30, 1950], [1980]), ([1050], [1050])] [([1050], [1050]), ([30, 1950], [1980]), ([20, 3980], [4000]), ([80, 2900], [2980]), ([200, 3300], [3500])] There are a lot of combinations!

Use in Python

installation

pip install dpss

Usage

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

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

print(dpss.findsubsetfastonlypositive([1, 2, 3, 4, 5], 10))

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

print(dpss.sequence_matcher([3, 5, 7], [1, 5, -3, 4, 5, 3]))

[[([3], 3), ([5], 5), ([5, 4, -3, 1], 7)], [([3], 3), ([4, 1], 5), ([5, 5, -3], 7)], [([5, -3, 1], 3), ([5], 5), ([3, 4], 7)]]

print(dpss.sequencematcherm2m([1980, 2980, 3500, 4000, 1050], [1950, 2900, 30, 80, 3300, 200, 3980, 1050, 20]))

[[([20, 30, 1050, 2900], [4000]), ([200, 3300], [3500]), ([80, 1950, 3980], [1050, 1980, 2980])], [([20, 3980], [4000]), ([80, 2900], [2980]), ([30, 1950], [1980]), ([1050], [1050]), ([200, 3300], [3500])], [([20, 3980], [4000]), ([80, 2900], [2980]), ([1050], [1050]), ([30, 1950], [1980]), ([200, 3300], [3500])], [([20, 3980], [4000]), ([200, 3300], [3500]), ([80, 2900], [2980]), ([1050], [1050]), ([30, 1950], [1980])], [([30, 1950], [1980]), ([80, 2900], [2980]), ([20, 3980], [4000]), ([200, 3300], [3500]), ([1050], [1050])], [([30, 1950], [1980]), ([80, 2900], [2980]), ([200, 3300], [3500]), ([20, 3980], [4000]), ([1050], [1050])], [([30, 1950], [1980]), ([80, 2900], [2980]), ([1050], [1050]), ([20, 3980], [4000]), ([200, 3300], [3500])], [([80, 2900], [2980]), ([20, 3980], [4000]), ([1050], [1050]), ([200, 3300], [3500]), ([30, 1950], [1980])], [([80, 2900], [2980]), ([1050], [1050]), ([30, 1950], [1980]), ([20, 3980], [4000]), ([200, 3300], [3500])], [([200, 3300], [3500]), ([20, 30, 1050, 2900], [4000]), ([80, 1950, 3980], [1050, 1980, 2980])], [([200, 3300], [3500]), ([20, 3980], [4000]), ([80, 2900], [2980]), ([30, 1950], [1980]), ([1050], [1050])], [([1050], [1050]), ([30, 1950], [1980]), ([20, 3980], [4000]), ([80, 2900], [2980]), ([200, 3300], [3500])]] ```

Use in Rust

Please check https://crates.io/crates/subset_sum.

Cargo.toml [dependencies] subset_sum = "(version)"

Find subset

main.rs ```rust use subsetsum::dp::findsubset;

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

Sequence Matcher (One-to-Many)

main.rs ```rust use subsetsum::dp::sequencematcher;

fn main() { let result = sequence_matcher(&mut vec![3, 5, 7], &mut vec![1, 5, -3, 4, 5, 3]); println!("{:?}", result); } Output [ [([3], 3), ([5], 5), ([5, 4, -3, 1], 7)] [([3], 3), ([4, 1], 5), ([5, 5, -3], 7)] [([5, -3, 1], 3), ([5], 5), ([3, 4], 7)] ] ```

Sequence Matcher (Many-to-Many)

main.rs ```rust use subsetsum::dp::sequencematcher_m2m;

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