Permutations and Combinations in SequenceableCollection
Locked
12
12
Permutations and Combinations in SequenceableCollection
 
|
Hi,
I'm trying to generate the permutations of a sequence of numbers. I've found # permutationsDo: aBlock, but this generated the permutation of the entire sequence. I want to do it in groups of 2. The #combinations: anInteger atATimeDo: aBlock method does what I need for combinations, but I cannot find the equivalent for permutations. Does something like this exist in the standard library, or in an external package.
-- -JT _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Permutations and Combinations in SequenceableCollection
|
|
On Jan 5, 2010, at 5:19 32PM, John Toohey wrote:
> Hi, > I'm trying to generate the permutations of a sequence of numbers. I've found # permutationsDo: aBlock, but this generated the permutation of the entire sequence. I want to do it in groups of 2. The #combinations: anInteger atATimeDo: aBlock method does what I need for combinations, but I cannot find the equivalent for permutations. Does something like this exist in the standard library, or in an external package. > > -- > -JT How about: #(1 2 3 4) combinations: 2 atATimeDo: [:array | array permutationsDo: [:each | Transcript show: each printString; cr]] ? Cheers, Henry _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Permutations and Combinations in SequenceableCollection
|
|
But this doesn't get 1-1, 2-2 or 3-3. I had tried something like that use #reverse on each combination, but #combinations does not generate -duplicates- from the number sequences.
On Tue, Jan 5, 2010 at 12:16, Henrik Johansen <[hidden email]> wrote:
-- -JT _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
|
|
Can you give an example (on #(1 2 3 4) for instance) ?
Thx
2010/1/5 John Toohey <[hidden email]> But this doesn't get 1-1, 2-2 or 3-3. I had tried something like that use #reverse on each combination, but #combinations does not generate -duplicates- from the number sequences. -- Cédrick _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Permutations and Combinations in SequenceableCollection
|
|
In reply to this post by John Toohey
On Tue, 5 Jan 2010, John Toohey wrote:
> But this doesn't get 1-1, 2-2 or 3-3. I had tried something like that use > #reverse on each combination, but #combinations does not generate > -duplicates- from the number sequences. I guess you are looking for this: allPairsFromCollectionDo := [ :collection :block | | o | o := OrderedCollection newFrom: collection. o size timesRepeat: [ o with: collection do: block. o add: o removeFirst ] ]. Transcript open. allPairsFromCollectionDo value: #(1 2 3 4) value: [ :a :b | Transcript print: { a. b }; cr ]. Transcript flush Levente > > On Tue, Jan 5, 2010 at 12:16, Henrik Johansen > <[hidden email]>wrote: > >> On Jan 5, 2010, at 5:19 32PM, John Toohey wrote: >> >>> Hi, >>> I'm trying to generate the permutations of a sequence of numbers. I've >> found # permutationsDo: aBlock, but this generated the permutation of the >> entire sequence. I want to do it in groups of 2. The #combinations: >> anInteger atATimeDo: aBlock method does what I need for combinations, but I >> cannot find the equivalent for permutations. Does something like this exist >> in the standard library, or in an external package. >>> >>> -- >>> -JT >> >> How about: >> #(1 2 3 4) combinations: 2 atATimeDo: [:array | array permutationsDo: >> [:each | Transcript show: each printString; cr]] ? >> >> Cheers, >> Henry >> >> >> _______________________________________________ >> Pharo-project mailing list >> [hidden email] >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> > > > > -- > -JT > _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Permutations and Combinations in SequenceableCollection
|
|
Very nice, thank you.
On Tue, Jan 5, 2010 at 17:21, Levente Uzonyi <[hidden email]> wrote:
-- -JT _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Permutations and Combinations in SequenceableCollection
|
|
In reply to this post by Levente Uzonyi-2
>>>>> "Levente" == Levente Uzonyi <[hidden email]> writes:
Levente> On Tue, 5 Jan 2010, John Toohey wrote: >> But this doesn't get 1-1, 2-2 or 3-3. I had tried something like that use >> #reverse on each combination, but #combinations does not generate >> -duplicates- from the number sequences. Levente> I guess you are looking for this: Levente> allPairsFromCollectionDo := [ :collection :block | Levente> | o | Levente> o := OrderedCollection newFrom: collection. Levente> o size timesRepeat: [ Levente> o with: collection do: block. Levente> o add: o removeFirst ] ]. Or more simply: aCollection do: [:x | aCollection do: [:y | "use x and y"]]. Unless I'm misunderstanding the problem. Which is neither combinations nor permutations, but so far is the only thing that fits all the bizarre conditions. -- Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095 <[hidden email]> <URL:http://www.stonehenge.com/merlyn/> Smalltalk/Perl/Unix consulting, Technical writing, Comedy, etc. etc. See http://methodsandmessages.vox.com/ for Smalltalk and Seaside discussion _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Permutations and Combinations in SequenceableCollection
|
|
What I needed to do was from a sequence of say, 0 to: 4, produce #(0 0)#(1 1)#(2 2)#(3 3)#(4 4)#(1 0)#(2 1)#(3 2)#(4 3)#(0 4)#(2 0)#(3 1)#(4 2)#(0 3)#(1 4)#(3 0)#(4 1)#(0 2)#(1 3)#(2 4)#(4 0)#(0 1)#(1 2)#(2 3)#(3 4). Basically, I wanted to generate all possible scores for a soccer match, hence the 1-1, 0-0, etc.
On Tue, Jan 5, 2010 at 19:58, Randal L. Schwartz <[hidden email]> wrote: >>>>> "Levente" == Levente Uzonyi <[hidden email]> writes: -- -JT _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Permutations and Combinations in SequenceableCollection
|
|
In reply to this post by Randal L. Schwartz
On Tue, 5 Jan 2010, Randal L. Schwartz wrote:
>>>>>> "Levente" == Levente Uzonyi <[hidden email]> writes: > > Levente> On Tue, 5 Jan 2010, John Toohey wrote: >>> But this doesn't get 1-1, 2-2 or 3-3. I had tried something like that use >>> #reverse on each combination, but #combinations does not generate >>> -duplicates- from the number sequences. > > Levente> I guess you are looking for this: > Levente> allPairsFromCollectionDo := [ :collection :block | > Levente> | o | > Levente> o := OrderedCollection newFrom: collection. > Levente> o size timesRepeat: [ > Levente> o with: collection do: block. > Levente> o add: o removeFirst ] ]. > > Or more simply: > > aCollection do: [:x | aCollection do: [:y | "use x and y"]]. Nice, it's funny that I didn't find this simple solution. And it's O(n^2) instead of O(n^3) like mine (because OrderedCollection is implemented such a dumb way). Levente > > Unless I'm misunderstanding the problem. > > Which is neither combinations nor permutations, but so far is the only thing > that fits all the bizarre conditions. > > -- > Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095 > <[hidden email]> <URL:http://www.stonehenge.com/merlyn/> > Smalltalk/Perl/Unix consulting, Technical writing, Comedy, etc. etc. > See http://methodsandmessages.vox.com/ for Smalltalk and Seaside discussion > _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Permutations and Combinations in SequenceableCollection
|
|
In reply to this post by John Toohey
>>>>> "John" == John Toohey <[hidden email]> writes:
John> What I needed to do was from a sequence of say, 0 to: 4, produce #(0 0)#(1 John> 1)#(2 2)#(3 3)#(4 4)#(1 0)#(2 1)#(3 2)#(4 3)#(0 4)#(2 0)#(3 1)#(4 2)#(0 John> 3)#(1 4)#(3 0)#(4 1)#(0 2)#(1 3)#(2 4)#(4 0)#(0 1)#(1 2)#(2 3)#(3 John> 4). Basically, I wanted to generate all possible scores for a soccer match, John> hence the 1-1, 0-0, etc. That's what I did. You want X, Y for all possible values of X from 0 to 4 and Y from 0 to 4, right? That's *not* permutations. That's *not* combinations. That's "combinations with replacement/repetition". ... http://en.wikipedia.org/wiki/Combination I hate it when people use the words permutation or combination without realizing they have specific math meanings. But that's not your fault, but I hope you never do it again. :) -- Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095 <[hidden email]> <URL:http://www.stonehenge.com/merlyn/> Smalltalk/Perl/Unix consulting, Technical writing, Comedy, etc. etc. See http://methodsandmessages.vox.com/ for Smalltalk and Seaside discussion _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Permutations and Combinations in SequenceableCollection
|
|
In reply to this post by John Toohey
2010/1/5 John Toohey <[hidden email]> What I needed to do was from a sequence of say, 0 to: 4, produce #(0 0)#(1 1)#(2 2)#(3 3)#(4 4)#(1 0)#(2 1)#(3 2)#(4 3)#(0 4)#(2 0)#(3 1)#(4 2)#(0 3)#(1 4)#(3 0)#(4 1)#(0 2)#(1 3)#(2 4)#(4 0)#(0 1)#(1 2)#(2 3)#(3 4). Basically, I wanted to generate all possible scores for a soccer match, hence the 1-1, 0-0, etc. allPairsDo: aBinaryBlock self do: [:first| self do: [:second| aBinaryBlock value: first value: second]] right?
_______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Permutations and Combinations in SequenceableCollection
|
|
<blush>oops, just noticed Randal already provided this.</blush>
On Tue, Jan 5, 2010 at 5:47 PM, Eliot Miranda <[hidden email]> wrote:
_______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Permutations and Combinations in SequenceableCollection
|
|
In reply to this post by Randal L. Schwartz
Thank you, duly chastened. I did know the formulae for P and C, but didn't know how to add the repetitions. My original code was :-
|c| c := SortedCollection new.
c add: '0, 0'; add:'1, 1'; add: '2, 2'; add:'3, 3'; add: '4, 4'. (0 to: 4) combinations: 2 atATimeDo:[:each | c add: each asCommaString. c add:( each reverse) asCommaString].
^c Really glad that I asked the question. Thank you again.
On Tue, Jan 5, 2010 at 20:36, Randal L. Schwartz <[hidden email]> wrote: >>>>> "John" == John Toohey <[hidden email]> writes: -- -JT _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Permutations and Combinations in SequenceableCollection
|
|
In reply to this post by Eliot Miranda-2
>>>>> "Eliot" == Eliot Miranda <[hidden email]> writes:
Eliot> <blush>oops, just noticed Randal already provided this.</blush> "Like ships, passing in the night..." :-) -- Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095 <[hidden email]> <URL:http://www.stonehenge.com/merlyn/> Smalltalk/Perl/Unix consulting, Technical writing, Comedy, etc. etc. See http://methodsandmessages.vox.com/ for Smalltalk and Seaside discussion _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Permutations and Combinations in SequenceableCollection
|
|
In reply to this post by John Toohey
>>>>> "John" == John Toohey <[hidden email]> writes:
John> Thank you, duly chastened. I did know the formulae for P and C, but didn't John> know how to add the repetitions. My original code was :- John> |c| John> c := SortedCollection new. John> c add: '0, 0'; add:'1, 1'; add: '2, 2'; add:'3, 3'; add: '4, 4'. John> (0 to: 4) combinations: 2 atATimeDo:[:each | c add: each asCommaString. c John> add:( each reverse) asCommaString]. "Every time I cut with this wide saw, it removes 1/2 inch from the wood! I'll just glue it back after the cuts!" "why don't you just use the laser cutter? no losses!" :-) -- Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095 <[hidden email]> <URL:http://www.stonehenge.com/merlyn/> Smalltalk/Perl/Unix consulting, Technical writing, Comedy, etc. etc. See http://methodsandmessages.vox.com/ for Smalltalk and Seaside discussion _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Permutations and Combinations in SequenceableCollection
|
|
:-)
I don't suppose you have an equally elegant solution to the scores for a NFL game, where the units can be 1,2,3,6, assuming that each team could score a total of say, 35 points.
On Tue, Jan 5, 2010 at 21:26, Randal L. Schwartz <[hidden email]> wrote: John> Thank you, duly chastened. I did know the formulae for P and C, but didn't -- -JT _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Permutations and Combinations in SequenceableCollection
|
|
I guess its just something like this :-
|c| c := #(1 2 3 6 7 2 4 6 12 14 3 6 9 18 21 4 8 12 24 28 5 10 15 32 35). c do: [:x | c do: [:y | Transcript show: '('; show: x; show: '-'; show: y;show:')']].
On Tue, Jan 5, 2010 at 21:34, John Toohey <[hidden email]> wrote: :-) -- -JT _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Permutations and Combinations in SequenceableCollection
|
|
In reply to this post by John Toohey
2010/1/5 John Toohey <[hidden email]> :-) Since the increments include 1 this is equivalent to (0 to: max) allPairsDo: ... i.e. it is possible for a team to continue to score a single point, therefore the possible pairs of scores are all the pairs from 0 to N.
But isn't American Football more complex? an't you only score 1 after scoring a touchdown? What are the scoring rules? In any case your numbers are so small that you can use brute force and enumerate all possible combinations, filtering totals that exceed your limit.
_______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Permutations and Combinations in SequenceableCollection
|
|
Yep, the four scores would be 1 point conversion, 2 point conversion or a safety, 3 point field goal, and a 6 point touchdown. Although the 1 point can only come after a 6 point touchdown, so any score with just a 1 point would not be possible, but in theory, you could have 2-2, 4-4 etc.
2010/1/5 Eliot Miranda <[hidden email]>
-- -JT _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Permutations and Combinations in SequenceableCollection
|
|
2010/1/5 John Toohey <[hidden email]> Yep, the four scores would be 1 point conversion, 2 point conversion or a safety, 3 point field goal, and a 6 point touchdown. Although the 1 point can only come after a 6 point touchdown, so any score with just a 1 point would not be possible, but in theory, you could have 2-2, 4-4 etc. So that has to be #(0), (2 to: limit) allPairsDo: right? Since 2 is the lowest score, 3 the next, 4 = 2 + 2, 5 = 3 + 2, right?
_______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
«
Return to Pharo Smalltalk Developers
|
1 view|%1 views
| Free forum by Nabble | Edit this page |