Python: generateeuro-millions combinations Post: 302512600

Sponsored Content

Top Forums Shell Programming and Scripting Python: generateeuro-millions combinations Post 302512600 by penguin-friend on Monday 11th of April 2011 04:22:00 AM

04-11-2011

Registered User

Python: generateeuro-millions combinations

Hello All!!
Long time since i haven't been here, but here is my new question.
I love giving myself challenges. Here is the new one:
in the european euro-million, you choose 5 from 50 numbers plus 2 from from 9 "stars" (9 numbers).
So in fact, you have the possibility to have 76275360 combinations possible ( 5 from 50 * 2 from 9). Order has no importance.
I wrote this bit of code to generate the 5 from 50 combinations:

Code:

from time import time

def combinations(list, k):
    """Choose combinations of list, choosing k elements(no repeats)"""
    A=[]
    if len(list) < k:
        return []
    else:
        seq = [i for i in range(k)]
        while seq:
            #print[list[index] for index in seq]
            if[list[index] for index in seq] not in A:
                A.append([list[index] for index in seq])
            seq = get_next_combination(len(list), k, seq)
        return A

def get_next_combination(num_elements, k, seq):
        index_to_move = find_index_to_move(num_elements, seq)
        if index_to_move == None:
            return None
        else:
            seq[index_to_move] += 1
            #for every element past this sequence, move it down
            for i, elem in enumerate(seq[(index_to_move+1):]):
                seq[i + 1 + index_to_move] = seq[index_to_move] + i + 1
            return seq

def find_index_to_move(num_elements, seq):
        """Tells which index should be moved"""
        for rev_index, elem in enumerate(reversed(seq)):
            if elem < (num_elements - rev_index - 1):
                return len(seq) - rev_index - 1
        return None

def main(n,p):

    F=combinations(range(1,n+1),p)
    print len(F)

if __name__ == '__main__':

    start=time()
    main(50,3)
    end=time()
    print "total time:",end-start

Running it on my computer under windows) 3.5 GO RAM and Core Duo 3GHz, it took 26 hours!!!!!!

So, could anybody help me to get the code faster? And to add the part concerning the 2 "stars"?

Thanx in advance....

penguin-friend

View Public Profile for penguin-friend

Find all posts by penguin-friend

8 More Discussions You Might Find Interesting

1. UNIX for Dummies Questions & Answers

dump/restore of a fs with 100 of millions hardlinks

Hi :-) i have a dump of a backupdisk (~540GB / ext3). The Backups have some 100 millions of hardlinks (backups are created with storeBackup). The OS is linux. A restore of a directory ended after some days with the errormessage "no memory to extend symbol table" The restore of the complete...

2. Shell Programming and Scripting

Generating millions of record using shell script

Hi All, My requirement is like this. I want to generate records of 1 million lines. If I say lines it means one line will contain some string or numbers like AA,3,4,45,+223424234,Tets,Ghdj,+33434,345453434,........................ upto length lets say 41. ( 41 comma sepearted aplha numneric...

3. UNIX for Advanced & Expert Users

How to zip/tar millions of files?

Hi guys, I have an issue processing a large amount of files. I have around 5 million files (some of them are actually directories) in a server. I am unable to find out the exact number of files since it's taking "forever" to finish (See this thread for more on the issue). Anyway, now I...

4. Shell Programming and Scripting

Need script to remove millions of tmp files in /html/cache/ directory

Hello, I just saw that on my vps (centOS) my oscommerce with a seo script has created millions of tmp files inside the /html/cache/ directory. I would need to remove all those files (millions), I tried via shell but the vps loads goes to very high and it hangs, is there some way to do a...

5. Shell Programming and Scripting

Need an efficient way to search for a tag in an xml file having millions of rows

Hi, I have an XML file with around 1 billion rows in it and i am trying to find the number of times a particular tag occurs in it. The solution i am using works but takes a lot of time (~1 hr) .Please help me with an efficient way to do this. Lets say the input file is <Root> ...

6. Shell Programming and Scripting

Millions of record using shell script

I wanna create a millions of record using shell scripts.. the scenario is somehow like this,,,i want to create the record for these fields in my database..id,name,addrs,sales. So can you please give a overall idea for how to achieve it?

7. Shell Programming and Scripting

How to create a file contains millions of lines and each line has different datas?

I want to create a file contains millions of lines. The line format like this: acnum$$123456$$+$$Tom$$111$$ fields separated by $$, field 1 and field 3 have only two options:acnum or crenum; + or -. field 4 can be any name or any letters. Other fields can be any fixed length digits. So, I want to...

8. UNIX for Beginners Questions & Answers

Print a python script down a list in a text file without printing a lot combinations

In a python script I have 2 files printing side by side on the same line. I want to have 1 of the files to be already displayed at once while the other file print down the list in the file and it still will produce new lines. I want to do it like that to reduce printing a lot of lines and...

LEARN ABOUT LINUX

dh_python

DH_PYTHON(1)							     Debhelper							      DH_PYTHON(1)

NAME

       dh_python - calculates Python dependencies and adds postinst and prerm Python scripts (deprecated)

SYNOPSIS

       dh_python [debhelperoptions] [-n] [-V version] [moduledirs...]

DESCRIPTION

       Note: This program is deprecated. You should use dh_pysupport or dh_pycentral instead. This program will do nothing if debian/pycompat or a
       Python-Version control file field exists.

       dh_python is a debhelper program that is responsible for generating the ${python:Depends} substitutions and adding them to substvars files.
       It will also add a postinst and a prerm script if required.

       The program will look at Python scripts and modules in your package, and will use this information to generate a dependency on python, with
       the current major version, or on pythonX.Y if your scripts or modules need a specific python version. The dependency will be substituted
       into your package's control file wherever you place the token ${python:Depends}.

       If some modules need to be byte-compiled at install time, appropriate postinst and prerm scripts will be generated. If already byte-
       compiled modules are found, they are removed.

       If you use this program, your package should build-depend on python.

OPTIONS

       module dirs
	   If your package installs Python modules in non-standard directories, you can make dh_python check those directories by passing their
	   names on the command line. By default, it will check /usr/lib/site-python, /usr/lib/$PACKAGE, /usr/share/$PACKAGE,
	   /usr/lib/games/$PACKAGE, /usr/share/games/$PACKAGE and /usr/lib/python?.?/site-packages.

	   Note: only /usr/lib/site-python, /usr/lib/python?.?/site-packages and the extra names on the command line are searched for binary (.so)
	   modules.

       -V version
	   If the .py files your package ships are meant to be used by a specific pythonX.Y version, you can use this option to specify the
	   desired version, such as 2.3. Do not use if you ship modules in /usr/lib/site-python.

       -n, --noscripts
	   Do not modify postinst/prerm scripts.

CONFORMS TO

       Debian policy, version 3.5.7

       Python policy, version 0.3.7

SEE ALSO

       debhelper(7)

       This program is a part of debhelper.

AUTHOR

       Josselin Mouette <joss@debian.org>

       most ideas stolen from Brendan O'Dea <bod@debian.org>

8.9.0ubuntu2.1							    2012-06-12							      DH_PYTHON(1)