Path: csiph.com!usenet.pasdenom.info!news.redatomik.org!newsfeed.xs4all.nl!newsfeed2a.news.xs4all.nl!xs4all!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.015 X-Spam-Evidence: '*H*': 0.97; '*S*': 0.00; 'algorithm': 0.04; 'returned.': 0.07; 'received:80.91': 0.09; 'received:80.91.229': 0.09; 'received:gmane.org': 0.09; 'received:list': 0.09; 'algorithm.': 0.16; 'extension.': 0.16; 'from:addr:behnel.de': 0.16; 'from:addr:stefan_ml': 0.16; 'from:name:stefan behnel': 0.16; 'manageable': 0.16; 'received:80.91.229.3': 0.16; 'received:plane.gmane.org': 0.16; 'subject:generation': 0.16; 'elements': 0.16; 'wrote:': 0.18; 'pointed': 0.19; 'stefan': 0.19; 'written': 0.21; '>>>': 0.22; 'header:User-Agent:1': 0.23; 'now?': 0.24; 'header:X-Complaints-To:1': 0.27; 'header:In-Reply-To:1': 0.27; 'am,': 0.29; 'room': 0.29; 'fri,': 0.33; 'could': 0.34; 'something': 0.35; 'received:84': 0.35; 'there': 0.35; 'doubt': 0.36; 'processed': 0.36; 'list': 0.37; 'being': 0.38; 'to:addr :python-list': 0.38; 'though,': 0.39; 'to:addr:python.org': 0.39; 'received:org': 0.40; 'ian': 0.60; "you'll": 0.62; 'more': 0.64; 'mar': 0.68; 'obvious': 0.74; 'yourself': 0.78; '100': 0.79; 'age': 0.80; '2015': 0.84; '9.6': 0.84; 'crucial': 0.91; 'hundred': 0.95 X-Injected-Via-Gmane: http://gmane.org/ To: python-list@python.org From: Stefan Behnel Subject: Re: Speeding up permutations generation Date: Fri, 06 Mar 2015 21:24:40 +0100 References: Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit X-Gmane-NNTP-Posting-Host: dslb-084-056-062-139.084.056.pools.vodafone-ip.de User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.4.0 In-Reply-To: X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.19 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: 28 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1425673495 news.xs4all.nl 2941 [2001:888:2000:d::a6]:37464 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:87059 Ian Kelly schrieb am 06.03.2015 um 18:13: > On Fri, Mar 6, 2015 at 1:24 AM, Abhiram R wrote: >>> A list of 100 elements has approximately 9.33 x 10**157 permutations. >>> If you could somehow generate one permutation every yoctosecond, >>> exhausting them would still take more than a hundred orders of >>> magnitude longer than the age of the universe. >> >> True that :D I may have exaggerated on the number. Let's consider something >> more practically manageable => 50 elements with a 50! permutation. >> Is there a solution now? > > That's still infeasible, as others have pointed out. At one > permutation every picosecond, you'll still need 9.6 x 10**44 years. > > If the size isn't that important to you and you just want a faster > implementation of permutations, you could try reimplementing it > yourself as a C extension. The stdlib implementation is already > written in C though, so unless you have a better algorithm I doubt > you'll find much room for optimization. Well, one obvious "optimisation" in a case like this is to change the order in which permutations are returned. If processing all of them is infeasible, then being able to control which ones will be processed can be a crucial property of a "better" algorithm. Stefan