Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder1.news.weretis.net!feeder.erje.net!eu.feeder.erje.net!xlned.com!feeder1.xlned.com!newsfeed.xs4all.nl!newsfeed3.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Sender: "John O'Hagan" <johnmohagan@gmail.com>
Date: Sun, 24 Nov 2013 13:57:34 +1100
From: John O'Hagan <research@johnohagan.com>
To: Python List <python-list@python.org>
Subject: Re: Recursive generator for combinations of a multiset?
In-Reply-To: <CAGGBd_pyBLX_FFT=1KCDXBCNUSLsfB3OAKR_VwNfzKkGubcuhQ@mail.gmail.com>
References: <20131121174614.53450d51@mini.home> <CAGGBd_oz8B8bU5SfTdbq7kAU0yM05WktHQ4GGwJrwNBQDZMi_A@mail.gmail.com> <20131123115838.4016c671@mini.home> <CAGGBd_pyBLX_FFT=1KCDXBCNUSLsfB3OAKR_VwNfzKkGubcuhQ@mail.gmail.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.3113.1385261877.18130.python-list@python.org>
Lines: 65
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:60347

On Fri, 22 Nov 2013 22:33:29 -0800
Dan Stromberg <drsalists@gmail.com> wrote:

> On Fri, Nov 22, 2013 at 4:58 PM, John O'Hagan
> <research@johnohagan.com>wrote:
> 
> > On Thu, 21 Nov 2013 12:59:26 -0800
> > Dan Stromberg <drsalists@gmail.com> wrote:
> >
> > > On Wed, Nov 20, 2013 at 10:46 PM, John O'Hagan
> > > <research@johnohagan.com>wrote:
> > >
> > > >
> > > > Short story: the subject says it all, so if you have an answer
> > > > already, fire away. Below is the long story of what I'm using it
> > > > for, and why I think it needs to be recursive. It may even be of
> > > > more general interest in terms of filtering the results of
> > > > generators.
> > > >
> > >
> > > I think you probably need permutations rather than combinations.
> > >
> > > Also, I think you'll need to form a word (partitioned off by
> > > spaces), and then check it against a set
> > > containing /usr/share/dict/words before recursing for the
> > > remainder of the sentence - this should speed things up a LOT.
> >
> > Thanks for the reply. If I understand you correctly, you are
> > suggesting permuting the input _characters_ to form words and then
> > seeing if they exist, as opposed to my approach of combining known
> > words and seeing if they are anagrams. (Permutations of words would
> > not help find anagrams as they merely change the word order). Here
> > is an attempt at that:
> 
> 
> You've interpreted me correctly.
> 
> However, I was thinking about this in the back of my mind, and
> decided it would probably be best to inhale /usr/share/dict/words (if
> on Linux), and pull out words of the corrects lengths (as separated
> by the blanks) over the correct (possible) alphabet, and permute
> Those, afterward checking if they form good anagrams of the original
> sentence.  This would probably be much faster, since English isn't
> that dense of a space.

If you look back at my original question, you'll see that's pretty much
what I've done. I didn't spell out all the details, but  I made a
dictionary of wordlength keys containing lists of all dictionary words
of that length made of the correct sub-alphabet.

But to to recap the problem: to produce non-redundant anagram phrases, I
need the cartesian product (not permutations) of these lists if each is
unique, but with a subroutine producing multiset combinations if a list
is repeated, i.e., if a particular length is called for more than once.
The version I have so far is correct but substantially slower than the
product-only one, which just goes ahead and produces all the redundant
results. This seems counter-intuitive, and my theory is that this is
because I am unable to "prune" the non-recursive combination algorithm
I currently have.

Regards,

--

John