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