Some thoughts out loud.
So, basically we need to take the length of the input sequence N, and split it into k numbers >= 1, so that the sum total of them will be = N.
Let's say N = 10, k = 3. What kind of outputs can we get?
Start with major number M = N - k + 1 = 8. Here the list of combinations will be the shortest, with only k combinations:
{ 8 1 1 }
{ 1 8 1 }
{ 1 1 8 }
Next major number is M = N - k = 7:
{ 7 2 1 }
{ 7 1 2 }
{ 1 7 2 }
{ 2 7 1 }
{ 1 2 7 }
{ 2 1 7 }
Next major is M = N - k - 1 = 6:
{ 6 3 1 }
{ 6 1 3 }
{ 3 6 1 }
{ 3 6 1 }
{ 1 6 3 }
{ 3 1 6 }
{ 3 1 6 }
{ 1 3 6 }
{ 6 2 2 }
{ 2 6 2 }Then M = 5:
{ 5 4 1 }...
{ 5 3 2 }...
...
When we get below N div 2, the combinations will repeat earlier ones.
If we look at the case with major number 6, we can see that we need to compute all permutations of { 6 3 1 } and { 6 2 2 }. The code for this exists in Factor library.
How does on get the numbers to combine with the major number M? Those are the (k - 1) numbers with sum total = N - M. A simple recursive formula can return all such numbers.
When we have the array of lengths, such as { 6 3 1 }, we can apply it to the original sequence with `cum-sum split-indices but-last`:
"1234567890" { 6 3 1 } cum-sum split-indices but-last
{ "123456" "789" "0" }
26.04.2020, 07:03, "Luca Di Sera" <bloodtype.si...@gmail.com>:
,,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 sIf 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.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”?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
---=====---
Александр
_______________________________________________ Factor-talk mailing list Factor-talk@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/factor-talk
