in reply to (Golf as well): List of Partitions
Rule #7 for sociopathic obsessive compulsives is "If you can't win, change the rules".
So here is a context-free iterator that produces all unique partitionings along with a golfed version of it:
The advantage of a "context-free iterator" is that you can compute all possible partitions for really large numbers without running out of memory. They also tend to be pretty fast.#!/usr/bin/perl -w use strict; sub ipart { my( @a, $n )= @_; while( $n++, 0 == --$a[$#a] ){ $n += pop @a; return if ! @a; } do { push @a, @a && $a[$#a] < $n ? $a[$#a] : $n; $n -= $a[$#a]; } while( 0 < $n ); return @a; } sub ip { my(@a,$n)=@_;$n+=shift@a while$n++,@a&&!--$a[0]; {@a||last;@a=($a[0]<$n?$a[0]:$n,@a);($n-=$a[0])&&redo}@a } for( @ARGV ) { print "$_:\n"; my @p= $_; do { print " [",join(",",@p),"]\n"; } while( @p= ipart( @p ) ); print "$_:\n"; @p= $_; do { print " [",join(",",@p),"]\n"; } while( @p= ip( @p ) ); }
An iterator returns partitionings one at a time. "Context-free" means that all you have to pass subsequent calls to the iterator is the previously returned iterator.
Normally the first call to the iterator is a special case that initializes it and returns the first solution. In this case I cheat a little since ipart($n) looks like an initialization but can also be considered as passing in the first solution, I just start by returning the second solution.
Anyway, feel free to golf that down from the 104-character version I came up with (since the newline is not required).
- tye (but my friends call me "Tye")
|
---|