Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!news.tele.dk!feed118.news.tele.dk!news.tele.dk!small.news.tele.dk!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Sender: "John O'Hagan" <johnmohagan@gmail.com>
Date: Sat, 23 Nov 2013 12:07:32 +1100
From: John O'Hagan <research@johnohagan.com>
To: python-list@python.org
Subject: Re: Recursive generator for combinations of a multiset?
In-Reply-To: <9b7100f3-0d99-4eac-8be2-7f4403da341f@googlegroups.com>
References: <20131121174614.53450d51@mini.home> <CAHVvXxQ0Kdd91nCmmz6fw0fMiA=1nrPT=DLZAxhrFNhsuS89DA@mail.gmail.com> <mailman.3008.1385038886.18130.python-list@python.org> <9b7100f3-0d99-4eac-8be2-7f4403da341f@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.3062.1385168868.18130.python-list@python.org>
Lines: 158
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:60258

On Thu, 21 Nov 2013 18:14:41 -0800 (PST)
James <hslee911@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