Skip to content

Instantly share code, notes, and snippets.

@luxbock

luxbock/j_setparts.md

Created October 22, 2022 18:18
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save luxbock/c1ce55524e91599d6770b193e682b05b to your computer and use it in GitHub Desktop.
Save luxbock/c1ce55524e91599d6770b193e682b05b to your computer and use it in GitHub Desktop.
Download ZIP
Raw
j_setparts.md

Set partitions in J

https://code.jsoftware.com/wiki/Essays/Set_Partitions

   nextpart=: (#~ ,"1 0 ;@:(i.&.>)@]) >:@#@~."1
   setpart=: nextpart^:(]`(''"_))

The power gerund in setpart is just a way of passing arguments to the power conjunction in tacit style. We could have written it as:

   setpart =: {{ nextpart^:y '' }}

What about nextpart? (With boxed display on):

   nextpart
┌────────────────────────────────────────┬─────────────────────┐
│┌─────┬─────────┬──────────────────────┐│┌───────────────┬─┬─┐│
││┌─┬─┐│┌─┬─┬───┐│┌────────────────┬─┬─┐│││┌────────┬─┬──┐│"│1││
│││#│~│││,│"│1 0│││┌─┬──┬─────────┐│@│]│││││┌──┬─┬─┐│@│~.││ │ ││
││└─┴─┘│└─┴─┴───┘│││;│@:│┌──┬──┬─┐││ │ ││││││>:│@│#││ │  ││ │ ││
││     │         │││ │  ││i.│&.│>│││ │ │││││└──┴─┴─┘│ │  ││ │ ││
││     │         │││ │  │└──┴──┴─┘││ │ ││││└────────┴─┴──┘│ │ ││
││     │         ││└─┴──┴─────────┘│ │ │││└───────────────┴─┴─┘│
││     │         │└────────────────┴─┴─┘││                     │
│└─────┴─────────┴──────────────────────┘│                     │
└────────────────────────────────────────┴─────────────────────┘

We see that nextpart is a hook consisting of a train and a verb.

Let's see some examples:

   nextpart&.>^:(1 2 3 4) <''
┌─┬───┬─────┬───────┐
│0│0 0│0 0 0│0 0 0 0│
│ │0 1│0 0 1│0 0 0 1│
│ │   │0 1 0│0 0 1 0│
│ │   │0 1 1│0 0 1 1│
│ │   │0 1 2│0 0 1 2│
│ │   │     │0 1 0 0│
│ │   │     │0 1 0 1│
│ │   │     │0 1 0 2│
│ │   │     │0 1 1 0│
│ │   │     │0 1 1 1│
│ │   │     │0 1 1 2│
│ │   │     │0 1 2 0│
│ │   │     │0 1 2 1│
│ │   │     │0 1 2 2│
│ │   │     │0 1 2 3│
└─┴───┴─────┴───────┘

Let's name them to use them for later:

   'p_2 p_3' =: nextpart&.>^:(2 3) <''

Let's name the verbs:

   npa =: #~
   npb =: ,"1 0
   npc =: ;@:(i.&.>)@]
   npd =: >:@#@~."1
   
   np =: (npa npb npc) npd
   
   np
┌─────────────┬───┐
│┌───┬───┬───┐│npd│
││npa│npb│npc││   │
│└───┴───┴───┘│   │
└─────────────┴───┘

Make sure they do the same thing:

   (np -: nextpart)&.>^:(1 2 3 4) <''
┌─┬─┬─┬─┐
│1│1│1│1│
└─┴─┴─┴─┘

Probably good enough...

Now ((f g h) k) y = (y f k y) g (y h k y), so we should have that:

   p_2
0 0
0 1

   np p_2
0 0 0
0 0 1
0 1 0
0 1 1
0 1 2

   (p_2 npa npd p_2) npb (p_2 npc npd p_2)
0 0 0
0 0 1
0 1 0
0 1 1
0 1 2

   [ a_res =: (p_2 npa npd p_2)
0 0
0 0
0 1
0 1
0 1

   [ c_res =: (p_2 npc npd p_2)
0 1 0 1 2

   a_res ,"1 0 c_res
0 0 0
0 0 1
0 1 0
0 1 1
0 1 2

   NB. We could have also done:
   a_res ,. ,. c_res
0 0 0
0 0 1
0 1 0
0 1 1
0 1 2

The J-Wiki explains the algorithm as doing the following:

We note that the next generation is obtained from the previous by: 1) taking each row 2) finding its nub+1 indices i.>:#~. 3) appending each of the indices to a... 4) ...copy of the row

Let's try to map these to the expressions we have, starting from the right:

      p_3
0 0 0
0 0 1
0 1 0
0 1 1
0 1 2

   npd p_3
2 3 3 3 4

   (p_3 npc npd p_3)
0 1 0 1 2 0 1 2 0 1 2 0 1 2 3

   npc f.
;@:(i.&.>)@]

   npc npd p_3                  NB. Left argument not used
0 1 0 1 2 0 1 2 0 1 2 0 1 2 3

   npc f. npd f.
;@:(i.&.>)@] >:@#@~."1

   ;@:(i.&.>)@] >:@#@~."1 p_3
0 1 0 1 2 0 1 2 0 1 2 0 1 2 3  NB. Still works

   ; i.&.> >: # ~."1 p_3
0 1 2 3 4 5                    NB. Hmm...

      ~."1 p_3
0 0 0
0 1 0
0 1 0
0 1 0
0 1 2

   #"1 ~."1 p_3
3 3 3 3 3

   #@~."1 p_3
1 2 2 2 3

   ~."1&.> <"1 p_3
┌─┬───┬───┬───┬─────┐
│0│0 1│0 1│0 1│0 1 2│
└─┴───┴───┴───┴─────┘

   >:@# each ~."1&.> <"1 p_3
┌─┬─┬─┬─┬─┐
│2│3│3│3│4│
└─┴─┴─┴─┴─┘

Ah, we have to do our work before a fill is applied.

That's probably why we need each with i. in npc as well.

   [ nubis =. npd p_3
2 3 3 3 4

   npc nubis
0 1 0 1 2 0 1 2 0 1 2 0 1 2 3

   i."0 nubis
0 1 0 0
0 1 2 0
0 1 2 0
0 1 2 0
0 1 2 3

   , i."0 nubis
0 1 0 0 0 1 2 0 0 1 2 0 0 1 2 0 0 1 2 3

   ,@:i."0 nubis
0 1 0 0
0 1 2 0
0 1 2 0
0 1 2 0
0 1 2 3                                    NB. Hmm...

   ,@:(i."0) nubis
0 1 0 0 0 1 2 0 0 1 2 0 0 1 2 0 0 1 2 3    NB. Oh right

   i. each nubis
┌───┬─────┬─────┬─────┬───────┐
│0 1│0 1 2│0 1 2│0 1 2│0 1 2 3│
└───┴─────┴─────┴─────┴───────┘

   ; i. each nubis
0 1 0 1 2 0 1 2 0 1 2 0 1 2 3              NB. Neat

Zooming past the rank and fill issues, what we are really doing is:

   a =. (<'partition'), <"1 a3
   b =. (<'# old parts'), <"0 #@~."1 a3
   c =. (<'# new parts'), <"0 npd a3
   d =. (<'possible parts'), i. each nubis
   a ,. b ,. c ,. d
┌─────────┬───────────┬───────────┬──────────────┐
│partition│# old parts│# new parts│possible parts│
├─────────┼───────────┼───────────┼──────────────┤
│0 0 0    │1          │2          │0 1           │
├─────────┼───────────┼───────────┼──────────────┤
│0 0 1    │2          │3          │0 1 2         │
├─────────┼───────────┼───────────┼──────────────┤
│0 1 0    │2          │3          │0 1 2         │
├─────────┼───────────┼───────────┼──────────────┤
│0 1 1    │2          │3          │0 1 2         │
├─────────┼───────────┼───────────┼──────────────┤
│0 1 2    │3          │4          │0 1 2 3       │
└─────────┴───────────┴───────────┴──────────────┘

If we wanted to verbalise the algorithm:

   partitions =: p_3
   count_parts =: #@~.
   assign_elements =: ;@:(i. each)
   replicate =: #
   add =: ,"1 0

   npv =: (replicate~ add assign_elements@]) (1+count_parts)"1
   
   npv p_3
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 0 1 2
0 1 0 0
0 1 0 1
0 1 0 2
0 1 1 0
0 1 1 1
0 1 1 2
0 1 2 0
0 1 2 1
0 1 2 2
0 1 2 3

   (new_parts replicate partitions) add (assign_elements new_parts =: (1+count_parts)"1 p_3)
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 0 1 2
0 1 0 0
0 1 0 1
0 1 0 2
0 1 1 0
0 1 1 1
0 1 1 2
0 1 2 0
0 1 2 1
0 1 2 2
0 1 2 3

Coming back to our original (slightly modified) version, and the steps of the algorithm:

1) taking each row
2) finding its nub+1 indices `i.>:#~.`
3) appending each of the indices to a...
4) ...copy of the row

We can see where each step takes place:

              nextpart
            (#~ ,"1 0 ;@:(i.&.>)@]) (1 + #@~.)"1
             ┬  ──┬──    ─┬────      ──┬────  ─┬
     (4) ────┘    │       │            │       └─── (1)
                 (3)      └────────────┴─── (2)
                 
   (new_parts replicate partitions) add (assign_elements new_parts =: (1+count_parts)"1 p_3)
                 (4)                (3)            (2)                               (1)

This might be obvious, but I wasn't actually sure the order of steps would remain the same between the tacit and expression versions!

Finally, here's a comparison to another fairly concise language I know, Clojure:

(into []
  (mapcat (fn [part] ;; ─── (1)
            (let [p_count (count (into #{} part))] ;; ─┐
              (map #(conj part %) ;; ─── (3,4)         ├── (2)
                   (range (inc p_count))))))       ;; ─┘
  p_3)

The control flow is more mixed up, and even if one were to only count symbols and ignore punctuation, the J solution is still quite a bit more concise.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment