Hi all !
I wanted to make sure the algorithms worked and gave correct results, so
I made a comparison.
See below.
Cheers,
Erling Hellenäs
-----Project---
ts=: 6!:2 , 7!:2@] NB. Time and space
normalize=: 3 :0
NB. The idea here is to normalize the representation so that
NB. the copies are adjacent.
NB. Sort buckets within each combination after first item in each bucket
v31=.(] /: {.&.>)"1 y
NB. Sort buckets within each combination after number of items in each
bucket
v4=.(] /: #&.>)"1 v31
NB. Remove duplicates, sort to show nicely
/:~ ~.v4
)
compare=: -:&:normalize
NB. Esa Lippu
parEL=: 4 : 0
a=.(y#x) #: i. x^y
sort ~.((x=#@~."1 a)#a) </."1 i.y
)
NB. Raul
parR=: (#~ 1 - a: e."1 ])@~.@([: /:~"1 i.@] </."1~ [ #.^:_1 [ i.@^ ])
NB. Erling
combE=: 3 : '(m{.#:i.m=.(0~:#y)*<.2^#y) <@# y'
parE =: 4 : 0
NB. All combinations of all items
v=.}.combE i.y
NB. Select combinations with less than or equal to 1+y-x items
v1=.((#&> v)<:1+y-x)#v
NB. All combinations in all buckets
v2=. > , ,&.>//>x#<<"0 v1
NB. Select combinations with one and only one of each number
v3=.(((i.y) -: /:~@:;) "1 v2) # v2
NB. The idea here is to normalize the representation so that
NB. the copies are adjacent.
NB. Sort buckets within each combination after first item in each bucket
v31=.(] /: {.&.>)"1 v3
NB. Sort buckets within each combination after number of items in each
bucket
v4=.(] /: #&.>)"1 v31
NB. Remove duplicates, sort to show nicely
/:~ ~.v4
)
x=:1
y=:1
[EL=:x parEL y
[R=:x parR y
[E=:x parE y
EL compare R
EL compare E
R compare E
x=:1
y=:2
[EL=:x parEL y
NB.[R=:x parR y - Length Error
[E=:x parE y
EL compare R
EL compare E
R compare E
x=:1
y=:3
[EL=:x parEL y
NB. R=:x parR y - Length Error
[E=:x parE y
EL compare R
EL compare E
R compare E
x=:2
y=:4
[EL=:x parEL y
[R=:x parR y
[E=:x parE y
EL compare R
EL compare E
R compare E
x=:2
y=:5
EL=:x parEL y
R=:x parR y
E=:x parE y
EL compare R
EL compare E
R compare E
x=:3
y=:5
EL=:x parEL y
R=:x parR y
E=:x parE y
EL compare R
EL compare E
R compare E
x=:3
y=:6
EL=:x parEL y
R=:x parR y
E=:x parE y
EL compare R
EL compare E
R compare E
ts'x parEL y'
ts'x parR y'
ts'x parE y'
----------Result printout----
x=:1
y=:1
[EL=:x parEL y
┌─┐
│0│
└─┘
[R=:x parR y
┌─┐
│0│
└─┘
[E=:x parE y
┌─┐
│0│
└─┘
EL compare R
1
EL compare E
0
R compare E
0
x=:1
y=:2
[EL=:x parEL y
┌───┐
│0 1│
└───┘
NB.[R=:x parR y - Length Error
[E=:x parE y
EL compare R
0
EL compare E
0
R compare E
0
x=:1
y=:3
[EL=:x parEL y
┌─────┐
│0 1 2│
└─────┘
NB. R=:x parR y - Length Error
[E=:x parE y
EL compare R
0
EL compare E
0
R compare E
0
x=:2
y=:4
[EL=:x parEL y
┌─────┬─────┐
│0 │1 2 3│
├─────┼─────┤
│0 1 │2 3 │
├─────┼─────┤
│0 1 2│3 │
├─────┼─────┤
│0 1 3│2 │
├─────┼─────┤
│0 2 │1 3 │
├─────┼─────┤
│0 2 3│1 │
├─────┼─────┤
│0 3 │1 2 │
└─────┴─────┘
[R=:x parR y
┌─────┬─────┐
│0 1 2│3 │
├─────┼─────┤
│0 1 3│2 │
├─────┼─────┤
│0 1 │2 3 │
├─────┼─────┤
│0 2 3│1 │
├─────┼─────┤
│0 2 │1 3 │
├─────┼─────┤
│0 3 │1 2 │
├─────┼─────┤
│0 │1 2 3│
└─────┴─────┘
[E=:x parE y
┌───┬─────┐
│0 │1 2 3│
├───┼─────┤
│0 1│2 3 │
├───┼─────┤
│0 2│1 3 │
├───┼─────┤
│0 3│1 2 │
├───┼─────┤
│1 │0 2 3│
├───┼─────┤
│2 │0 1 3│
├───┼─────┤
│3 │0 1 2│
└───┴─────┘
EL compare R
1
EL compare E
1
R compare E
1
x=:2
y=:5
EL=:x parEL y
R=:x parR y
E=:x parE y
EL compare R
1
EL compare E
1
R compare E
1
x=:3
y=:5
EL=:x parEL y
R=:x parR y
E=:x parE y
EL compare R
1
EL compare E
1
R compare E
1
x=:3
y=:6
EL=:x parEL y
R=:x parR y
E=:x parE y
EL compare R
1
EL compare E
1
R compare E
1
ts'x parEL y'
0.00202699 403840
ts'x parR y'
0.00232291 465280
ts'x parE y'
0.150278 4.75155e7
Den 2017-10-26 kl. 18:22, skrev 'Skip Cave' via Programming:
Rob's analysis assumes that each bucket must contain a fixed number of
objects. In my problem, each bucket can hold any number of objects.
However, in each trial, every bucket must hold at least one object. Of
course, that means that for a specific x & y, the most that any bucket can
hold is y-x-1 where y is the number of objects, and x is the number of
buckets.
Skip Cave
Cave Consulting LLC
On Sat, Oct 21, 2017 at 7:29 PM, 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
