In one of my more successful years I studied partitions as well, see http://www.jsoftware.com/pipermail/programming/2006-September/003209.html
R.E. Boss > -----Original Message----- > From: Programming [mailto:[email protected]] > On Behalf Of Rob B > Sent: zondag 22 oktober 2017 11:40 > To: [email protected] > Subject: Re: [Jprogramming] Partitions > > In the twelvefold way at https://www.johndcook.com/TwelvefoldWay.pdf I > think this is case 6, labelled, unlabelled, >=1. > > Regards, Rob. > > > On 22 Oct 2017, at 01:29, Rob Hodgkinson <[email protected]> wrote: > > > > Skip, not sure the status of a solution for this yet (Raul’s was last > > closest I > believe ?). > > > > I thought through the following analysis over the weekend, more around > combinatorics. > > > > Problem is to split a list of objects o, into y “buckets” and you want to > > all the > ways possible given the constraints below. > > > > A combinatoric view is to consider filling each bucket (without > > replacement) until no more objects, for example; Suppose 7 objects (e.g. > ‘abcdefg’) split into 3 buckets of size 2 3 2. > > There are 2C7 (or 2!7) ways to fill the first bucket, leaving 5 left. > > From these 5 there are then 3!5 ways to fill the second bucket, leaving 2 > left. > > From these 2 there are then 2!2 ways to fill the last bucket > > > > The combinations (with decreasing sample sets) can be calculated as > follows (I pasted in Courier New, hope this appears OK). > > smoutput bset=:(+/bsize)- +/\ 0,}:bsize=:2 3 2 > > 7 5 2 > > > > So from the reducing sample from which to fill each successive bucket, the > possible combinations are: > > bsize ! bset=:(+/bsize)- +/\ 0,}:bsize=:2 3 2 > > 21 10 1 > > > > And the combinations in each bucket are then “indices” within each bucket > from the available objects remaining; > > smoutput bcombs=:bsize comb each bset=:(+/bsize)- +/\ 0,}:bsize=:2 3 > > 2 ┌───┬─────┬───┐ > > │0 1│0 1 2│0 1│ > > │0 2│0 1 3│ │ > > │0 3│0 1 4│ │ > > │0 4│0 2 3│ │ > > │0 5│0 2 4│ │ > > │0 6│0 3 4│ │ > > │1 2│1 2 3│ │ > > │1 3│1 2 4│ │ > > │1 4│1 3 4│ │ > > │1 5│2 3 4│ │ > > │1 6│ │ │ > > │2 3│ │ │ > > │2 4│ │ │ > > │2 5│ │ │ > > │2 6│ │ │ > > │3 4│ │ │ > > │3 5│ │ │ > > │3 6│ │ │ > > │4 5│ │ │ > > │4 6│ │ │ > > │5 6│ │ │ > > └───┴─────┴───┘ > > So for example the first row in each bucket only says e.g. from ‘abcdefg’, > choose (‘ab’;’cde’;’fg’), the first “trial”. > > $ each bcombs > > ┌────┬────┬───┐ > > │21 2│10 3│1 2│ > > └────┴────┴───┘ > > > > This shows there would be 210 possible combinations (trials), although I am > unclear on your rule 5 below, to remove “like” combinations, but this could > be achieved post the algorithm. > > To get the actual 210 samples you could then index into each cell, but the > “samples remaining” would then change for each combination. > > > > For example, bucket1 is straightforward to calculate, along with the > remainder samples available to fill the remaining buckets … > > smoutput bucket1=:'abcdefg' {~ >{.bcombs ab ac ad ae af ag bc bd be > > bf bg cd ce cf cg de df dg ef eg fg > > bucket1;'abcdefg'-."1 bucket1 > > ┌──┬─────┐ > > │ab│cdefg│ > > │ac│bdefg│ > > │ad│bcefg│ > > │ae│bcdfg│ > > │af│bcdeg│ > > │ag│bcdef│ > > │bc│adefg│ > > │bd│acefg│ > > │be│acdfg│ > > │bf│acdeg│ > > │bg│acdef│ > > │cd│abefg│ > > │ce│abdfg│ > > │cf│abdeg│ > > │cg│abdef│ > > │de│abcfg│ > > │df│abceg│ > > │dg│abcef│ > > │ef│abcdg│ > > │eg│abcdf│ > > │fg│abcde│ > > └──┴─────┘ > > The steps would be repeated for each product, at each stage “expanding” > the combinations within each bucket by the successive indices (avoiding > selecting any items already in existing buckets). > > This will become a cartesian product of samples at each iteration to > generate the final 210 samples. > > > > This would likely involve recursion or some form of (f ,/), but wanted to > check my understanding is on track. It may make the solution clearer. > > > > I hope this makes sense, Rob > > > >> On 21 Oct 2017, at 10:06 am, 'Skip Cave' via Programming > <[email protected]> wrote: > >> > >> Perhaps here is a better way to describe the problem I was trying to solve: > >> > >> 1. I have y unique objects. I have x containers. I want to find all > >> the different ways I can put those y unique objects into x containers. > >> > >> 2. A single trial is defined as distributing *all* y of the objects > >> into all of the x containers. After the trial, the objects are > >> removed from the containers and redistributed in the containers for > >> the next trial. Objects can not be duplicated. > >> > >> 3. Empty containers are not allowed in any trial. There must be at > >> least one object in every container in every trial. > >> > >> 4. There is no order requirement for objects in a container. If two > >> trials are identical except for the order of the objects in any of > >> the containers, those two trials are considered as one trial. > >> > >> 5. There is no order requirement for the containers. If two trials > >> are identical in that both trials have the same number of objects in > >> each of the x containers, but the order of the containers is > >> different, those two trials are considered as one trial. > >> > >> Skip > >> > >> Skip Cave > >> Cave Consulting LLC > >> > >>> On Fri, Oct 20, 2017 at 3:54 AM, Raul Miller <[email protected]> > wrote: > >>> > >>> With that description, I think I might do something like this: > >>> > >>> nparts=: ~.@([: /:~"1 i.@] </."1~ [ #.^:_1 [ i.@^ ]) > >>> 2 nparts 3 > >>> ┌───┬─────┐ > >>> │ │0 1 2│ > >>> ├───┼─────┤ > >>> │0 1│2 │ > >>> ├───┼─────┤ > >>> │0 2│1 │ > >>> ├───┼─────┤ > >>> │0 │1 2 │ > >>> └───┴─────┘ > >>> > >>> I should be able to do something more efficient, but before I > >>> attempt that, I would like to clarify something: > >>> > >>> In your examples, you do not have any empty partitions, so is that a > >>> part of the specification also? > >>> > >>> I am unsure if I should be paying close attention to your examples > >>> because you said "The order of the objects in each partition is not > >>> important" but your examples also omit partitions which contain the > >>> objects out of order. > >>> > >>> Actually... there's several kinds of order here which we could be > >>> discussing: > >>> > >>> (1) the order of objects within a partition. > >>> (2) the order of objects across partitions. > >>> (3) the order of partitions. > >>> > >>> In other words: > >>> > >>> NB. (1) the order of objects within a partition \:~each 2 nparts 3 > >>> ┌───┬─────┐ > >>> │ │2 1 0│ > >>> ├───┼─────┤ > >>> │1 0│2 │ > >>> ├───┼─────┤ > >>> │2 0│1 │ > >>> ├───┼─────┤ > >>> │0 │2 1 │ > >>> └───┴─────┘ > >>> > >>> NB. (2) the order of objects across partitions > >>> 2 ~.@([: \:~"1 i.@] </."1~ [ #.^:_1 [ i.@^ ]) 3 ┌─────┬───┐ > >>> │0 1 2│ │ > >>> ├─────┼───┤ > >>> │2 │0 1│ > >>> ├─────┼───┤ > >>> │1 │0 2│ > >>> ├─────┼───┤ > >>> │1 2 │0 │ > >>> └─────┴───┘ > >>> > >>> NB. (3) the order of partitions > >>> 2 ((i.@[ ,"1 [ #.^:_1 i.@^) <@}./."1 {. , i.@]) 3 ┌─────┬─────┐ > >>> │0 1 2│ │ > >>> ├─────┼─────┤ > >>> │0 1 │2 │ > >>> ├─────┼─────┤ > >>> │0 2 │1 │ > >>> ├─────┼─────┤ > >>> │0 │1 2 │ > >>> ├─────┼─────┤ > >>> │1 2 │0 │ > >>> ├─────┼─────┤ > >>> │1 │0 2 │ > >>> ├─────┼─────┤ > >>> │2 │0 1 │ > >>> ├─────┼─────┤ > >>> │ │0 1 2│ > >>> └─────┴─────┘ > >>> > >>> I have presumed that you are thinking of both the partition contents > >>> and the partitions themselves as sets. In other words, I think that > >>> none of these orders matter. But... this kind of thing is worth > >>> verifying? > >>> > >>> Thanks, > >>> > >>> -- > >>> Raul > >>> > >>> On Fri, Oct 20, 2017 at 12:19 AM, 'Skip Cave' via Programming > >>> <[email protected]> wrote: > >>>> Mike, > >>>> > >>>> I wasn't very thorough in my definition of the original problem. I > >>> thought > >>>> that the example I gave was enough to clarify the requirements, but > >>> looking > >>>> back, more definition would have been good. > >>>> > >>>> The original problem I posted was to develop a dyadic verb that > >>>> would > >>> take > >>>> y objects and show all the ways that those y objects could be > >>>> partitioned into x groups. Each partition set must include all objects > exactly once. > >>>> Duplication of objects is not allowed. The order of the objects in > >>>> each partition is not important. > >>>> > >>>> Erling got the right idea in his previous post: > >>>> > >>>> par=: 4 : '(1,.2</\"1(i.x)#/~(y=+/"1 o)#o=.((x$v)#:i.v^x){1+i.v=.1+ > >>>> y-x)<;.1[1+i.y' > >>>> > >>>> 2 par 3 > >>>> ┌───┬───┐ > >>>> │1 │2 3│ > >>>> ├───┼───┤ > >>>> │1 2│3 │ > >>>> └───┴───┘ > >>>> 2 par 4 > >>>> ┌─────┬─────┐ > >>>> │1 │2 3 4│ > >>>> ├─────┼─────┤ > >>>> │1 2 │3 4 │ > >>>> ├─────┼─────┤ > >>>> │1 2 3│4 │ > >>>> └─────┴─────┘ > >>>> 2 par 5 > >>>> ┌───────┬───────┐ > >>>> │1 │2 3 4 5│ > >>>> ├───────┼───────┤ > >>>> │1 2 │3 4 5 │ > >>>> ├───────┼───────┤ > >>>> │1 2 3 │4 5 │ > >>>> ├───────┼───────┤ > >>>> │1 2 3 4│5 │ > >>>> └───────┴───────┘ > >>>> 3 par 4 > >>>> ┌───┬───┬───┐ > >>>> │1 │2 │3 4│ > >>>> ├───┼───┼───┤ > >>>> │1 │2 3│4 │ > >>>> ├───┼───┼───┤ > >>>> │1 2│3 │4 │ > >>>> └───┴───┴───┘ > >>>> 3 par 5 > >>>> ┌─────┬─────┬─────┐ > >>>> │1 │2 │3 4 5│ > >>>> ├─────┼─────┼─────┤ > >>>> │1 │2 3 │4 5 │ > >>>> ├─────┼─────┼─────┤ > >>>> │1 │2 3 4│5 │ > >>>> ├─────┼─────┼─────┤ > >>>> │1 2 │3 │4 5 │ > >>>> ├─────┼─────┼─────┤ > >>>> │1 2 │3 4 │5 │ > >>>> ├─────┼─────┼─────┤ > >>>> │1 2 3│4 │5 │ > >>>> └─────┴─────┴─────┘ > >>>> 3 par 6 > >>>> ┌───────┬───────┬───────┐ > >>>> │1 │2 │3 4 5 6│ > >>>> ├───────┼───────┼───────┤ > >>>> │1 │2 3 │4 5 6 │ > >>>> ├───────┼───────┼───────┤ > >>>> │1 │2 3 4 │5 6 │ > >>>> ├───────┼───────┼───────┤ > >>>> │1 │2 3 4 5│6 │ > >>>> ├───────┼───────┼───────┤ > >>>> │1 2 │3 │4 5 6 │ > >>>> ├───────┼───────┼───────┤ > >>>> │1 2 │3 4 │5 6 │ > >>>> ├───────┼───────┼───────┤ > >>>> │1 2 │3 4 5 │6 │ > >>>> ├───────┼───────┼───────┤ > >>>> │1 2 3 │4 │5 6 │ > >>>> ├───────┼───────┼───────┤ > >>>> │1 2 3 │4 5 │6 │ > >>>> ├───────┼───────┼───────┤ > >>>> │1 2 3 4│5 │6 │ > >>>> └───────┴───────┴───────┘ > >>>> > >>>> Skip Cave > >>>> Cave Consulting LLC > >>>> > >>>> On Thu, Oct 19, 2017 at 5:47 PM, 'Mike Day' via Programming < > >>>> [email protected]> wrote: > >>>> > >>>>> Skip, in your actual Quora Problem, why not include other triads, > >>>>> such as 1 1 24, 2 3 4 etc; or, otherwise, why include both 2 4 3 > >>> and 4 > >>>>> 2 3 ? > >>>>> > >>>>> Anyway, this is (quite) short and brutish but not too nasty to > >>>>> solve > >>> your > >>>>> Quora problem for quite small numbers and numbers of factors: > >>>>> > >>>>> |: 24 ([ ( (= */"1)#]) [:>:[#.inv i.@^ ) 3 NB. transpose > >>> gratuitous! > >>>>> 1 1 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 4 4 4 4 6 6 6 8 8 12 12 > >>>>> 24 > >>>>> 1 2 3 4 6 8 12 24 1 2 3 4 6 12 1 2 4 8 1 2 3 6 1 2 4 1 3 1 2 1 > >>>>> 24 12 8 6 4 3 2 1 12 6 4 3 2 1 8 4 2 1 6 3 2 1 4 2 1 3 1 2 1 > >>>>> 1 > >>>>> > >>>>> It builds triads 1 1 1 , 1 1 2 ,...1 1 24, ... up to 24 24 24, and > >>>>> keeps > >>>>> > >>>>> just those whose product is 24. > >>>>> > >>>>> > >>>>> No points for space or time, filtering 30 out of 13824 candidates, > >>>>> but > >>> it's > >>>>> > >>>>> quite straightforward, and it does yield all 30 permutations, > >>>>> which > >>> some > >>>>> > >>>>> of the Quora corresondents appear to consider the requirement. > >>>>> > >>>>> > >>>>> NB - it's not clear to me what the problem actually is - is 30 the > >>> required > >>>>> > >>>>> answer (number of permutations of 3 suitable factors), or 6 > >>>>> (number of > >>>>> > >>>>> combinations of same)? > >>>>> > >>>>> > >>>>> Mike > >>>>> > >>>>> > >>>>> > >>>>> > >>>> ------------------------------------------------------------------- > >>>> --- 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
