Hmm... right - it corresponds to an upper (or lower) triangular matrix, not the identity matrix. So...
(|.>:/~i.x)#&(,/)(i.x)+(1 j.(i.x)=/-~/~i.x)#"1"_1-~/~i.x In other words, once again, oops. (But at least, this time, I tested the expression. Though I know it could be refactored to be more concise-- but the phone UI is too clumsy for that...) Thanks, -- Raul On Wednesday, November 22, 2017, 'Mike Day' via Programming < [email protected]> wrote: > I was going to say that that’s a nice special case and I hadn’t quite got > there! > > But it misses several cases, eg > 01203, 01023 and so on. There are 10 partitions in all. > > What a pity, > > Mike > > Please reply to [email protected] <javascript:;>. > Sent from my iPad > > > On 22 Nov 2017, at 22:51, Raul Miller <[email protected] > <javascript:;>> wrote: > > > > Oops, sorry, yes. > > > > I was expecting exponential growth to make the results unrepresentable. > But > > that only happens at the low end (of the x values). > > > > I guess maybe just set a=:u:i.48+n > > > > That said, note that when x=y-1 you can use a result of the form > > (1+=i.x)#"1 i.x > > > > Thanks, > > > > -- > > Raul > > > > On Wednesday, November 22, 2017, 'Mike Day' via Programming < > > [email protected] <javascript:;>> wrote: > > > >> How’s that, Raul? > >> > >> Wouldn’t ParXXX / 300 400 (Heaven forbid!) need 300 things, whether > >> integers, symbols or what you will? > >> > >> What have I misunderstood? > >> > >> Cheers, > >> > >> Mike > >> > >> > >> Please reply to [email protected] <javascript:;> > <javascript:;>. > >> Sent from my iPad > >> > >>> On 22 Nov 2017, at 21:56, Raul Miller <[email protected] > <javascript:;> > >> <javascript:;>> wrote: > >>> > >>> The only case where you need more than 256 symbols is when the left > >>> arg matches the right arg. > >>> > >>> For that case, it's reasonable to produce the result u:i.1,y > >>> > >>> Thanks, > >>> > >>> -- > >>> Raul > >>> > >>> On Wed, Nov 22, 2017 at 2:05 PM, 'Mike Day' via Programming > >>> <[email protected] <javascript:;> <javascript:;>> wrote: > >>>> Here's another shot at a non-recursive constructive approach to > >> generating > >>>> RGFs. > >>>> It continues to use characters to store and represent the RGFs. It > >> would > >>>> need > >>>> reworking if there were more than 256 digits/symbols, though I think > >> we'd > >>>> hit other > >>>> problems before needing to worry about representation in such cases. > >>>> > >>>> Performance is reasonable if not outstanding, similar to or a bit > >> better > >>>> than parMD. > >>>> > >>>> I think it's a bit easier to understand than my earlier effort. I > hope > >> the > >>>> comments in > >>>> the following script help. > >>>> > >>>> NB. Please take care with line-wrapping... > >>>> > >>>> makeinsert =: 3 : 0 M. NB. to memoise or not to memoise? > >>>> a =. a. |.~ a. i. '0' NB. symbol list - arbitrary, but '012...' > >> here > >>>> 'd g' =. 1 0 + y > >>>> a{~ d #.inv i. d^g > >>>> ) > >>>> > >>>> join =: 3 : 0 > >>>> : > >>>> nx =. #x [ ny =. #y > >>>> (ny#x),. (,y)$~ (nx,1) * $y > >>>> ) > >>>> > >>>> NB. join =: ,/@(,"1/) > >>>> > >>>> NB. Generate all RGFs, each using at least one of each symbol/digit > >> 0123...k > >>>> representing > >>>> NB. (k+1)partitions > >>>> NB. Method: let a "basic" RGF for 4 symbols be, eg, 0001002000300, > >>>> NB. ie having exactly one of each non-zero > >>>> NB. This example has gaps of size 2 3 and 2 again between digits 1&2, > >> 2&3, > >>>> and 3&[end] respectively > >>>> NB. it is the template for many derived RGFs. > >>>> NB. A derived RGF is based on a basic RGF with arbitrary > >> digits > >>>> replacing zeros in the gaps, > >>>> NB. subject to added digits not exceeding the left hand > >> boundary > >>>> of the gap. > >>>> NB. eg, the sequence 20003 may have some or all of the 3 > >> zeros > >>>> replaced by 1 or 2 but not 3 > >>>> > >>>> NB. 3 helper functions: x join y : x ,/@(,"1/) y, but seems better in > >>>> explicit code!? > >>>> NB. - concatenates all rows of x with all rows of > y > >>>> > >>>> NB. makeinsert d,g : form a table with g columns > >>>> NB. of all possible perms of 0 1 > 2 > >> ... > >>>> d > >>>> NB. to yield all suitable > >> replacements > >>>> for g zeros > >>>> > >>>> NB. comb - as in stats.ijs, or otherwise, > >> according to > >>>> taste! > >>>> > >>>> require'stats' > >>>> > >>>> rgfMD =: 3 : 0 > >>>> : > >>>> k =. <: x > >>>> n =. y > >>>> a =. a. |.~ a. i. '0' NB. symbol list - arbitrary, but '012...' > >> here > >>>> if. x > n do. NB. special-case impossible partitions > >>>> ' '$~ 0, n return. > >>>> elseif. x = 1 do. NB. special-case 1-partition > >>>> ,: n#{.a return. > >>>> elseif. x = 2 do. NB. special-case 2-partition > >>>> a{~ (n#2) #: }. i. 2 ^ n-1 return. > >>>> elseif. x = n do. NB. special-case n-partition > >>>> ,: n{.a return. > >>>> end. > >>>> c =. >: k comb <:n NB. possible start cols for 1 2 ... k > >>>> g =. <: +/\inv"1] c =. c,. n NB. sizes of gaps between starts of > 1 > >> 2 3 > >>>> ... for each RGF pattern > >>>> a =. a. }.~ a. i. '0' NB. symbol list - arbitrary, but '012...' > >> here > >>>> out =. ' '$~ 0, n > >>>> for_i. i.#c do. NB. loop for each patterns of start cols > >>>> gi =. i{g > >>>> new =. 1 0$a NB. defer setting initial zeros > >>>> for_j. }.i.#gi do. NB. loop over non-zero digits > >>>> new=. new,. j{a NB. append next non-zero digit > >>>> gj =. j{ gi NB. size of following gap > >>>> if. gj do. NB. if size of gap is non-zero, append all > >>>> gap-sized sets of 0 1 ... j > >>>> new =. new join makeinsert j, gj > >>>> end. > >>>> end. > >>>> out =. out, new join~ a{~ ,: 0{. ~ -{.i{c NB. prepend initial > >> zeros > >>>> end. > >>>> ) > >>>> > >>>> makeinsert =: 3 : 0 M. > >>>> a =. a. }.~ a. i. '0' NB. symbol list - arbitrary, but '012...' > >> here > >>>> 'd g' =. 1 0 + y > >>>> a{~ d #.inv i. d^g > >>>> ) > >>>> > >>>> join =: 3 : 0 > >>>> : > >>>> nx =. #x [ ny =. #y > >>>> (ny#x),. (,y)$~ (nx,1) * $y > >>>> ) > >>>> > >>>> NB. join =: ,/@(,"1/) NB. explicit verb seems better!? > >>>> > >>>> Cheers, > >>>> > >>>> Mike > >>>> > >>>> > >>>> > >>>> > >>>>> On 17/11/2017 18:14, '[email protected] <javascript:;> > <javascript:;>' via > >> Programming wrote: > >>>>> > >>>>> Erling Helenas, Raul Miller, and others have come up with various > >>>>> methods to generate subsets of “restricted generating functions” > (RGFs) > >>>>> suitable for the production of partitions of sets. Several of these > >>>>> have used Ruskey’s algorithm. > >>>>> > >>>>> I’ve found a fairly simple approach which has the benefits of (a) not > >>>>> being recursive, (b) being fairly easy to understand, and (c) not > >>>>> generating redundant data needing later filtering. It does, > however, > >>>>> use a loop, albeit needing fewer loops than the final number of > rows, > >>>>> ie RGFs . > >>>>> > >>>>> It saves a fair amount of space by using a character array of symbols > >>>>> rather than integers to represent the RGFs. A character string > serves > >>>>> equally as well as an integer vector as left argument to </. for the > >>>>> generation of boxed partitions. > >>>>> > >>>>> Key features, which might be improved upon, include the local verb > >>>>> “ki” which yields the index of that element in an RGF which needs to > be > >>>>> incremented in generating the next RGF, and a number of small > look-up > >>>>> mini-arrays useful in finding the next appropriate few RGFs. > >>>>> > >>>>> Its performance compares favourably with other recent offerings. > >>>>> > >>>>> There is one main verb, “parMD”, and a helper verb, “makeblock”, > >>>>> which constructs one of the look-up arrays. > >>>>> > >>>>> Here it is; look out for line-wraps, though it looks ok this end! > :- > >>>>> > >>>>> > >>>>> ============================================================ > >> ============================== > >>>>> NB. produce a table of "restricted growth functions" (rgf) (strings > of > >>>>> symbols) subject to > >>>>> NB. requirement that each "function" (or string) includes at least > one > >>>>> instance of each symbol > >>>>> NB. eg 001100 is an rgf, but if all the symbols '012' are required, > >>>>> it's not suitable here > >>>>> NB. eg an rgf such as 001213 is a suitable equivalent to > >>>>> NB. |01|24|3|5|, a 4-partition for 6 elements > >>>>> > >>>>> NB. Any symbols may be used, but they are subject to an implicit or > >>>>> explicit ordering. > >>>>> > >>>>> parMD =: 3 : 0 > >>>>> y parMD~ <:#y > >>>>> : > >>>>> k =. <: x > >>>>> NB. starting/current row > >>>>> if. 1 = #y do. > >>>>> list =. ,: cur =. (-y){.i.x > >>>>> else. NB. Admit a starting row (of integers, not symbols) other > than > >>>>> 0 0 0 1 2 ... > >>>>> NB. NB. not tested here for validity!!! > >>>>> list =. ,: cur =. y > >>>>> end. > >>>>> n =. #cur > >>>>> a =. a. }.~ a. i. '0' NB. symbol list - arbitrary, but '012...' > >>>>> here > >>>>> if. x > n do. NB. special-case impossible partitions > >>>>> ' '$~ 0, n > >>>>> elseif. x = 1 do. NB. special-case 1-partition > >>>>> ,: n#{.a > >>>>> elseif. x = 2 do. NB. special-case 2-partition > >>>>> a{~ (n#2) #: }. i. 2 ^ n-1 > >>>>> elseif. x = n do. NB. special-case n-partition > >>>>> ,: n{.a > >>>>> elseif. 1 do. > >>>>> NB. I use the term k-partition, below, loosely - it should be x- > >>>>> partition or (k+1)-partn. > >>>>> list =. a {~ list NB. output as char array, offset so that 0 1 > 2 > >>>>> ... <==> '012...' > >>>>> NB. end =. k <. i. n NB. preset last row if required for stopping > >>>>> condition > >>>>> incr =. =/~ i.n NB. look-up array for incrementing i{cur > >>>>> blnk =. +/\ incr NB. look-up array for blanking all elements > >>>>> after i{cur > >>>>> block=. x makeblock n NB. look-up array for forcing "new" rows to be > >> k- > >>>>> partition equivalents. > >>>>> ki =. >:@i:&1@:(}. < k <. >:@:(>./\)@:}:) NB. restricted growth > >>>>> function index finder, > >>>>> NB. modified for > >>>>> limitation to 1+k symbols > >>>>> while. n | i =. ki cur do. NB. test new index - stop if = n > >>>>> NB. one of several possible stopping conditions > - > >>>>> could test cur -: end > >>>>> new =. (i{incr) + cur*i{blnk NB. next suitable "restricted > growth > >>>>> function" > >>>>> mx =. >./ new NB. ALL values 0 1 2 ... k MUST appear for a k- > >>>>> partition > >>>>> NB. Adjust "new" if not already a k-partition equivalent, and expand > >>>>> to several rows > >>>>> new =. new +"1 >mx { block > >>>>> NB. eg 00101000 (invalid k-part if x>2) becomes 00101023, 00101123 > if > >>>>> (and only if) x = 4 > >>>>> list =. list, new { a > >>>>> cur =. {: new > >>>>> end. > >>>>> list > >>>>> end. > >>>>> ) > >>>>> > >>>>> NB. assemble look-up array of blocks > >>>>> NB. eg > >>>>> NB. 4 makeblock 5 > >>>>> NB. +---------+---------+---------+---------+ > >>>>> NB. |0 0 1 2 3|0 0 0 2 3|0 0 0 0 3|0 0 0 0 0| > >>>>> NB. | |0 0 1 2 3|0 0 0 1 3|0 0 0 0 1| > >>>>> NB. | | |0 0 0 2 3|0 0 0 0 2| > >>>>> NB. | | | |0 0 0 0 3| > >>>>> NB. +---------+---------+---------+---------+ > >>>>> makeblock =: 3 : 0 > >>>>> makeblock/ y > >>>>> : > >>>>> NB. a work-a-day method, not a smart implementation! > >>>>> m =. 0 > >>>>> b =. '' > >>>>> i =. i. x > >>>>> while. x >: m =. >: m do. > >>>>> b =. b, < (i.m),. m#,: i =. }. i > >>>>> end. > >>>>> (-y){."1 each b > >>>>> ) > >>>>> > >>>>> > >>>>> > >>>>> ============================================================ > >> ============================== > >>>>> > >>>>> eg - generate RGFs suitable for 4-partitions of 5 elements: > >>>>> parMD/ 4 5 > >>>>> 00123 > >>>>> 01023 > >>>>> 01123 > >>>>> 01203 > >>>>> 01213 > >>>>> 01223 > >>>>> 01230 > >>>>> 01231 > >>>>> 01232 > >>>>> 01233 > >>>>> > >>>>> (parMD/ 4 5)</."1 i.5 > >>>>> +---+---+---+---+ > >>>>> |0 1|2 |3 |4 | > >>>>> +---+---+---+---+ > >>>>> |0 2|1 |3 |4 | > >>>>> +---+---+---+---+ > >>>>> |0 |1 2|3 |4 | > >>>>> +---+---+---+---+ > >>>>> |0 3|1 |2 |4 | > >>>>> +---+---+---+---+ > >>>>> |0 |1 3|2 |4 | > >>>>> +---+---+---+---+ > >>>>> |0 |1 |2 3|4 | > >>>>> +---+---+---+---+ > >>>>> |0 4|1 |2 |3 | > >>>>> +---+---+---+---+ > >>>>> |0 |1 4|2 |3 | > >>>>> +---+---+---+---+ > >>>>> |0 |1 |2 4|3 | > >>>>> +---+---+---+---+ > >>>>> |0 |1 |2 |3 4| > >>>>> +---+---+---+---+ > >>>>> > >>>>> That's all for now! > >>>>> Mike > >>>>> > >>>>> ------------------------------------------------------------ > ---------- > >>>>> For information about J forums see http://www.jsoftware.com/ > forums.htm > >>>> > >>>> > >>>> > >>>> --- > >>>> This email has been checked for viruses by Avast antivirus software. > >>>> https://www.avast.com/antivirus > >>>> > >>>> ------------------------------------------------------------ > ---------- > >>>> For information about J forums see http://www.jsoftware.com/ > forums.htm > >>> ---------------------------------------------------------------------- > >>> For information about J forums see http://www.jsoftware.com/forums.htm > >> > >> ---------------------------------------------------------------------- > >> For information about J forums see http://www.jsoftware.com/forums.htm > > ---------------------------------------------------------------------- > > For information about J forums see http://www.jsoftware.com/forums.htm > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
