Re: Combinatorics partitions that preserves adjacency?

[Steve Miner]

For what it’s worth, I gave your problem a try and come up with the following 
implementation based on Mark Engelberg’s suggestion.  It should do less 
generating work up front so you don’t have to filter unwanted results.  This 
code depends on `combinations` preserving the order of the items.  I’m not sure 
that’s guaranteed, but the current implementation works that way, which is 
convenient.  My `sized-subsets` is a modified version of the combinatorics 
`subsets` that limits the results to the inclusive min and max counts given.

By the way, if you’re using subvectors you should be aware of bug CLJ-2065, 
reduce-kv fails on subvectors.  There’s an easy work-around in the bug report.

http://dev.clojure.org/jira/browse/CLJ-2065 


(require '[clojure.math.combinatorics :as mc])

;; inclusive sizes
(defn sized-subsets [items min-count max-count]
  (mapcat (fn [n] (mc/combinations items n))
  (range min-count (inc max-count


(defn subv-ordered-partitions [coll & {from :min to :max}]
  (let [v (vec coll)
cnt (count v)
smin (dec (or from 1))
smax (dec (or to cnt))]
(map (fn [splits]
   (map (fn [start end] (subvec v start end))
(conj splits 0)
(concat splits (list cnt
 (sized-subsets (range 1 cnt) smin smax

Steve Miner


> On Mar 16, 2017, at 12:59 PM, Paul Gowder  wrote:
> 
> For sake of completeness/if this is useful for anyone else, a full 
> implementation of the number-the-possible-split-locations method, including 
> the original API with :min and :max options. Could probably be tidied up with 
> transducers and such for all those filters but does the job. 
> 
> (require '[clojure.math.combinatorics :as c])
> (defn breaks->partition 
>  ([v brks]
>   (breaks->partition 0 [] v brks))
>  ([start pars v brks]
>   (if (empty? brks)
> (conj pars (subvec v start (count v)))
> (let [this-part (subvec v start (first brks))]
>   (recur (first brks) (conj pars this-part) v (rest brks))
> 
> (defn min-parts [min splits]
>  (>= (count splits) (- min 1)))
> 
> (defn max-parts [max splits]
>  (<= (count splits) (- max 1)))
> 
> (defn ordered-partitions [v & {:keys [max min]}]
>  (let 
>[s (c/subsets (range 1 (count v)))
> fs (cond
>  (and max min) 
>  (filter 
>(partial max-parts max) 
>(filter (partial min-parts min) s))
>  max (filter (partial max-parts max) s)
>  min (filter (partial min-parts min) s)
>  :else s)]
> (map (partial breaks->partition v) fs)))
> 
> It does, alas, take more than 10 times as long as Mike's version.  Which 
> proves that one should never try to do anything faster than the core.matrix 
> guy.  :-) 

-- 
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your 
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
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 clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: Combinatorics partitions that preserves adjacency?

[Paul Gowder]

For sake of completeness/if this is useful for anyone else, a full 
implementation of the number-the-possible-split-locations method, including the 
original API with :min and :max options. Could probably be tidied up with 
transducers and such for all those filters but does the job. 

(require '[clojure.math.combinatorics :as c])
(defn breaks->partition 
  ([v brks]
   (breaks->partition 0 [] v brks))
  ([start pars v brks]
   (if (empty? brks)
 (conj pars (subvec v start (count v)))
 (let [this-part (subvec v start (first brks))]
   (recur (first brks) (conj pars this-part) v (rest brks))

(defn min-parts [min splits]
  (>= (count splits) (- min 1)))

(defn max-parts [max splits]
  (<= (count splits) (- max 1)))

(defn ordered-partitions [v & {:keys [max min]}]
  (let 
[s (c/subsets (range 1 (count v)))
 fs (cond
  (and max min) 
  (filter 
(partial max-parts max) 
(filter (partial min-parts min) s))
  max (filter (partial max-parts max) s)
  min (filter (partial min-parts min) s)
  :else s)]
(map (partial breaks->partition v) fs)))

It does, alas, take more than 10 times as long as Mike's version.  Which proves 
that one should never try to do anything faster than the core.matrix guy.  :-) 

-- 
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your 
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
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 clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: Combinatorics partitions that preserves adjacency?

[Paul Gowder]

Ooh, thank you---those are both lovely solutions! 

-- 
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your 
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
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 clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: Combinatorics partitions that preserves adjacency?

[Mark Engelberg]

Think in terms of numbering the possible split locations:

a b c
 1 2

So the possible partitions are represented by [1], [2], [1 2], i.e., all
the non-empty subsets of [1 2].

So write a function that goes from this numbering scheme to partitions
(e.g., using subvec) and use combinatorics' subsets function.



On Wed, Mar 15, 2017 at 8:35 PM, 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 clojure@googlegroups.com
> Note that posts from new members are moderated - please be patient with
> your first post.
> To unsubscribe from this group, send email to
> clojure+unsubscr...@googlegroups.com
> 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 clojure+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>

-- 
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your 
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
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 clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: Combinatorics partitions that preserves adjacency?

[Mikera]

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 clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your 
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
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 clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.