Path: csiph.com!usenet.pasdenom.info!news.redatomik.org!newsfeed.xs4all.nl!newsfeed1.news.xs4all.nl!xs4all!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.075 X-Spam-Evidence: '*H*': 0.85; '*S*': 0.00; 'talks': 0.03; 'problem?': 0.07; 'cc:addr:python-list': 0.11; 'python': 0.11; 'from:addr:rosuav': 0.16; 'from:name:chris angelico': 0.16; 'iterating': 0.16; 'manageable': 0.16; 'subject:generation': 0.16; 'elements': 0.16; 'wrote:': 0.18; 'all,': 0.19; 'trying': 0.19; 'memory': 0.22; 'cc:addr:python.org': 0.22; 'now?': 0.24; 'cc:2**0': 0.24; 'header:In-Reply-To:1': 0.27; 'message- id:@mail.gmail.com': 0.30; 'url:mailman': 0.30; 'code': 0.31; 'usually': 0.31; 'about.': 0.31; 'url:python': 0.33; 'fri,': 0.33; 'guess': 0.33; 'programmers': 0.33; 'actual': 0.34; 'could': 0.34; 'something': 0.35; 'received:google.com': 0.35; 'there': 0.35; 'url:listinfo': 0.36; 'url:org': 0.36; 'wrong': 0.37; 'list': 0.37; 'pm,': 0.38; 'expect': 0.39; 'extremely': 0.39; 'generating': 0.39; 'url:mail': 0.40; 'even': 0.60; 'hope': 0.61; 'mentioned': 0.61; 'simply': 0.61; "you're": 0.61; 'more': 0.64; 'mar': 0.68; '100': 0.79; 'age': 0.80; '2015': 0.84; 'itertools,': 0.84; 'measure.': 0.84; 'to:none': 0.92; 'hundred': 0.95 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:cc :content-type; bh=D6kXAlCks8NYuRYzPikEsmYUPqeiezJgJIMV4o9zViw=; b=FFCpDwTGzAev5xaUI3QxYJcnK4OU+Q00ni0OMRxW4Z07+r+wFHwCcIGBr48zQOtNi1 E8QpTusxaA7/iLYSbHXAj1nWGUyDxdQKW2wXOW+oRWQTnXGOGEmqnzzcqhuZGS++Ji02 tX7kbHghuTdUZOyTis0fFA9V2f296sUevPBcz7xvtq2j1qajqujEZxGPqj6qeHg/eFhF LbvAciT45Xx5UT+j73eYBRp+4wwsUg8sMm7oT9G4gHB3pMlCuwGVTGLDhc48fpHuwwBG kjahjYbTpR3ZcoX9Ia1fgVSAy0wk3xeTJOkS6EuuSiLgd20zXw29bu/PxfHOdqz3G0b7 Qn4A== MIME-Version: 1.0 X-Received: by 10.107.128.219 with SMTP id k88mr26105148ioi.27.1425635954717; Fri, 06 Mar 2015 01:59:14 -0800 (PST) In-Reply-To: References: Date: Fri, 6 Mar 2015 20:59:14 +1100 Subject: Re: Speeding up permutations generation From: Chris Angelico Cc: Python Content-Type: text/plain; charset=UTF-8 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: 25 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1425635964 news.xs4all.nl 2912 [2001:888:2000:d::a6]:50546 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:87005 On Fri, Mar 6, 2015 at 7:24 PM, 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. >> -- >> https://mail.python.org/mailman/listinfo/python-list > > > 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? > Is the actual generation of permutations your problem? You mentioned that you're using itertools, so I would expect that you're simply iterating over that; I hope you're not immediately trying to construct a list of them all, because that would cost the memory that Mark's response talks about. Have you actually profiled your code and found that generating permutations is the bottleneck, or did you just guess? Because even experienced programmers - even extremely experienced Python programmers - are usually wrong when they guess about the slowest part of a program. The only way to know is to measure. ChrisA