I don't want to deprive you of the fun of writing this yourself, but readers should be aware of the following option: Add [org.clojure/math.combinatorics "0.0.4"] to your project.clj Then: (use 'clojure.math.combinatorics) (combinations [1 2 3 4] 2) => ((1 2) (1 3) (1 4) (2 3) (2 4) (3 4))
The library implementation is also faster than the naive recursive approach.
Sometimes you not only need combinations but also partitions, which I would like to see in org.clojure/math.combinatorics, too, but are not present yet.
There is a nice implementation from Ray Miller here: https://gist.github.com/ray1729/5830608
Nice!
ReplyDeleteYou can also use "for" for this purpose:
=> (for [x (range 1 5), y (range 1 5) :when (not= x y)]
[x y])
([1 2] [1 3] [1 4] [2 1] [2 3] [2 4] [3 1] [3 2] [3 4] [4 1] [4 2] [4 3])
It's not doing exactly what combos is doing, but I think it's possible to work something out
Right on. For combinations it would be:
Delete=> (for [i (range 4) j (range 4) :when (< i j)] [i j])
([0 1] [0 2] [0 3] [1 2] [1 3] [2 3])
That's not quite as general as the recursive version (plus it has exponential time complexity) but it's good in a pinch :)
how would you use for to implement combos then?
DeleteYou could do something like
Delete=> (let [N 5]
(for [i (range N)
:let [j (range (inc i) N)]
k j
:let [m (range (inc k) N)]
n m]
[i k n]))
([0 1 2] [0 1 3] [0 1 4] [0 2 3] [0 2 4] [0 3 4] [1 2 3] [1 2 4] [1 3 4] [2 3 4])
but that's starting to get pretty hacky.
I don't want to deprive you of the fun of writing this yourself, but readers should be aware of the following option:
ReplyDeleteAdd [org.clojure/math.combinatorics "0.0.4"] to your project.clj
Then:
(use 'clojure.math.combinatorics)
(combinations [1 2 3 4] 2) => ((1 2) (1 3) (1 4) (2 3) (2 4) (3 4))
The library implementation is also faster than the naive recursive approach.
Concurred.
DeleteSometimes you not only need combinations but also partitions, which I would like to see in org.clojure/math.combinatorics, too, but are not present yet.
ReplyDeleteThere is a nice implementation from Ray Miller here:
https://gist.github.com/ray1729/5830608
I'm interested in adding partitions to math.combinatorics. Do you think each partition should be a sequence of sets, or just a sequence of sequences?
DeleteIn other words:
=> (partitions (range 3))
((#{0 1 2}) (#{0 1} #{2}) (#{0 2} #{1}) (#{0} #{1 2}) (#{0} #{1} #{2}))
or
=> (partitions (range 3))
(((0 1 2)) ((0 1) (2)) ((0 2) (1)) ((0) (1 2)) ((0) (1) (2)))
partitions has now been added to clojure.math.combinatorics 0.0.6
Delete