Re: Recursive generator for combinations of a multiset?

Path	csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!goblin2!goblin.stu.neva.ru!newsfeed.xs4all.nl!newsfeed3.news.xs4all.nl!xs4all!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	<drsalists@gmail.com>
X-Original-To	python-list@python.org
Delivered-To	python-list@mail.python.org
X-Spam-Status	OK 0.142
X-Spam-Level	*
X-Spam-Evidence	'H': 0.72; 'S': 0.01; '"the': 0.07; 'pypy': 0.07; 'cc:addr:python-list': 0.11; 'already,': 0.16; 'cc:name:python list': 0.16; 'exponential': 0.16; 'for,': 0.16; 'generators.': 0.16; 'seconds,': 0.16; 'subject:combinations': 0.16; 'subject:generator': 0.16; 'url:svn': 0.16; 'wrote:': 0.18; 'wed,': 0.18; 'all,': 0.19; 'cc:addr:python.org': 0.22; 'filtering': 0.24; 'cc:2**0': 0.24; "i've": 0.25; 'header:In- Reply-To:1': 0.27; 'testing': 0.29; 'message-id:@mail.gmail.com': 0.30; "i'm": 0.30; 'code': 0.31; 'away.': 0.31; 'probably': 0.32; 'says': 0.33; 'updated': 0.34; '"the': 0.34; 'maybe': 0.34; 'problem.': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'ram': 0.36; 'subject:?': 0.36; 'url:org': 0.36; 'nov': 0.38; 'pm,': 0.38; 'short': 0.38; 'skip:& 20': 0.39; 'help,': 0.39; 'even': 0.60; 'most': 0.60; 'john': 0.61; 'story': 0.63; 'interest': 0.64; 'more': 0.64; 'fire': 0.65; 'believe': 0.68; '20,': 0.68; 'subject': 0.69; 'results': 0.69; 'day': 0.76; '2.2.': 0.84; 'ate': 0.84; 'blast': 0.84; "it'd": 0.84; 'recursive.': 0.84; 'story:': 0.84; 'killed': 0.91; '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=uBySMJMJvLkwX8Mtpfev5ZECUjyYOZ1a7Q9854sG6+s=; b=K98HzZ8mT4aZHBsULP9a0Biu+omqPzSfAgozIlDfy3hx0VfWzcCcP7/igcAxF+xSLY 2nlgayZQ6pUybXbqBtRLzj5wm5kzNqTjkkzSEOJnl486GjybuY4IgB9Yha2HGyWHdLtA vmswO7P19o9kUGeQdFIr7DX0NHonHXmaEn5ksA1qTKLnQun2WWfeVa2kVn4McJU7VYfa a0M5pHUuYz3gJmkOzzpXGGYqdHqX/ELbQ34yxptahO8I/2t5r30vCeRdxOyD0g2UFms9 eLq+kTITjb23v/4V9gqE3AMbGC9JYLwV8QvkX8gG72PwE3tiVe7LPnTgh5LxDkTK9BVG WvuQ==
MIME-Version	1.0
X-Received	by 10.180.183.72 with SMTP id ek8mr435793wic.31.1386302700354; Thu, 05 Dec 2013 20:05:00 -0800 (PST)
In-Reply-To	<20131121174614.53450d51@mini.home>
References	<20131121174614.53450d51@mini.home>
Date	Thu, 5 Dec 2013 20:05:00 -0800
Subject	Re: Recursive generator for combinations of a multiset?
From	Dan Stromberg <drsalists@gmail.com>
To	"John O'Hagan" <research@johnohagan.com>
Content-Type	multipart/alternative; boundary=001a11c3556e0180f804ecd5c005
Cc	Python List <python-list@python.org>
X-BeenThere	python-list@python.org
X-Mailman-Version	2.1.15
Precedence	list
List-Id	General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe	<https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive	<http://mail.python.org/pipermail/python-list/>
List-Post	<mailto:python-list@python.org>
List-Help	<mailto:python-list-request@python.org?subject=help>
List-Subscribe	<https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups	comp.lang.python
Message-ID	<mailman.3621.1386302707.18130.python-list@python.org> (permalink)
Lines	57
NNTP-Posting-Host	2001:888:2000:d::a6
X-Trace	1386302707 news.xs4all.nl 2872 [2001:888:2000:d::a6]:51153
X-Complaints-To	abuse@xs4all.nl
Xref	csiph.com comp.lang.python:61111

Show key headers only | View raw

[Multipart message — attachments visible in raw view] - view raw

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.
>

> Any suggestions?
>
I've updated my code at
http://stromberg.dnsalias.org/svn/anagrams/trunk/; It's multiword now.
 It can blast through the word "punishment" in 4
seconds, but for "The public art galleries" it ate about 7 gigabytes of RAM
and ran for more than a day before I killed it.

I believe it's an exponential problem.  Parallelization might help, but
it'd probably take a lot of RAM that way.  Maybe the RAM use would be
better with CPython, but it's much faster with Pypy; I did most of my
testing with Pypy 2.2.

Back to comp.lang.python | Previous | Next | Find similar | Unroll thread

Thread

Re: Recursive generator for combinations of a multiset? Dan Stromberg <drsalists@gmail.com> - 2013-12-05 20:05 -0800

csiph-web