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
