Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!newsfeed.fsmpi.rwth-aachen.de!proxad.net!feeder1-2.proxad.net!news.tele.dk!news.tele.dk!small.news.tele.dk!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.019 X-Spam-Evidence: '*H*': 0.96; '*S*': 0.00; '22,': 0.09; 'dan': 0.09; 'exist,': 0.09; 'interpreted': 0.09; 'mind,': 0.09; 'sentence': 0.09; 'cc:addr:python-list': 0.11; 'already,': 0.16; 'cc:name:python list': 0.16; 'corrects': 0.16; 'for,': 0.16; 'generators.': 0.16; 'lengths': 0.16; 'merely': 0.16; 'remainder': 0.16; 'separated': 0.16; 'subject:combinations': 0.16; 'subject:generator': 0.16; 'those,': 0.16; 'wrote:': 0.18; 'wed,': 0.18; 'all,': 0.19; 'thu,': 0.19; 'input': 0.22; 'email addr:gmail.com>': 0.22; 'cc:addr:python.org': 0.22; 'filtering': 0.24; 'space.': 0.24; 'cc:2**0': 0.24; '>': 0.26; 'header:In-Reply-To:1': 0.27; 'correct': 0.29; 'words': 0.29; 'message-id:@mail.gmail.com': 0.30; "i'm": 0.30; 'reply.': 0.31; 'away.': 0.31; 'correctly.': 0.31; 'faster,': 0.31; 'lot.': 0.31; 'probably': 0.32; 'says': 0.33; 'checking': 0.33; 'fri,': 0.33; 'received:google.com': 0.35; 'opposed': 0.36; 'thanks': 0.36; 'subject:?': 0.36; 'should': 0.36; 'nov': 0.38; 'pm,': 0.38; 'rather': 0.38; 'short': 0.38; 'even': 0.60; 'john': 0.61; 'back': 0.62; "you'll": 0.62; "you've": 0.63; 'story': 0.63; 'decided': 0.64; 'interest': 0.64; 'more': 0.64; 'fire': 0.65; 'here': 0.66; '20,': 0.68; 'combining': 0.68; 'subject': 0.69; 'results': 0.69; 'containing': 0.69; 'dense': 0.84; 'recursive.': 0.84; 'story:': 0.84; '2013': 0.98 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=sEzZbe0ebnnq8BRHogGMcDktV5DU3EAFguPffOJSmlI=; b=kq9Yk+zjCIa9igBIPIgLHwletWPmruGRWysQHHtcYHmPdOaKJYqLKX2yy3lYlNXnxK 8xy1GWaSxlUQIfeA1rd561sRHp5tl+AHjcP+aXALHJ7yPhIokwaOeuGCZBN/NdwiYGbT Xhmfoils7qRvpaE7dsCZztq7ngXo8zVRq5/5iSn3vyUri67QmDeqYgTYlAiN9WPZ0gq2 9VxxfB6WMmQai6VtfR5Pq3pGNRU8ZxZp4AWEt084GOh1n/MyzdCg1Gga13SIPerGaq36 0KqWZkiy+I/YcDmYSwso1iw6X0uV5GpsMMDLhiYDY5H4FGyiFTjII3W2UcZ86A4qPtWA P/LQ== MIME-Version: 1.0 X-Received: by 10.194.219.1 with SMTP id pk1mr13341278wjc.36.1385188409992; Fri, 22 Nov 2013 22:33:29 -0800 (PST) In-Reply-To: <20131123115838.4016c671@mini.home> References: <20131121174614.53450d51@mini.home> <20131123115838.4016c671@mini.home> Date: Fri, 22 Nov 2013 22:33:29 -0800 Subject: Re: Recursive generator for combinations of a multiset? From: Dan Stromberg To: "John O'Hagan" Content-Type: multipart/alternative; boundary=001a11c1a2f01feb7d04ebd24fe0 Cc: Python List X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 96 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1385188417 news.xs4all.nl 16010 [2001:888:2000:d::a6]:57898 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:60276 --001a11c1a2f01feb7d04ebd24fe0 Content-Type: text/plain; charset=ISO-8859-1 On Fri, Nov 22, 2013 at 4:58 PM, John O'Hagan wrote: > On Thu, 21 Nov 2013 12:59:26 -0800 > Dan Stromberg wrote: > > > On Wed, Nov 20, 2013 at 10:46 PM, John O'Hagan > > 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. --001a11c1a2f01feb7d04ebd24fe0 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable

= On Fri, Nov 22, 2013 at 4:58 PM, John O'Hagan <research@johnohag= an.com> wrote:
On T= hu, 21 Nov 2013 12:59:26 -0800
Dan Stromberg <drsalists@gmail.co= m> 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<= br> > > 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 space= s),
> 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 su= ggesting
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.<= br>
However, I was thinking about this in the back of my mind, and decid= ed 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) ov= er the correct (possible) alphabet, and permute Those, afterward checking i= f they form good anagrams of the original sentence.=A0 This would probably = be much faster, since English isn't that dense of a space.

--001a11c1a2f01feb7d04ebd24fe0--