Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Recursive subset matching algorithm #20

Closed
3 tasks done
Tracked by #3
ctrekker opened this issue Jan 14, 2022 · 0 comments
Closed
3 tasks done
Tracked by #3

Recursive subset matching algorithm #20

ctrekker opened this issue Jan 14, 2022 · 0 comments

Comments

@ctrekker
Copy link
Owner

ctrekker commented Jan 14, 2022

An algorithm and an implementation that can quickly find (ideally O(n)) whether or not a match between two sets exists is the first step of this issue. The second part is finding a way to both find and represent the possible matches between two sets. There probably exists an O(n) time algorithm for this too with some cleverness. Perhaps a good starting point is looking at algorithms relating to permutation functions and cyclic representation? Fundamentally a set of matches could hypothetically be thought of as a permutation cycle. Another way to look at it is that each node contains a set of potential matches, which then go through a logical elimination process by using singleton sets to remove elements which are already known to match a single other node.

  • Symbolic roots matching
  • Mixed-symbolic roots matching
  • Unit tests!
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant