Code Monkey home page Code Monkey logo

subset_sum's Introduction

Subset Sum(dpss)

github

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.

Any feedback is welcome!

There are four ways to use this program.

And it has two methods.

  • find_subset
    • It finds a subset from an array.
  • Sequence Matcher
    • It finds subset sum relationships with two arrays. Solving multiple subset sub problem.

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/
Website https://europeanplaice.github.io/subset_sum/

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 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]]

Sequence Matcher

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 100 100 10 false false

Synopsis:

[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 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.
  • the maximum number of answers 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.

In this example, the output is

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 :

Use in Python

installation

pip install dpss

Usage

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 :

Use in Rust

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

Cargo.toml

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

Find subset

main.rs

use dpss::dp::find_subset;

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

Output

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

Sequence Matcher

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));
}

Output

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 :

subset_sum's People

Contributors

dylan-dpc avatar europeanplaice avatar

Stargazers

avatar avatar avatar avatar avatar

Watchers

avatar

Forkers

vmanriq chris-ha458 mikethesapien densinh rajutarun

subset_sum's Issues

Bank Reconciliation

Hi,

Thanks for this great pkg. I am testing the wasm package (wasm_find_subset) to do reconciliations. But I have some questions:

  1. My subset array and target may include some values with 2 decimal places,
    example: subset [-40000, 25305.55, 25305.55, 30000, 54123.78] target: 79429.33.
    Could I just multiply the subset and the target by 100 to remove the decimals and make it work? By doing this will it take longer get a result?

  2. Using the same subset example as above, sometimes I can have repeated numbers in the subset array. Is it possible to get wasm_find_subset to return the result as positions in the array? example:
    subset [-40000, 25305.55, 25305.55, 30000, 54123.78] target: 79429.33
    result: [[1, 4], [2,4]]

  3. Currently the wasm_find_subset function returns a string. Could it return an array of arrays? Or is there an easy way to convert that string to an array of arrays.

Unsigned version for find_subset

Does this crate offer an unsigned version of the find_subset function?

For example a function with a signature like:

fn find_subset(Vec<usize>, usize, usize) -> Vec<Vec<usize>>;

I would need that in my project.

Importing the rust crate doesn't work

I would like to use your rust crate in my project but I ran into a problem when I add it to my Cargo.toml file.
Running cargo build ends up in an error:

error[E0433]: failed to resolve: use of undeclared crate or module `mem`
   --> /home/max/.cargo/registry/src/index.crates.io-6f17d22bba15001f/subset_sum-0.22.1/src/dp_module.rs:503:21
    |
503 |                     mem::swap(&mut y.0, &mut y.1);
    |                     ^^^ use of undeclared crate or module `mem`

This what I add to my Cargo.toml:

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

Python - Failing to build ModuleNotFoundError: No module named 'cffi'

Python version: 3.12
Platform: Win64

Full logs:

PS C:\Users\tavio\Downloads> pip install dpss
Collecting dpss
  Using cached dpss-0.22.0.tar.gz (150 kB)
  Installing build dependencies ... done
  Getting requirements to build wheel ... done
  Preparing metadata (pyproject.toml) ... done
Building wheels for collected packages: dpss
  Building wheel for dpss (pyproject.toml) ... error
  error: subprocess-exited-with-error

  × Building wheel for dpss (pyproject.toml) did not run successfully.
  │ exit code: 1
  ╰─> [30 lines of output]
      Running `maturin pep517 build-wheel -i C:\Users\tavio\AppData\Local\Programs\Python\Python312\python.exe --compatibility off`
         Compiling autocfg v1.1.0
         Compiling crossbeam-utils v0.8.8
         Compiling cfg-if v1.0.0
         Compiling lazy_static v1.4.0
         Compiling scopeguard v1.1.0
         Compiling rayon-core v1.9.1
         Compiling num_cpus v1.13.1
         Compiling either v1.6.1
         Compiling itertools v0.10.3
         Compiling memoffset v0.6.5
         Compiling crossbeam-epoch v0.9.8
         Compiling rayon v1.5.1
         Compiling crossbeam-channel v0.5.4
         Compiling crossbeam-deque v0.8.1
         Compiling subset_sum v0.22.0 (C:\Users\tavio\AppData\Local\Temp\pip-install-vt8ik074\dpss_84d1f0c3ac4c4da8b3452018dafd92c1)
          Finished release [optimized] target(s) in 7.60s
      💥 maturin failed
        Caused by: Failed to generate cffi declarations using C:\Users\tavio\AppData\Local\Programs\Python\Python312\python.exe: exit code: 1
      --- Stdout:

      --- Stderr:
      Traceback (most recent call last):
        File "<string>", line 2, in <module>
      ModuleNotFoundError: No module named 'cffi'

      📦 Including license file "LICENSE"
      🔗 Found cffi bindings
      ðŸ\x90\x8d Using CPython 3.12 at C:\Users\tavio\AppData\Local\Programs\Python\Python312\python.exe to generate the cffi bindings
      Error: command ['maturin', 'pep517', 'build-wheel', '-i', 'C:\\Users\\tavio\\AppData\\Local\\Programs\\Python\\Python312\\python.exe', '--compatibility', 'off'] returned non-zero exit status 1
      [end of output]

  note: This error originates from a subprocess, and is likely not a problem with pip.
  ERROR: Failed building wheel for dpss
Failed to build dpss
ERROR: Could not build wheels for dpss, which is required to install pyproject.toml-based projects

What I tried:

  • Installing and reinstalling Rust
  • Manually installing cffi (despite it already having been installed prior to installing dpss)
  • Installing package maturin from PyPI

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.