<< Back to previous view

[MCOMB-8] Better support for sets Created: 12/Mar/17  Updated: 18/Mar/17

Status: Open
Project: math.combinatorics
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Enhancement Priority: Minor
Reporter: Greg Chapman Assignee: Mark Engelberg
Resolution: Unresolved Votes: 0
Labels: None


 Description   

It seems reasonable to want to use a clojure set as the items parameter for the combinatoric functions. However, in the case of (combinations some-set 1), an exception is raised because Clojure's distinct function (called when (= t 1)) does not support sets. This problem can be worked around by converting the set to a seq before calling combinations.

For all the other functions, it appears extending all-different? with a set? check would make the functions slightly more efficient (by avoiding the linear distinct? scan).



 Comments   
Comment by Greg Chapman [ 12/Mar/17 2:12 PM ]

I looked a little further: it looks like nth-permutation-distinct will call nth on its l parameter. Sets do not support nth, so better set support would require a change to that function.

Comment by Mark Engelberg [ 13/Mar/17 4:13 AM ]

See discussion here: https://groups.google.com/forum/#!topic/clojure/XUEqdCSI6c4

I don't think it necessarily makes sense for sets to be valid inputs. What these algorithms return is highly dependent on the order of elements in the seq. Since sets are unordered, such a change would make it so that these are not pure functions, i.e., they could return completely different outputs for the same (equal) inputs. That's because two sets that compare as equal may return a different ordering of elements when applying seq. This could wreak havoc with people's test cases in their functions which call these with sets, etc.

I think it is better for the user to be forced to apply seq directly rather than have it happen implicitly, so he/she can think about the consequences, and maybe do a sort of the seq or something to ensure a consistent output, if desired.

Comment by Nathan Irwin Smutz [ 17/Mar/17 4:46 PM ]

Fix or no fix, the least that needs to happen is an edit to the docstring.

As it is, combinations is going to work just fine until the size-1 corner-case hits. Hidden land-mines like this need some kind of fix.
Forcing action on ordering issues would entail throwing an exception, popping a warning, or making functions error on sets consistently.

Comment by Mark Engelberg [ 17/Mar/17 5:08 PM ]

I agree that the current behavior is unfriendly. Possible solutions are:

1) Implicitly call seq on all inputs (disadvantage: no longer pure functions)
2) Throw errors on sets (disadvantage: adds runtime check)
3) Add info to docstring that inputs must be a sequential (disadvantage: need to read docstring to understand constraint, does everyone know what a "sequential" means, and that sets and maps do not qualify?)
4) Add discussion on this point to README (disdavantage: does anyone read the README?)

I'd lean towards 3 or 4. I'm happy to make a change along those lines.

Comment by Nathan Irwin Smutz [ 18/Mar/17 4:52 PM ]

Thinking about #1, for anything but size-1 combinations, the behavior wouldn't be any less pure than it is now. It would also have the exact same purity as seq, vec, map or any other order-preserving function. (map inc some-set) has the same caveat for order. Since the issue of equality on order-hiding data-structures and order-preserving (revealing?) functions is a lot bigger than combinatorics functions, a suitable equality-warning really belongs with order-hiding objects themselves.

Thinking about the discussion on the mailing list, one of the reasons people use sets is to deliberately ignore order. I think the best advice would be to convert sequences back to sets before testing. (set (map inc some-set))

I think if we wouldn't leave map broken on sets, it's worth fixing here.

Comment by Nathan Irwin Smutz [ 18/Mar/17 5:13 PM ]

I see some of the issue with combinations. Mathematical combinations are order-agnostic; but these are lists. For equality-testing you'd use: (set (map set (combinations some-set n)))





[MCOMB-7] Fix reflection errors Created: 03/May/16  Updated: 18/May/16  Resolved: 18/May/16

Status: Resolved
Project: math.combinatorics
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Enhancement Priority: Minor
Reporter: Ambrose Bonnaire-Sergeant Assignee: Mark Engelberg
Resolution: Completed Votes: 0
Labels: None

Attachments: Text File box-longs.patch    

 Description   

I get several reflection errors compiling math.combinatorics 0.1.1 on Clojure 1.8.

They were quite confusing to fix, but refactoring loops into multi-arity functions consistently fixed these errors.



 Comments   
Comment by Ambrose Bonnaire-Sergeant [ 03/May/16 12:43 PM ]

Patch fixes reflection errors in Clojure 1.8.

Comment by Mark Engelberg [ 03/May/16 2:48 PM ]

These loop auto-boxing warnings are because integer literals are now read in as primitive longs (since 1.6?), but these loops want boxed longs.

The simplest fix, I think, would be to replace the literals in the loop args with boxed longs. So, for example, 1 becomes (Long. 1). I believe that this is what the compiler does automatically when it sees that recur isn't passing in a primitive long (thus the warning that it is auto-boxing the loop arg), so I don't think it would have any impact on performance (this isn't actually a warning that it needs to do reflection at runtime), but it would make the warning disappear.

Breaking the loop out into a separate function strikes me as a heavy-handed solution (it makes the warning disappear because Clojure boxes numbers on function calls unless otherwise annotated, but there's really no need to break it into a separate function).

Comment by Ambrose Bonnaire-Sergeant [ 03/May/16 3:26 PM ]

Ah. My understanding here is limited. Would you like me to work on another patch with those suggestions?

Comment by Mark Engelberg [ 03/May/16 7:10 PM ]

Sure. I'm pretty sure there's no performance penalty in its current form, but if you find the warnings a nuisance and don't mind creating another patch, that would be great.

Comment by Ambrose Bonnaire-Sergeant [ 03/May/16 8:32 PM ]

New patch that explicitly boxes Long's to work around reflection errors, as suggested by Mark.

Comment by Mark Engelberg [ 18/May/16 5:54 AM ]

Auto-boxing loop warnings addressed as of version 0.1.2





[MCOMB-6] Support ClojureScript by converting from CLJ to CLJC Created: 18/Mar/16  Updated: 18/Mar/16

Status: Open
Project: math.combinatorics
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Enhancement Priority: Minor
Reporter: Eric Lavigne Assignee: Mark Engelberg
Resolution: Unresolved Votes: 0
Labels: None

Attachments: Text File combinatorics-cljc.patch    
Patch: Code

 Description   

Patch attached with two changes:
1) Rename main source file to change extension from .clj to .cljc.
2) Add Clojure 1.7 dependency to pom.xml.

Ran "mvn clojure:test" and confirmed that old tests still pass.

Did not test in ClojureScript environment.

Main downside is increasing the minimum Clojure version from 1.2 to 1.7 for CLJC support. Alex Miller also indicated that the Clojure CI system was not ready for CLJC files yet, but that it would be nice to have the ticket and patch ready.

See previous clojure-dev discussion: https://groups.google.com/forum/#!topic/clojure-dev/PDyOklDEv7Y






[MCOMB-5] Exclude `update` in :refer-clojure for Clojure 1.7.0 compatibility Created: 27/Oct/14  Updated: 24/Dec/15  Resolved: 16/Mar/15

Status: Resolved
Project: math.combinatorics
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Minor
Reporter: Tim McCormack Assignee: Mark Engelberg
Resolution: Completed Votes: 0
Labels: None

Attachments: Text File math.combinatorics.patch    

 Description   

Clojure 1.7.0 introduces a function `update`, so this line generates a shadowing warning:

https://github.com/clojure/math.combinatorics/blob/67b2e2a38be69fa25e713594c6da74303d52042c/src/main/clojure/clojure/math/combinatorics.clj#L219

This should be added to the ns block:

(:refer-clojure :exclude [update])


 Comments   
Comment by Atamert Ölçgen [ 08/Mar/15 1:37 AM ]

I have tested with Clojure 1.4 & 1.7.

(PS: Signed the CA just today.)

Comment by Mark Engelberg [ 16/Mar/15 6:41 PM ]

Fixed and released as 0.0.9.

Comment by Alexander Yakushev [ 24/Dec/15 1:56 AM ]

I still get the warning when working with latest Midje. It uses math.combinatorics 0.1.1.





[MCOMB-4] Performance enhancement for sorted-numbers? Created: 12/Jul/14  Updated: 19/Jul/14  Resolved: 19/Jul/14

Status: Resolved
Project: math.combinatorics
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Enhancement Priority: Trivial
Reporter: Daniel Marjenburgh Assignee: Mark Engelberg
Resolution: Completed Votes: 0
Labels: enhancement, patch, performance

Attachments: File sorted-numbers-perf-enh.diff    
Patch: Code
Approval: Accepted

 Description   

Hi,

Came upon this as I was trying to improve performance. The implementation of sorted-numbers? (only used by permutations) is:
(defn- sorted-numbers?
"Returns true iff s is a sequence of numbers in non-decreasing order"
[s]
(and (every? number? s)
(every? (partial apply <=) (partition 2 1 s))))

<= and similar operators are variadic, so partitioning into pairs is unneeded.
(apply <= s) is a lot faster, but breaks for empty sequences, so an additional check is needed.

The implementation can be changed to:

(and (every? number? s)
(or (empty? s) (apply <= s)))

I benched this to be 10 to 15 times faster. A regression test with test.check was done to verify that the behaviour was not changed under any input.
A patch is also included.

Cheers,

Daniel



 Comments   
Comment by Andy Fingerhut [ 13/Jul/14 7:39 PM ]

Thanks for the submission. I don't know whether Mark would be interested in taking the test.check regression test you developed, too, but if you would be willing to share it as a patch, it might be considered for inclusion as well.

Comment by Daniel Marjenburgh [ 18/Jul/14 5:43 AM ]

Hm, I don't know how I could include the regression test as a patch. Because:
1) The current project does not use external libraries or Leiningen (yet). How do I add dependencies when not using Leiningen?
2) I tested the old implementation vs the new one with generated inputs. If the old implementation is gone, there's no test to add...

Comment by Mark Engelberg [ 19/Jul/14 5:06 PM ]

Since this function is only called once at the beginning of the permutations process, on a sequence that is usually 10 or fewer items, I can't imagine this improvement will have any meaningful impact on the overall running time of the permutations algorithm. Nevertheless, it's an improvement, so I've gone ahead and added it.





[MCOMB-3] Please add project.clj Created: 23/Jun/13  Updated: 23/Jun/13

Status: Open
Project: math.combinatorics
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Task Priority: Major
Reporter: David James Assignee: Mark Engelberg
Resolution: Unresolved Votes: 0
Labels: None


 Description   

Is there a reason for not having a `project.clj` in the project?

I'd like to fork, run `lein test` and `lein repl`.



 Comments   
Comment by David James [ 23/Jun/13 5:53 PM ]

I added leiningen support to my fork:
https://github.com/xpe/math.combinatorics





[MCOMB-2] OutOfMemory Error with combinatorics/subsets Created: 29/Apr/13  Updated: 08/Apr/14  Resolved: 08/Apr/14

Status: Resolved
Project: math.combinatorics
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Minor
Reporter: Mark Engel Assignee: Mark Engelberg
Resolution: Completed Votes: 1
Labels: None
Environment:

Mac OS X 10.8.3
Clojure 1.5.1 (installed with homebrew)
Leiningen 2.1.3 on Java 1.6.0_45 Java HotSpot(TM) 64-Bit Server VM
-Xmx2048M
math.combinatorics 0.0.4

% java -version
java version "1.6.0_45"
Java(TM) SE Runtime Environment (build 1.6.0_45-b06-451-11M4406)
Java HotSpot(TM) 64-Bit Server VM (build 20.45-b01-451, mixed mode)


Attachments: Text File mcomb-2-allow-subsets-to-use-less-memory-v1.txt    

 Description   

Hello guys,

I have an issue with an OutOfMemory error with bigger sets and the subsets command.

I have bigger sets of 1000+ elements and want to lazily create all possible subsets of this set in order to filter out some that are interesting to me.

I was very happy to run into your library as it handles the heavy lifting for me and I only have to do the filtering. Nice!

But if I run this sample code

lein repl
=> (last (clojure.math.combinatorics/subsets (range 1000)))
OutOfMemoryError Java heap space  clojure.core/map (core.clj:2469)

it returns with an OutOfMemory Error to me.
I thought the memory usage of subsets would be constant as the function should return a lazy list.

It would be really nice if this library could calculate subsets of bigger lists without running into memory problems.

I posted this question on StackOverflow with more information:
http://stackoverflow.com/questions/16194841/clojure-lazy-sequences-in-math-combinatorics-results-in-outofmemory-oom-error

And people replied that they don't have this issue. Is this an issue with my platform or is this an issue with the memory usage of subsets?
It would be great if you could show me a way to get around this issue.

If I can be of any help, just let me know.

Cheers, Mark



 Comments   
Comment by Stefan du Fresne [ 29/Apr/13 5:29 AM ]

I get this as well, 2009 MBP, with any (range x) higher than 18.

Comment by Mark Engel [ 29/Apr/13 8:32 AM ]

Great to have the problem reproduced at another computer.

I just found an article describing an OutOfMemory Error with mapcat, which is used in the subsets function
http://clojurian.blogspot.de/2012/11/beware-of-mapcat.html.

Comment by Andy Fingerhut [ 02/May/13 2:30 PM ]

Patch mcomb-2-allow-subsets-to-use-less-memory-v1.txt dated May 2 2013 seems to fix this problem.

range returns a chunked sequence, and when map processes a chunked sequence it preserves the chunks. Chunks are little Java arrays of Object references, pointing at the results, and none of them will be GCed until the entire chunk is finished being processed.

It might be that a few other calls to unchunk wrapped around range calls might be useful in the math.combinatorics library, but certainly not all of them.

Comment by David James [ 23/Jun/13 6:04 PM ]

Thanks Andy, that worked for me!

Andy's patch, applied to my fork:
https://github.com/xpe/math.combinatorics/commit/5adb2fdfd6e1661eb4056cbf06e8d4a633dd0088

Comment by Andy Fingerhut [ 08/Apr/14 8:24 AM ]

Mark, any thoughts on this patch? The reason for the memory exhaustion without the patch is a bit subtle, and I can try explaining it differently if you are interested.

Comment by Andy Fingerhut [ 08/Apr/14 4:21 PM ]

Mark Engelberg committed this fix: https://github.com/clojure/math.combinatorics/commit/4b5312218344264c3227f7f814db6c688d0ab2fc

I will close this ticket.





[MCOMB-1] math.combinatorics README should be updated to conform to contrib standard Created: 17/Sep/12  Updated: 17/Sep/12  Resolved: 17/Sep/12

Status: Resolved
Project: math.combinatorics
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Enhancement Priority: Trivial
Reporter: Christian Romney Assignee: Mark Engelberg
Resolution: Completed Votes: 0
Labels: documentation, patch

Attachments: Text File 0001-Updated-README-to-conform-to-new-contrib-standard.patch    
Patch: Code

 Description   

As per Sean Corfield's suggestion here: https://groups.google.com/forum/?fromgroups=#!searchin/clojure-dev/math/clojure-dev/p5oz42gR_sk/cesMHO9cDWEJ
the math.combinatorics README.md should be updated to be more useful, especially to newbies.



 Comments   
Comment by Sean Corfield [ 17/Sep/12 11:35 AM ]

Patch applied.





Generated at Wed May 24 04:44:13 CDT 2017 using JIRA 4.4#649-r158309.