I’ve been trying to simply count solutions. The best I could do is with the
prime decomposition powers.
Say we want to find the number of unordered solutions to
n = */v
solving for vector v where n is a scalar, and both are non-negative integers.
Let p=: {: __ q: n.
Then we need to “partition” these powers into #v buckets.
For each x in p we need to calculate a sort of “ordered partition number” of x.
That is, in x=4 and 3 = #v:
4 + 0 + 0
0 + 4 + 0
0 + 0 + 4
3 + 1 + 0
3 + 0 + 1
1 + 3 + 0
1 + 0 + 3
0 + 3 + 1
0 + 1 + 3
2 + 1 + 1
1 + 2 + 1
1 + 1 + 2
are all possible “partitions” of x.
More specifically, we need to count the number of functions f from {1...#v} to
the naturals such that x = +/f”0 >:i.#v.
Then we could simply take the product of f applied to each of the items of p
and divide by !#v.
Unfortunately I doubt counting valid f is easy, and I haven’t found anything
yet.
Cheers,
Louis
> On 22 Oct 2017, at 12:53, R.E. Boss <[email protected]> wrote:
>
> 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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
