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.
Python implementation is also available.
dpss
is short for dynamic programming subset sum
.
Links
Name | URL |
---|---|
github | https://github.com/europeanplaice/subset_sum |
crates.io | https://crates.io/crates/subset_sum |
docs.rs | https://docs.rs/subset_sum/latest/dpss/ |
pypi | https://pypi.org/project/dpss/ |
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.3-pp37-pypy37_pp73-manylinux_2_5_x86_64.manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c623d0bf1d33de303489f16bf3a6135182cab3cc57600bb984b1a7ade8f7b740 |
|
MD5 | 81a443bd4b8972d196072284e30ebeb6 |
|
BLAKE2b-256 | 52f5e26b45c68c59560875ba18628aa3582303be67c2122964de4e9ca4ba14ee |
Hashes for dpss-0.10.3-cp310-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2072a26f7dc613002712f496770de6556e336b7e65caee089dd4c1e5b2f71fec |
|
MD5 | 8ee8f6f50e8d72fcee09af29256eb0af |
|
BLAKE2b-256 | deb7440c1d03fdbf5bffc43b73639f26750be9df8835ddfbeebcb8c0a8d2aafb |
Hashes for dpss-0.10.3-cp310-cp310-manylinux_2_5_x86_64.manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f83603653092934eed2cf7b6cd0e3431ffcb54a7fdcbec5bc3682d7c1897c2e9 |
|
MD5 | 5fe46b3b1a467a098a64d35b50cfb206 |
|
BLAKE2b-256 | 17adff74388a6d064229fc6870ab09d8084afc2a63b22b9dafd458ed1dec4391 |
Hashes for dpss-0.10.3-cp39-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c5233b976e6c1abc89020dd0905254c097a7efc95eb887d43827a9cf27cee167 |
|
MD5 | f01323a64ca02d74d80e4b6f7b18eb96 |
|
BLAKE2b-256 | 87c7f5ba3096d361f36f5e1c1039ee399d7cdaa4fd7233ef7c4062457f3360dc |
Hashes for dpss-0.10.3-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 040ce67e76e5b92ba0259c56049eca73dde451cae4a07d8fed32923ff3925d53 |
|
MD5 | 2ee1b0d3cc62bdb1adbf92528a872d4b |
|
BLAKE2b-256 | 1111ffe1a85c5fe7512ae03089dfe6d40e6930e46878bfb5229fd3a57dac465d |
Hashes for dpss-0.10.3-cp38-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 645a8b1ef27aa95f4fc23c5f9e5e5137c3efcc71ac460710666ab9e317e420c0 |
|
MD5 | 46e334f3394f33b8990eafcc55cfb0f5 |
|
BLAKE2b-256 | 1b155f1f41069f207f17b914c4420d08822c9d9e484d5d36278df19e1896dc6b |
Hashes for dpss-0.10.3-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bf700d207bef86c68a07e25dbd16ed8484a91f3f8cfcaa78e432a428baba3c48 |
|
MD5 | f3cc021855215533199eb8b04c7d6873 |
|
BLAKE2b-256 | a403828017e99dba6fa0355c869c13a63e086e3d9112b7891e9f90a05cd285c5 |
Hashes for dpss-0.10.3-cp37-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 986b9528bfcb247a5efc7f1cd90eb47ce7ae63fb19c2c05f66897992f9f88f5d |
|
MD5 | 65746ad8a3945442df5829c72e0e6327 |
|
BLAKE2b-256 | 2c28c09178cb64d1c2639dc04a967cc2164de67cf9043c597f30f55a3c2c182a |
Hashes for dpss-0.10.3-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f964331ca299f17ce70ad9b3ec235d74a3061b4578d220353a3da401727f3540 |
|
MD5 | b8b56f318808a409f78fd8383bbccdb7 |
|
BLAKE2b-256 | 3720b71f4b6b35ebed08d2a0919d8490ea6a21e187acea54c3890b24169a47fa |
Hashes for dpss-0.10.3-cp36-cp36m-manylinux_2_5_x86_64.manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5964e44b7220b1aef81a82f9a111c2788dc0dec58d0f302e1510c448514a744e |
|
MD5 | 4631af700c3af9b4e8dc2d14312880d8 |
|
BLAKE2b-256 | bf991505ff0367c597ca5cba1af2cb2ca1a9c9789c530f3ffde3fc31204020f6 |