Add combinatorics module

[natemcintosh]

combinatorics

A couple functions in the manner of python's itertools combinatoric functions

• [x] combinations<T>(data []T, r int) [][]T
• [x] combinations_with_replacement<T>(data []T, r int) [][]T
• [x] product<T>(data []T, repeat int) [][]T
• [x] permutations<T>(data []T, r int) [][]T

Is VSL the best place for something like this?

If it is, I'll give it a try. I'm in my first couple days of learning V however, so it'll certainly be ugly.

[natemcintosh]

I have an initial working version of combinations() in a local branch, but don't have permissions to push the branch to the server.

I've now also noticed that VTL might also be a good place a combinatorics module. Would it be better there? Or maybe just in it's own combinatorics library?

[ulises-jeremias]

Hey! How is it going? I think vsl is the best place (since vtl uses it as backend and will define its own combinators using vsl's definition). ~Also, I can send you some notes about how I was thinking it could be implemented in order to do it with lazy loading and not store the whole set of combinations in memory (as the python module works).~

About the contribution, you will need to fork the repo, create a new branch and then create a PR (same way for each repo in vlang)

~I'll send you the notes I mentioned above later in the day 👌🏻.~ Thanks for contributing also

EDIT

since generics are not fully working on V right now, we can wait until the creation of a lazy loading impl for combinatorics. In that case, you can just create a PR as described above. Then I'll review it and merge it. Next week I can create a lazy loading version for [ ]f64 and use it in the future to create a version for generics.

[natemcintosh]

Hi! Thanks for the help! I've submitted a PR from my fork for fn combinations(data []int, r int) [][]int.

I'm very interested to see how to do lazy loading in V. I'm used to the generators and generator expressions in Python and Julia, and don't quite understand how this would work in V. Lazy loading is obviously the way to go long term for combinatorics.

[ulises-jeremias]

just merged the PR. I'll do some quick changes to it, since we already have in vsl n_choose_k an things like that

[ulises-jeremias]

also, change from int to f64 everything. Then I'll do the same with lazyloading and show it to you 👍🏻

[natemcintosh]

Thanks for making all the suggested changes!

[ulises-jeremias]

you are wellcome! also, just added the struct CombinationsIter to lazy compute the combinations https://github.com/vlang/vsl/blob/master/comb/comb_iter.v. Redefined the function using that https://github.com/vlang/vsl/blob/master/comb/comb.v

[ulises-jeremias]

I think we can use that approach for the rest of the functions, what do you think?

[natemcintosh]

Yeah, I think this could work really well! So this provides users to use cases:

• One in which they called the combinations function and get the fully formed array of all combinations
• The other in which they create a CombinationsIter and call next() on it themselves for the lazy behavior

I think as long as it’s well documented, it should be great! I should be able to get started on combinations with replacements in a few days.

[natemcintosh]

I've opened up a pull request for a lazy implementation of combinations_with_permutations().

It looks like #7855 has been fixed as well!

[natemcintosh]

An eager [permutations] function (near the bottom of the file) is almost complete. It passes most of the tests I wrote. It fails one test (test_permutations_simple_4()) because it duplicates some of the permutations. Have not yet been able to figure out why. Once again, I'm using the example function in python's itertools to write this eager version.

Any thoughts on why it might be failing are welcome.

[ulises-jeremias]

Hey @natemcintosh ! sorry for the delay, let me check that right now. Also, some notes about the work you are doing

• I think It would be better to have another file into vsl.comb for permutations, perm.v should work.
• For new functions, such us permutations, I think it will be easier to define the lazy way first and then use it to define the functions that returns all permutations in memory, since the next function will be more similar to that you are using from python.
• Before you do the new PR, it would be great if you move fn move_ith_to_end into vsl.util, so we can use it for other modules

[natemcintosh]

Hi @ulises-jeremias, I think I've got all those changes made in my fork.

• [x] permutations code now in comb/perm.v and comb/perm_test.v
• [x] lazy infrastructure for permutations is up and working at the same level as the eager version
• [x] move_ith_to_end has been moved to util

I'm still running into the issue with the duplicated permutations in test vsl/comb/perm_test.v/test_permutations_simple_4(), but otherwise, things look good for the lazy version.

Thanks for all the help and suggestions!

[ulises-jeremias]

@natemcintosh great! I just did a minor change removing the usage of rev_range using a for loop, just to not store unnecesary extra data

[ulises-jeremias]

I think you can change that too, and then create a PR with all your changes (we can fix that bug your are facing latter) I'll put a FIXME: comment on that

[natemcintosh]

done!

[ulises-jeremias]

@natemcintosh I just renamed the module to vsl.iter, so then we can start implementing the rest of the functions from https://docs.python.org/3.9/library/itertools.html#module-itertools . Do you think you can continue with that work? I can help on anything you need while you continue with that 👌🏻

[ulises-jeremias]

Also, I'll do a quick change on the design to make function names shorter

[natemcintosh]

Do you think you can continue with that work?

Yea! That would be pretty fun! I think we should be able to build most of the functions. However, those that take arbitrary functions as part of their input might be harder to replicate. As far as I can tell from the docs, higher order functions in V require that the function input argument knows all of its types. Is there a way to pass in generic predicate functions?

I've got a product() function pretty much done, and hope to check it in within the next few days.

[ulises-jeremias]

For those cases we can use this type of functions as argument https://vlang.github.io/vsl/#Function