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.
Any feedback is welcome!
There are three ways to use this program. * CLI * Rust * Python
Here is an out of the box example you can run now in google colab. https://colab.research.google.com/github/europeanplaice/subset_sum/blob/main/python/example.ipynb
And it has three methods.
find_subset find_subset_fast_only_positive Sequence Matcher (One-to-Many)
Sequence Matcher (Many-to-Many)
dpss is short for dynamic programming subset sum.
|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/|
Binary files are provided on the Releases page. When you download one of these, please add it to your PATH manually.
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.
Call subset_sum.exe num_set.txt 3 3
The executable's name subset_sum.exe would be different from your choice. Change this example along with your environment.
The second argument is the target sum.
The third argument is the maximum length of the combination.
In this example, the output is
[[2, 1], [4, -3, 2], [5, -3, 1]]
key.txt
3
5
7
targets.txt
1
5
-3
4
5
3
Call subset_sum.exe key.txt targets.txt o2m 4
The fourth argument is the maximum length of the combination.
In this example, the output is
[(3, [3]), (5, [5]), (7, [5, 4, -3, 1])]
[(3, [3]), (5, [4, 1]), (7, [5, 5, -3])]
[(3, [5, -3, 1]), (5, [5]), (7, [3, 4])]
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
[([1050], [1050]), ([1980, 2980, 3500, 4000], [20, 30, 80, 200, 1950, 2900, 3300, 3980])]
[([1050, 1980, 2980], [80, 1950, 3980]), ([3500, 4000], [20, 30, 200, 1050, 2900, 3300])]
...
[([4000], [20, 3980]), ([1050], [1050]), ([1980, 2980, 3500], [30, 80, 200, 1950, 2900, 3300])]
[([4000], [20, 3980]), ([1050, 1980, 2980, 3500], [30, 80, 200, 1050, 1950, 2900, 3300])]
pip install dpss
find_subsetpython
import inspect
import dpss
help(dpss.find_subset)
```
findsubset(arr, value, maxlength, /) 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. ```
python
print(dpss.find_subset([1, -2, 3, 4, 5], 2, 3))
```
[[4, -2], [3, -2, 1]] ```
find_subset_fast_only_positive
python
help(dpss.find_subset_fast_only_positive)
```
findsubsetfastonlypositive(arr, value, maxlength, /) Finds subsets sum of a target value. It can't accept negative values but relatively faster. # Arguments *
arr- An array. *value- The value to the sum of the subset comes. *max_length- The maximum length of combinations of the answer.python print(dpss.findsubsetfastonly_positive([1, 2, 3, 4, 5], 10, 4))[[4, 3, 2, 1], [5, 3, 2], [5, 4, 1]] ```
sequence_matcherpython
help(dpss.sequence_matcher)
```
sequencematcher(key, targets, maxtargetlength, /) Finds the integers from two vectors that sum to the same value. This method assumes that the two vectors have One-to-Many relationships. Each integer of the
keyvector corresponds to the multiple integers of thetargetsvector. # Arguments *key- An array. *targets- An array. *max_length- The maximum length of combinations of the answer.python print(dpss.sequencematcher([3, 5, 7], [1, 5, -3, 4, 5, 3], 4))[ [(3, [3]), (5, [5]), (7, [5, 4, -3, 1])], [(3, [3]), (5, [4, 1]), (7, [5, 5, -3])], [(3, [5, -3, 1]), (5, [5]), (7, [3, 4])], ] ```
sequence_matcher_m2m
python
help(dpss.sequence_matcher_m2m)
```
sequencematcherm2m(keys, targets, nshuffle, /) 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
keysvector corresponds to the multiple integers of thetargetsvector. With this method, we can find some combinations of the integers. # Arguments *keys- An array. *targets- An array.python print(dpss.sequencematcher_m2m([1980, 2980, 3500, 4000, 1050], [1950, 2900, 30, 80, 3300, 200, 3980, 1050, 20]))[[([1050], [1050]), ([1980, 2980, 3500, 4000], [20, 30, 80, 200, 1950, 2900, 3300, 3980])], [([1050, 1980, 2980], [80, 1950, 3980]), ([3500, 4000], [20, 30, 200, 1050, 2900, 3300])], ... ```
Please check https://crates.io/crates/subset_sum.
Cargo.toml
[dependencies]
dpss = { version = "(version)", package = "subset_sum" }
main.rs
```rust
use dpss::dp::find_subset;
fn main() {
let result = find_subset(&mut vec![1, 2, 3, 4, 5], 6, 3);
println!("{:?}", result);
}
Output
[[3, 2, 1], [4, 2], [5, 1]]
```
main.rs
```rust
use dpss::dp::sequence_matcher;
fn main() {
let result = sequence_matcher(&mut vec![3, 5, 7], &mut vec![1, 5, -3, 4, 5, 3], 4);
println!("{:?}", result);
}
Output
[
[(3, [3]), (5, [5]), (7, [5, 4, -3, 1])]
[(3, [3]), (5, [4, 1]), (7, [5, 5, -3])]
[(3, [5, -3, 1]), (5, [5]), (7, [3, 4])]
]
```
main.rs
```rust
use dpss::dp::sequencematcherm2m;
fn main() {
let result = sequencematcherm2m(&mut vec![1980, 2980, 3500, 4000, 1050], &mut vec![1950, 2900, 30, 80, 3300, 200, 3980, 1050, 20]);
println!("{:?}", result);
}
Output
[([1050], [1050]), ([1980, 2980, 3500, 4000], [20, 30, 80, 200, 1950, 2900, 3300, 3980])]
[([1050, 1980, 2980], [80, 1950, 3980]), ([3500, 4000], [20, 30, 200, 1050, 2900, 3300])]
[([1050, 1980, 2980, 3500, 4000], [20, 30, 80, 200, 1050, 1950, 2900, 3300, 3980])]
...
```