On Thu, 21 Nov 2013 18:14:41 -0800 (PST) James <hslee...@yahoo.com> wrote:
> On Thursday, November 21, 2013 5:01:15 AM UTC-8, John O'Hagan wrote: [...] > > > On 21 November 2013 06:46, John O'Hagan > > > > > wrote: > > [...] > > > > > > def multicombs(it, r): > > > > > > result = it[:r] > > > > > > yield result > > > > > > while 1: > > > > > > for i in range(-1, -r - 1, -1): > > > > > > rep = result[i] > > > > > > if rep < it[i]: > > > > > > break > > > > > > else: > > > > > > break > > > > > > for j, n in enumerate(it): > > > > > > if n > rep: > > > > > > break > > > > > > result = result[:i] + it[j:j - i] > > > > > > yield result > > > > > [...] > > > > I neglected to mention that multicombs takes a sorted iterable; > > > > it doesn't work right otherwise. I'd forgotten that because my > > > > wordlists are guaranteed sorted by the way they're built. Sorry > > about > > > > that. > > > > > > > > In my use-case the first argument to multicombs is a tuple of words > > > > which may contain duplicates, and it produces all unique > > combinations > > > > of a certain length of those words, eg: > > > > > > > > list(multicombs(('cat', 'hat', 'in', 'the', 'the'), 3)) > > > > > > > > [('cat', 'hat', 'in'), ('cat', 'hat', 'the'), ('cat', 'in', 'the'), > > > > ('cat', 'the', 'the'), ('hat', 'in', 'the'), ('hat', 'the', 'the'), > > > > ('in', 'the', 'the')] > > > > [...] > > What I'm looking for is a recursive algorithm which does what > > > > multicombs does (order unimportant) so that I can apply a pruning > > > > shortcut like the one I used in the recursive cartesian product > > > > algorithm in my original post. > > > > > > > > Multiset combination algorithms seem pretty thin on the ground out > > > > there - as I said, I could only find a description of the procedure > > > > above, no actual code. The ones I did find are non-recursive. I'm > > > > hoping some combinatorics and/or recursion experts can offer > > advice. > > > > [...] > > > > John > > Could convert the following perl script to python? > > use Data::Dump qw(dump); > dump combo([@ARGV], 3); > > sub combo { > my ($t, $k) = @_; > my @T = @$t; > my @R = (); > my %g = (); > if ($k == 1) { > for (@T) { > push @R, $_ unless $g{$_}++; > } > } else { > while (my $x = shift @T) { > $p = combo([@T], $k-1); > for (@{$p}) { > my $q = $x.",".$_; > push @R, $q unless $g{$q}++; > } > } > } > [@R]; > } > > $ prog.pl cat hat in the the > [ > "cat,hat,in", > "cat,hat,the", > "cat,in,the", > "cat,the,the", > "hat,in,the", > "hat,the,the", > "in,the,the", > ] > > James Thanks. Now I just have to learn Perl to understand what that does! :) Regards, -- John -- https://mail.python.org/mailman/listinfo/python-list