I'm sorry, it seems my message from yesterday was blocked as it was too
long.
To make a summary, I got the same impression as what is being said in Mr.
llin post.
If we are able to produce the k-partitions of n we can find the
k-compositions by finding their (unique)-permutations ( If we'd find all
permutations we'd have some double results. For example { 2 1 1 } has two {
1 2 1 } permutations that are the same composition )
and from the composition we can partition a sequence.
Since factor already provides code for both splitting a sequence and
finding the permutations of a sequence we only need to generate the
k-partitions.
I further noted that it may makes sense to build a work for the
<=k-partitions, instead of the =k-partitions, as from that we can easily
build both all-partitions and the =k-partitions.
Furthermore, I showed some (badly-implemented, ugly and unsafe [ and that
doesn't cover some edge cases ] ) test-code that I had yesterday morning
that explores this concept with the algorithms derived in the paper I
linked.
<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 ;
>
:: <=k-children ( partition k -- )
> partition ,
> partition has-an-expanding-child? [
> partition length k < [ partition expanding-child k <=k-children ]
> when
> partition has-a-preserving-child? [ partition preserving-child k
> <=k-children ] when
> ] when ;
>
: root-child ( n -- partition )
> 1 - 1 2array ;
>
: <=k>=k ( partition delta -- partition )
> [ [ [ 1 + ] map ] [ length ] bi ] dip swap - 1 <repetition> append ;
>
PRIVATE>
>
> : <=k-partitions ( n k -- partitions )
> [ drop 1array 1array ] [
> [ [ 1 > ] bi@ and ]
> [ [ root-child ] dip [ <=k-children ] { } make append ]
> smart-when*
> ] 2bi ;
>
: partitions ( n -- partitions )
> dup <=k-partitions ;
>
: =k-partitions ( n k -- partitions )
> [ = ] [ drop [ 1 ] replicate 1array ] [
> [ [ - ] keep <=k-partitions ] [ nip [ <=k>=k ] curry map ] 2bi
> ] smart-if ;
>
: compositions ( partitions -- compositions )
> [ all-permutations members ] [ append ] map-reduce ;
>
! This was modified to follow Mr.llin snippet
: split-compositions ( seq compositions -- seq )
> [ cum-sum split-indices but-last ] with map ;
IN: scratchpad "pqrs" 4 2 =k-partitions compositions split-compositions .
> { { "pqr" "s" } { "p" "qrs" } { "pq" "rs" } }
> IN: scratchpad "(i+i)xi" dup length 3 =k-partitions compositions
> split-compositions .
> {
> { "(i+i)" "x" "i" }
> { "(" "i+i)x" "i" }
> { "(" "i" "+i)xi" }
> { "(i+i" ")x" "i" }
> { "(i+i" ")" "xi" }
> { "(i" "+i)x" "i" }
> { "(i" "+" "i)xi" }
> { "(" "i+i)" "xi" }
> { "(" "i+" "i)xi" }
> { "(i+" "i)" "xi" }
> { "(i" "+i)" "xi" }
> { "(i" "+i" ")xi" }
> { "(i+" "i)x" "i" }
> { "(i+" "i" ")xi" }
> { "(" "i+i" ")xi" }
> }
In the end, I brought to attention that what ( and by what I simply mean
the result above; not the implementation, the architecture or anything else
) is shown above is what I'm exactly aiming for and need for Unger's
parsers, so that is should be clearer what is the objective.
_______________________________________________
Factor-talk mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/factor-talk
