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: 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 To: "John O'Hagan" Content-Type: multipart/alternative; boundary=001a11c3556e0180f804ecd5c005 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: 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 --001a11c3556e0180f804ecd5c005 Content-Type: text/plain; charset=ISO-8859-1 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. > > 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. --001a11c3556e0180f804ecd5c005 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable

= On Wed, Nov 20, 2013 at 10:46 PM, John O'Hagan <research@johnoha= gan.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<= br> think it needs to be recursive. It may even be of more general
interest in terms of filtering the results of generators.
<= div>=A0
Any suggestions?
=
I've updated my code at=A0 http://stromberg.dnsalias.org/svn/anagr= ams/trunk/ ; It's multiword now.=A0 It can blast through the word &= quot;punishment" in 4 seconds, but for "The public art galleries&= quot; 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.=A0 Parallelizatio= n might help, but it'd probably take a lot of RAM that way.=A0 Maybe th= e RAM use would be better with CPython, but it's much faster with Pypy;= I did most of my testing with Pypy 2.2.

--001a11c3556e0180f804ecd5c005--