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"?
i didn't read your codes through. I wrote a py script, to do the combination calculation (5 from 50). you can change the two numbers. of course some validation was not implemented, e.g m(5) should be smaller than n(50) etc.
I saved the results in a list (result), didn't print it out or save into a file. the output of my codes was just the total possibilities. (2118760). it took 2min and 50 secs to calculate C 50 5.
Code:
kent$ time python pySolution.py
2118760
python pySolution.py 167.13s user 0.64s system 98% cpu 2:50.08 total
here are the python script:
PHP Code:
#!/usr/bin/python def getCombinations(n,m): allNum = range(1,n+1) idx = [0]*n # index matrix idxMatrix = [] result = []
for i in range(m): idx[i]=1 idxMatrix.append(idx) while(getIdxMatrix(idxMatrix,m)): pass for l in idxMatrix: #print l result.append([x for x in allNum if l[allNum.index(x)]]) print len(result)
def getIdxMatrix(idxMatrix,m): last = idxMatrix[-1] newline = list(last) for i in range(len(newline)): if i!=len(newline)-1 and newline[i]==1 and newline[i+1]==0: su = sum(last[:i]) newline[i],newline[i+1] = 0,1 for j in range(i): newline[j]=1 if j<su else 0 idxMatrix.append(newline) return True return False
10 seconds here to write all combinations to a file (3 seconds to just run and count without i/o), on a core2duo 2.16 GHz cpu (circa 2007 laptop).
Code:
$ time ./em.py > out
real 0m10.227s
user 0m9.926s
sys 0m0.300s
$ wc -l out
2118760 out
In the following code:
n = how many numbers to use (50 = range from 1 to 50)
p = the number of placeholders in the drawing (5)
a = array containing the placeholders
i = shortlived misc index
j = shortlived misc index
Code:
#!/usr/bin/env python
def perms(n, p):
a = []
j = p
for i in range(p):
a.append(j)
j -= 1
while True:
print a
for i in range(p):
if a[i] < n - i:
a[i] += 1
for j in range(0, i):
a[j] = a[i] + i - j
break
else:
break
if __name__ == '__main__':
perms(50, 5)
Nicely done. I seldom hack in python (usually only when I need to tweak a tool to add/fix a feature), so I don't know it or its libraries very well. Still, after googling itertools and finding that the module is implemented in C, I'm confident your solution is as fast as it gets using python. http://svn.python.org/view/python/tr...89&view=markup
Amusingly, I just tried to time the itertools approach on my machine, but since the only python I have installed is 2.5.1 (it's not my main machine), itertools is not available (it's new in 2.6). It's an old OSX Tiger macbook that I don't use much.
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... (0 Replies)
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... (9 Replies)
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? (9 Replies)
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>
... (13 Replies)
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... (7 Replies)
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... (6 Replies)
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... (2 Replies)
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... (0 Replies)