For my current use case I would need the set to be ordered and to not allow
null values ( I will further along need to build one that is still ordered
but allows null values to work with epsilon-producing rules but I'll look
at that case later ).
I see. If there is no word I have no problem implementing one, but I would
gladly receive feedback or provide a specification to look at how you would
implement it.
So, for the specification case:
I'm looking for a word that, given a positive integer k and a sequence of
objects seq of length n, with 1 <= k <= n, builds a sequence of all the
k-partitions of seq.
With partitions as defined above and with the remark at the top of this
message that the set is ordered.
( I've seen that for integer partitions, if the order matters, the result
is called a composition instead. I'm not sure if this is the same for
set-partittions as I couldn't find any relevant terminology, but I'm
intending a set-partition to be akin to an integer composition rather than
to integer partition )
For example:
"pqrs" 3 k-partitions .
{ { "pq" "r" "s" } { "p" "qr" "s" } { "p" "q" "rs" } }
"(i+i)xi" 3 k-partitions .
{
{ "(" "i" "+i)xi" }
{ "(" "i+" "+)xi" }
{ "(" "i+i" ")xi" }
{ "(" "i+i)" "xi" }
{ "(" "i+i)x" "i" }
{ "(i" "+" "i)xi" }
{ "(i" "+i" ")xi" }
{ "(i" "+i)" "xi" }
{ "(i" "+i)x" "i" }
{ "(i+" "i" ")xi" }
{ "(i+" "i)" "xi" }
{ "(i+" "i)x" "i" }
{ "(i+i" ")" "xi" }
{ "(i+i" ")x" "i" }
{ "(i+i)" "x" "i" }
}
This is what I would request if it is someone else who will do the
implementation.
If I am the one to do the implementation, then I'm a slave to the whims of
my curiosity.
Thus, even if in practice I need the above, I'm much more interested in
implementing the paper I linked to in my first post ( as It seems to have
inspired me in different ways for both factor and idris ) and would, then,
ask help with improving code that is related to this task.
For example, this is the stub implementation that I've done for the general
case of generating all unrestricted partitions:
<PRIVATE
>
> : expanding-child ( partition -- seq )
> unclip 1 - prefix 1 suffix ;
>
> : preserving-child ( partition -- seq )
> unclip 1 - prefix unclip-last 1 + suffix ;
>
> : has-an-expanding-child? ( partition -- ? )
> first2 > ;
>
> : has-a-preserving-child? ( partition -- ? )
> [ 2 tail* first2 [ > ] [ - 1 > ] 2bi ]
> [ length 2 > ]
> bi or and ;
>
> : children ( partition -- )
> [ has-an-expanding-child? ] [
> [ expanding-child [ , ] [ children ] bi ]
> [ [ has-a-preserving-child? ] [ preserving-child [ children ] [ ,
> ] bi ] smart-when* ] bi
> ] smart-when* ;
>
> PRIVATE>
>
> : partitions ( n -- partitions )
> [
> 1 - 1 2array [ [ children ] { } make ] [ prefix ] bi
> ] [ 1array prefix ] bi ;
>
> : split-partitions ( seq -- partitions )
> dup length partitions [ 0 [ + ] accumulate* split-indices harvest ]
> with map ;
> IN: scratchpad 8 partitions .
> {
> { 8 }
> { 7 1 }
> { 6 1 1 }
> { 5 1 1 1 }
> { 4 1 1 1 1 }
> { 3 1 1 1 1 1 }
> { 2 1 1 1 1 1 1 }
> { 1 1 1 1 1 1 1 1 }
> { 5 2 1 }
> { 4 2 1 1 }
> { 3 2 1 1 1 }
> { 2 2 1 1 1 1 }
> { 3 2 2 1 }
> { 2 2 2 1 1 }
> { 2 2 2 2 }
> { 4 2 2 }
> { 4 3 1 }
> { 3 3 1 1 }
> { 3 3 2 }
> { 4 4 }
> { 5 3 }
> { 6 2 }
> }
> IN: scratchpad { 1 2 3 4 5 6 7 8 } split-partitions .
> {
> { { 1 2 3 4 5 6 7 8 } }
> { { 1 2 3 4 5 6 7 } { 8 } }
> { { 1 2 3 4 5 6 } { 7 } { 8 } }
> { { 1 2 3 4 5 } { 6 } { 7 } { 8 } }
> { { 1 2 3 4 } { 5 } { 6 } { 7 } { 8 } }
> { { 1 2 3 } { 4 } { 5 } { 6 } { 7 } { 8 } }
> { { 1 2 } { 3 } { 4 } { 5 } { 6 } { 7 } { 8 } }
> { { 1 } { 2 } { 3 } { 4 } { 5 } { 6 } { 7 } { 8 } }
> { { 1 2 3 4 5 } { 6 7 } { 8 } }
> { { 1 2 3 4 } { 5 6 } { 7 } { 8 } }
> { { 1 2 3 } { 4 5 } { 6 } { 7 } { 8 } }
> { { 1 2 } { 3 4 } { 5 } { 6 } { 7 } { 8 } }
> { { 1 2 3 } { 4 5 } { 6 7 } { 8 } }
> { { 1 2 } { 3 4 } { 5 6 } { 7 } { 8 } }
> { { 1 2 } { 3 4 } { 5 6 } { 7 8 } }
> { { 1 2 3 4 } { 5 6 } { 7 8 } }
> { { 1 2 3 4 } { 5 6 7 } { 8 } }
> { { 1 2 3 } { 4 5 6 } { 7 } { 8 } }
> { { 1 2 3 } { 4 5 6 } { 7 8 } }
> { { 1 2 3 4 } { 5 6 7 8 } }
> { { 1 2 3 4 5 } { 6 7 8 } }
> { { 1 2 3 4 5 6 } { 7 8 } }
> }
The code is as ugly as can be and I would love to hear your suggestion on
how to improve it ( both from an idiomatic point of view and from a more
general one [ for example, I'm really disregarding performance in this
first implementation ] ).
On a side note, your blog post was really interesting and, at the same
time, inspiring.
Your last implementation is of an absolute elegance to my untrained eyes.
As a last note, please allow me to thank you for your time up till now.
I hope that I'm not abusing your kindness with this last message.
Il giorno dom 26 apr 2020 alle ore 04:04 John Benediktsson <mrj...@gmail.com>
ha scritto:
> In your example, the inputs are an ordered set and null sets aren’t
> allowed?
>
> I think would have expected to see an unordered result:
>
> { p } { q r } { s }
> { p } { q s } { r }
> { p q } { r } { s }
> { p r } { q } { s }
> { p s } { q } { r }
> { p } { q } { r s
>
> If it’s an ordered set, then this would be the result?
>
> { p } { q r } { s }
> { p q } { r } { s }
> { p } { q } { r s }
>
> I don’t think we have a word exactly like either, but it wouldn’t be that
> much to add it. We can help you code it, and take pull requests, or
> implement it given a good idea of the spec you are looking for.
>
> Your link reminds me of this blog post I wrote awhile ago. Maybe it helps.
>
> http://re-factor.blogspot.com/2010/05/evenly-partition-integer.html
> <http://re-factor.blogspot.com/2010/05/evenly-partition-integer.html?m=1>
>
> Best,
> John.
>
> On Apr 25, 2020, at 7:45 PM, Luca Di Sera <bloodtype.si...@gmail.com>
> wrote:
>
>
> I don't think they are the same thing.
>
> I apologize as I seem to have forgotten to provide a correct explanation
> of what I'm looking for.
>
> By a partition of a set S I mean a collection of non-empty subsets of S
> that are disjoint and which union is S.
>
> e.g { { p q r } { s } } is a partition of { p q r s }.
>
> A k-partition is a partition formed by exactly k subsets.
> Thus { { p q } { r } { s } }, { { p } { q r } { s } } and { { p } { q r }
> { s } } are the 3-partitions of { p q r s }.
>
> ( For integer Partitions of a positive integer n, instead, we mean a
> multiset of positive integers which sum is n it seems from what I learned
> today ).
>
> Permutations and Partitions should be different mathematical objects for
> the small amount of knowledge I have.
>
> Now, I have no idea if partitions can be generated from permutations or if
> I'm missing something ( that is maybe obvious )(my knowledge is really
> limited on combinatorics and other parts of mathematics for now ), so I
> apologize if that is the case.
>
>
> Il dom 26 apr 2020, 03:15 John Benediktsson <mrj...@gmail.com> ha scritto:
>
>> Is “K partitions” the same as “K permutations”?
>>
>>
>> https://docs.factorcode.org/content/word-__lt__k-permutations__gt__,math.combinatorics.html
>>
>>
>>
>> On Apr 25, 2020, at 6:46 PM, Luca Di Sera <bloodtype.si...@gmail.com>
>> wrote:
>>
>>
>> I was studying Unger's Parsers and was in need of a way to generate the
>> k-partitions of the input string.
>>
>> I wasn't able to find it neither in math.combinatorics,splitting,
>> grouping or by a general search.
>> I'm currently working on implementing one myself from the integer
>> partitioning in this paper (
>> http://www.nakano-lab.cs.gunma-u.ac.jp/Papers/e90-a_5_888.pdf ) but
>> would gladly use something that is already present in factor.
>>
>> So, is there any word ( or simple combination of words ) that I'm somehow
>> missing that will let me build the k-partitions of a sequence/string?
>> _______________________________________________
>> Factor-talk mailing list
>> Factor-talk@lists.sourceforge.net
>> https://lists.sourceforge.net/lists/listinfo/factor-talk
>>
>> _______________________________________________
>> Factor-talk mailing list
>> Factor-talk@lists.sourceforge.net
>> https://lists.sourceforge.net/lists/listinfo/factor-talk
>>
> _______________________________________________
> Factor-talk mailing list
> Factor-talk@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/factor-talk
>
> _______________________________________________
> Factor-talk mailing list
> Factor-talk@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/factor-talk
>
_______________________________________________
Factor-talk mailing list
Factor-talk@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/factor-talk
