Filtering and sorting each partition is going to be pretty expensive! If
the list is long you will be discarding most of the results anyway.
I found a recursive way to do this that is fairly efficient, by observing
that you either want to join two adjacent elements together in a partition
or split at this point.
(defn ordered-partitions
([[fst & more]]
(ordered-partitions (list [fst]) more))
([init more]
(if (empty? more)
(list init)
(let [more-partitions (ordered-partitions more)
start (butlast init)
join (last init)]
(concat
(map #(concat init %) more-partitions)
(map #(let [[more-fst & more-more] %]
(concat start (list (vec (concat join more-fst)))
more-more)) more-partitions))))))
(time (count (ordered-partitions (range 20))))
"Elapsed time: 822.939961 msecs"
524288
i.e. you can compute half a million partitions in less than a second, which
I think is decent?
On Thursday, 16 March 2017 11:35:55 UTC+8, Paul Gowder wrote:
>
> Hi everyone,
>
> Does anyone know of a straightforward way to get something like
> clojure.math/combinatorics/partitions that works more like partition in the
> core library, that is, that only selects partitions with adjacent elements?
>
> In other words, right now this is the problem:
>
> (require '[clojure.math.combinatorics :as c])
> (c/partitions [:a :b :c] :min 2)
>
> => (([:a :b] [:c]) ([:a :c] [:b]) ([:a] [:b :c]) ([:a] [:b] [:c]))
>
> But that ([:a :c] [:b]) there in the second position isn't a proper
> partition because :a and :c aren't adjacent in the original vector.
>
> I feel like there's got to be a standard, canonical solution for this, or
> some existing sequence or combinatorics function with a funny name that
> just returns (([a :b] [:c]) ([:a] [:b :c]) ([:a] [:b] [:c])) in this
> situation. I just don't know it...
>
> The best I can come up with is kind of a hackish workaround that only
> works when the original vector is sorted, namely, flattening all the
> partitions and testing to see whether they are sorted too, i.e.:
>
> (require '[clojure.math.combinatorics :as c])
>
> (defn test-fn [part]
> (let [f (flatten part)]
> (= f (sort f))))
>
> (filter test-fn (c/partitions [:a :b :c] :min 2))
>
> => (([:a :b] [:c]) ([:a] [:b :c]) ([:a] [:b] [:c])) ; Yay! :-)
>
> And that works, but, as noted, only when the original vector is sorted.
> What if someone wanted to preserve adjacencies in an unsorted vector?
>
> All thoughts appreciated, thanks!
>
> Cheers,
>
> -Paul
>
>
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
