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.
Project description
Subset Sum(dpss)
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.
dpss
is short for dynamic programming subset sum
.
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)
key.txt
1980
2980
3500
4000
1050
targets.txt
1950
2900
30
80
3300
200
3980
1050
20
Call subset_sum.exe key.txt targets.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
import dpss
print(dpss.find_subset([1, 2, 3], 2))
print(dpss.find_subset_fast_only_positive([1, 2, 3], 2))
print(dpss.sequence_matcher([1, 2, 3], [1, 2, 3]))
print(dpss.sequence_matcher_m2m([1, 2, 3], [1, 2, 3]))
Use in Rust
Cargo.toml
[dependencies]
subset_sum = "(version)"
Example
subset_sum = "0.8.0"
Subset sum
main.rs
use subset_sum::dp::find_subset;
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
use subset_sum::dp::sequence_matcher;
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
use subset_sum::dp::sequence_matcher_m2m;
fn main() {
let result = sequence_matcher_m2m(&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])]
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distributions
Hashes for dpss-0.10.1-cp39-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 549d28537edc46673a69e41462aa4fe4e83cac00f0a96eb9eab08c206d2e97be |
|
MD5 | 133a100f021bfa130175e83f05b9fdb0 |
|
BLAKE2b-256 | 583aa95b22d5cfdb1dee9b475a9c1a249d7d89542dce5eb9509d48dd1c1a8518 |
Hashes for dpss-0.10.1-cp38-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4079c010a19f27c8c87a532d0176f73d2d6b5cde168e7062240459d95d415656 |
|
MD5 | 2b8267e5bc3137e414ed7b985dfbfab2 |
|
BLAKE2b-256 | 5c0266792deef8e6d48ca45bd2b6edadb128de2181c01a072df520aa921b8a9a |
Hashes for dpss-0.10.1-cp37-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 29f82a27ec926e72c500deca1696f7890506fa1c8ec5b0bf6844f9ef5b67dca8 |
|
MD5 | 71eeebf288256f68bc574ffc749e4fac |
|
BLAKE2b-256 | a9f3a54e15b727f590195aa06ee344184631c672b68680fe5d4ab0ad54a35bec |