yet another noob question

[mike_wilson1333]

I would like to generate every unique combination of numbers 1-5 in a 5
digit number and follow each combo with a newline. So i'm looking at
generating combinations such as: (12345) , (12235), (55554) and so on.
What would be the best way to do this? So, basically i'm looking for a
list of all combinations of 1-5 in a 5 digit unique number. Also, when
I send the list to print there can't be any duplicates of the combos.
Thanks,

Mike

[Stargaming]

mike_wilson1333 schrieb:

I would like to generate every unique combination of numbers 1-5 in a 5
digit number and follow each combo with a newline. So i'm looking at
generating combinations such as: (12345) , (12235), (55554) and so on.
What would be the best way to do this? So, basically i'm looking for a
list of all combinations of 1-5 in a 5 digit unique number. Also, when
I send the list to print there can't be any duplicates of the combos.
Thanks,

Mike

Generally, it is range(11111, 55555)

Sincerely,
Stargaming
--

[Simon Forman]

mike_wilson1333 wrote:

I would like to generate every unique combination of numbers 1-5 in a 5
digit number and follow each combo with a newline. So i'm looking at
generating combinations such as: (12345) , (12235), (55554) and so on.
What would be the best way to do this? So, basically i'm looking for a
list of all combinations of 1-5 in a 5 digit unique number. Also, when
I send the list to print there can't be any duplicates of the combos.
Thanks,

Mike

Hi Mike, this is one of those "Somebody must have had this problem
before me" kind of situations. Google on "python combination" and you
should be well rewarded. :-)

Peace,
~Simon

[Rene Pijlman]

mike_wilson1333:

>I would like to generate every unique combination of numbers 1-5 in
a 5 digit number [...] What would be the best way to do this?

Ask the Java newsgroup to design a clever algorithm and post it here for
pythonification. Ask for the pseudocode, not the Java code.

--
René Pijlman

[Rene Pijlman]

Stargaming:

>Generally, it is range(11111, 55555)

Minus all numbers whose decimal string representation matches
[0-9]*[06-9][0-9]* Briljant!

--
René Pijlman

[Stargaming]

Stargaming schrieb:

mike_wilson1333 schrieb:

>I would like to generate every unique combination of numbers 1-5 in a 5
digit number and follow each combo with a newline. So i'm looking at
generating combinations such as: (12345) , (12235), (55554) and so on.
What would be the best way to do this? So, basically i'm looking for a
list of all combinations of 1-5 in a 5 digit unique number. Also, when
I send the list to print there can't be any duplicates of the combos.
Thanks,

Mike

Generally, it is range(11111, 55555)

Sincerely,
Stargaming

Whoops, I'm sorry. I think I was a little bit too enthusiastic and "wow
look 'print range' is fun!". You could do a list comprehension over the
range thingy.

[Simon Forman]

Stargaming wrote:

Stargaming schrieb:

mike_wilson1333 schrieb:

I would like to generate every unique combination of numbers 1-5 in a 5
digit number and follow each combo with a newline. So i'm looking at
generating combinations such as: (12345) , (12235), (55554) and so on.
What would be the best way to do this? So, basically i'm looking for a
list of all combinations of 1-5 in a 5 digit unique number. Also, when
I send the list to print there can't be any duplicates of the combos.
Thanks,

Mike

Generally, it is range(11111, 55555)

Sincerely,
Stargaming

Whoops, I'm sorry. I think I was a little bit too enthusiastic and "wow
look 'print range' is fun!". You could do a list comprehension over the
range thingy.

def stoopid_way(start, end):
for n in xrange(start, end + 1):

# Make a string.
s = '%d' % n

# Exclude 0's.
if '0' in s: continue

# Exclude 6-9's.
try:
int(s, 6)
except ValueError:
continue

yield s

Use it like so:

# Get all the strings as a list..
data = list(stoopid_way(11111, 55555))

# ..or print the strings one-by-one..
for s in stoopid_way(11111, 55555):
print s

# ..or print one big string, joined by newlines.
print '\n'.join(stoopid_way(11111, 55555))
I originally meant this as a joke and was going to say not to use it.
But on my old, slow computer it only takes about a second or two. If
that's fast enough for you then it won't do any harm to use it. (Just
don't mention my name ;-) )

Peace,
~Simon

[Alex Martelli]

mike_wilson1333 <mw*********@hotmail.comwrote:

I would like to generate every unique combination of numbers 1-5 in a 5
digit number and follow each combo with a newline. So i'm looking at
generating combinations such as: (12345) , (12235), (55554) and so on.
What would be the best way to do this? So, basically i'm looking for a
list of all combinations of 1-5 in a 5 digit unique number. Also, when
I send the list to print there can't be any duplicates of the combos.

[[warning: haven't tried out any of the following code, just typed it
into the newsreader, so there may be typos or whatnot, but, I'm focusing
on communicating the general ideas anyway:-)]]
A working but boilerplatey solution is to nest 5 loops...:

r = range(1, 6)
for i0 in r:
for i1 in r:
for i2 in r:
for i3 in r:
for i4 in r:
print '(%d%d%d%d%d)' % (i0,i1,i2,i3,i4)

While this does work, it's inelegant -- "flat is better than nested",
and all that. Hard-coding the exact number of nested loops, etc, is
definitely not ideal.

So here's an alternative:

def allcomb(seq=range(1, 6), reps=5):
counter = reps*[0]
format = '(' + '%s'*reps + ')'
maxcount = len(seq)-1
while True:
print format % tuple(seq[i] for i in counter)
i = 0
while i<reps and counter[i]==maxcount:
counter[i] = 0
i += 1
if i >= reps: return
counter[i] += 1

You can have many variations on this theme, but basically what they're
doing is "counting in base N" (where N is len(seq)) -- variations around
that are mere stylistic issues. For example, the inner loop (after the
print statement) could become:
for i in range(reps):
if counter[i] < maxcount:
counter[i] += 1
break
else:
counter[i] = 0
else:
return
or, you could loop with "for i, c in enumerate(counter):", etc, etc --
but these variations are all implementing the same algorithm. One
algorithms that's definitely different enough to distinguish is to use
recursion -- but it won't offer much advantage over this one.
Alex

[bearophileHUGS]

Simon Forman:

I originally meant this as a joke and was going to say not to use it.
But on my old, slow computer it only takes about a second or two.

Another possibility, still using a filter:

nodig = set("06789")
r = [i for i in xrange(11111, 55555+1) if not (set(`i`) & nodig)]

Bye,
bearophile

[Paul Rubin]

"mike_wilson1333" <mw*********@hotmail.comwrites:

I would like to generate every unique combination of numbers 1-5 in a 5
digit number and follow each combo with a newline. So i'm looking at
generating combinations such as: (12345) , (12235), (55554) and so on.
What would be the best way to do this? So, basically i'm looking for a
list of all combinations of 1-5 in a 5 digit unique number. Also, when
I send the list to print there can't be any duplicates of the combos.

Basically you want to print a list of integers in 5-digit base-5
notation, except relabelling the digits. There will be (5**5 - 1)
numbers in the list. You want to print 0 as '11111', 1 as '11112',
etc. Here's one way to get the representation. It's sort of a
"functional" approach using recursion, but feels natural if you're
into that sort of thing:

def base5x(k, ndigits):
if ndigits == 1: return '%d'% (k+1)
return base5x(k//5, ndigits-1) + base5x(k%5, 1)

Now you can use the function to print the list you wanted:

for i in xrange(1234,1333):
print base5x(i, 5)

[Paul Rubin]

Paul Rubin <http://ph****@NOSPAM.invalidwrites:

Now you can use the function to print the list you wanted:

for i in xrange(1234,1333):
print base5x(i, 5)

Whoops, pasted the wrong thing from my test window. Sorry. That
was supposed to say:

for i in xrange(5**5):
print base5x(i, 5)

[Cameron Laird]

In article <1h*************************@mac.com>,
Alex Martelli <al***@mac.comwrote:

>mike_wilson1333 <mw*********@hotmail.comwrote:

>I would like to generate every unique combination of numbers 1-5 in a 5
digit number and follow each combo with a newline. So i'm looking at

[mensanator]

Sybren Stuvel wrote:

mike_wilson1333 enlightened us with:

I would like to generate every unique combination of numbers 1-5 in a 5
digit number and follow each combo with a newline. So i'm looking at
generating combinations such as: (12345) , (12235), (55554) and so on.

Count from 0 to 44444 in a base-5 numbering, and add 11111 to every
number.

b5_11111 = int('11111', 5)

for i in range(int('44444', 5)+1):
i += b5_11111
print i

Only the print command needs to convert back to base-5. Does anyone
know of an elegant way to do that?

Use the gmpy module which does base conversion in both directions.

>>import gmpy
b5_11111 = gmpy.mpz('11111',5)
b5_11111

mpz(781)

>>print gmpy.digits(b5_11111,5)

11111

>
Sybren
--
The problem with the world is stupidity. Not saying there should be a
capital punishment for stupidity, but why don't we just take the
safety labels off of everything and let the problem solve itself?
Frank Zappa

[Jason Nordwick]

def pr(x): print(x)

>>x=map(pr,[x for x in xrange(11,56) if '1'<=min(str(x)) and max(str(x))<='5'])

11
12
13
14
15
21
22
23
24
25
31
32
33
34
35
41
42
43
44
45
51
52
53
54
55
mike_wilson1333 wrote:

I would like to generate every unique combination of numbers 1-5 in a 5
digit number and follow each combo with a newline. So i'm looking at
generating combinations such as: (12345) , (12235), (55554) and so on.
What would be the best way to do this? So, basically i'm looking for a
list of all combinations of 1-5 in a 5 digit unique number. Also, when
I send the list to print there can't be any duplicates of the combos.
Thanks,

Mike

[Jason Nordwick]

Or without filter:

from operator import add
def pr(x): print x
def cross(x,y): return reduce(add, [[a+b for b in y] for a in x])
x=map(pr, reduce(cross, [map(str,range(1,6))]*5))

mike_wilson1333 wrote:

I would like to generate every unique combination of numbers 1-5 in a 5
digit number and follow each combo with a newline. So i'm looking at
generating combinations such as: (12345) , (12235), (55554) and so on.
What would be the best way to do this? So, basically i'm looking for a
list of all combinations of 1-5 in a 5 digit unique number. Also, when
I send the list to print there can't be any duplicates of the combos.
Thanks,

Mike

[Jason Nordwick]

better (sorry, still learning Python):

def cross(x,y): return [a+b for a in x for y in b]

Jason Nordwick wrote:

Or without filter:

from operator import add
def pr(x): print x
def cross(x,y): return reduce(add, [[a+b for b in y] for a in x])
x=map(pr, reduce(cross, [map(str,range(1,6))]*5))

mike_wilson1333 wrote:

>I would like to generate every unique combination of numbers 1-5 in a 5
digit number and follow each combo with a newline. So i'm looking at
generating combinations such as: (12345) , (12235), (55554) and so on.
What would be the best way to do this? So, basically i'm looking for a
list of all combinations of 1-5 in a 5 digit unique number. Also, when
I send the list to print there can't be any duplicates of the combos.
Thanks,

Mike

[Stargaming]

Jason Nordwick schrieb:

Or without filter:

from operator import add
def pr(x): print x
def cross(x,y): return reduce(add, [[a+b for b in y] for a in x])
x=map(pr, reduce(cross, [map(str,range(1,6))]*5))

[...]

reduce(add, list) is the same as sum(list) and is only half as fast as sum:

>>from timeit import Timer
sum(Timer("sum(range(500))").repeat(200, 1000))/200

0.055693786500798058

>>sum(Timer("reduce(add, range(500))", "from operator import

add").repeat(200, 1000))/200
0.10820861031220445

>>>

Also note that reduce will be removed in Python 3000.

[bearophileHUGS]

Stargaming:

Also note that reduce will be removed in Python 3000.

Then let's use it until it lasts! :-)

bearophile

[Gerard Flanagan]

mike_wilson1333 wrote:

I would like to generate every unique combination of numbers 1-5 in a 5
digit number and follow each combo with a newline. So i'm looking at
generating combinations such as: (12345) , (12235), (55554) and so on.
What would be the best way to do this? So, basically i'm looking for a
list of all combinations of 1-5 in a 5 digit unique number. Also, when
I send the list to print there can't be any duplicates of the combos.
Thanks,

Mike

Hi Mike

mod5 = ['1','2','3','4','5']

X = [ ''.join([a,b,c,d,e])
for a in mod5
for b in mod5
for c in mod5
for d in mod5
for e in mod5 ]

assert len(X) == 5**5
assert len(set(X)) == 5**5 #no duplicates
Gerard

[bearophileHUGS]

Gerard Flanagan:

mod5 = ['1','2','3','4','5']
X = [ ''.join([a,b,c,d,e])
for a in mod5
for b in mod5
for c in mod5
for d in mod5
for e in mod5 ]

A modified version of your one is the faster so far:

v = "12345"
r = [a+b+c+d+e for a in v for b in v for c in v for d in v for e in v]

Bye,
bearophile

[Jason Nordwick]

Somehow my other response to the list got lost. I'm still learning Python, but this seems much better than my first attempt:

def pr(x): print x
def cross(x,y): return [a+b for a in x for b in y]
x=map(pr, reduce(cross, [map(str,range(1,6))]*5))

-j

Stargaming wrote:

Jason Nordwick schrieb:

>Or without filter:

from operator import add
def pr(x): print x
def cross(x,y): return reduce(add, [[a+b for b in y] for a in x])
x=map(pr, reduce(cross, [map(str,range(1,6))]*5))

[...]

reduce(add, list) is the same as sum(list) and is only half as fast as sum:

>>from timeit import Timer
>>sum(Timer("sum(range(500))").repeat(200, 1000))/200

0.055693786500798058

>>sum(Timer("reduce(add, range(500))", "from operator import

add").repeat(200, 1000))/200
0.10820861031220445

>>>

Also note that reduce will be removed in Python 3000.

[Jason Nordwick]

Stargaming wrote:

>
Also note that reduce will be removed in Python 3000.

What will replace it?

-j

[bearophileHUGS]

Jason Nordwick:

Stargaming wrote:

Also note that reduce will be removed in Python 3000.

What will replace it?

Nothing, I presume. You will have to write a function to find another
way to solve problems.

Bye,
bearophile

[Jason Nordwick]

*mouth agape*

Wow. That really sucks. I make extensive use of reduce. It seems to run more than twice as fast as a for loop.

>>t = Timer('bino.reduceadd(bino.bits)', 'import bino')
s = Timer('bino.loopadd(bino.bits)', 'import bino')
t.timeit(10)

1.2373670396656564

>>s.timeit(10)

2.6450051612705039

>>t.timeit(100)

11.312374896809501

>>s.timeit(100)

25.817132345032689

where

bits = map(lambda x:randint(0,1), xrange(1000000))

def reduceadd(v):
return reduce(add, v)

def loopadd(v):
sum = 0
for x in v:
sum = add(sum, x)
return sum

(Yes, I know there are better ways to sum up a list, but I just wanted to test the performance of the loop against reduce. In most of my reduce usages, the function passed to reduce is much more complex.)
-j
be************@lycos.com wrote:

Jason Nordwick:

>Stargaming wrote:

>>Also note that reduce will be removed in Python 3000.

What will replace it?

Nothing, I presume. You will have to write a function to find another
way to solve problems.

Bye,
bearophile

[AlbaClause]

mike_wilson1333 wrote:

I would like to generate every unique combination of numbers 1-5 in a 5
digit number and follow each combo with a newline. So i'm looking at
generating combinations such as: (12345) , (12235), (55554) and so on.
What would be the best way to do this? So, basically i'm looking for a
list of all combinations of 1-5 in a 5 digit unique number. Also, when
I send the list to print there can't be any duplicates of the combos.
Thanks,

Mike

This is one of those questions that reminded me that I don't know Python.
I launched my Python interpreter, and forgot how to even print a string.
Duh!

Oh well...

--
--
There are several things that I will never be:
* I will never be attracted to females.
* I will never enjoy the company of others.
Exactly how these realities bode for my enemy, is not of my concern.

[Stargaming]

Jason Nordwick wrote:
<benchmark here>

>
be************@lycos.com wrote:

>Jason Nordwick:

>>Stargaming wrote:

Also note that reduce will be removed in Python 3000.

What will replace it?

Nothing, I presume. You will have to write a function to find another
way to solve problems.

Bye,
bearophile

Well, *perhaps* there will be a new function product() -- and there we
go having replaced every arithmetical use of reduce() because Guido
cannot read them. Nice.

Read on: "The fate of reduce() in Python 3000"
http://www.artima.com/weblogs/viewpost.jsp?thread=98196 -- found on "PEP
3100 -- Miscellaneous Python 3.0 Plans"
http://www.python.org/dev/peps/pep-3100/#id63

Regards,
Stargaming
--

[starGaming]

Jason Nordwick wrote:

*mouth agape*

Wow. That really sucks. I make extensive use of reduce. It seems to run more than twice as fast as a for loop.

>t = Timer('bino.reduceadd(bino.bits)', 'import bino')
s = Timer('bino.loopadd(bino.bits)', 'import bino')
t.timeit(10)

1.2373670396656564

>s.timeit(10)

2.6450051612705039

>t.timeit(100)

11.312374896809501

>s.timeit(100)

25.817132345032689

where

bits = map(lambda x:randint(0,1), xrange(1000000))

def reduceadd(v):
return reduce(add, v)

def loopadd(v):
sum = 0
for x in v:
sum = add(sum, x)
return sum

(Yes, I know there are better ways to sum up a list, but I just wanted to test the performance of the loop against reduce. In most of my reduce usages, the function passed to reduce is much more complex.)

[...]

Assuming Guido van Rossum is right and reduce() is only useful for
arithmetic expressions (could you show an example where you use it
else?), you could take advantage of more "built-ins".
To spoiler the result of this, the loop-variant is slightly (in this
test: 2ms) faster.
The results on my amd64 3k+ were:
Reduce: 0.5686828074520.56633643382
For-loop: 0.56633643382

#!/usr/bin/env python
#
#

from random import randint
from timeit import Timer
from operator import add

def bits():
return [randint(0,1) for x in xrange(1000)]
# use def & list comprehension since lambda/map will be removed in
Python 3.0, too
print bits()[0:5]
print bits()[0:5] # it's working.

def reducefunc(x):
return reduce(add,x)
def loopfunc(x):
y = 0
for i in x: y += i
return y

x = bits()
print reducefunc(x)
print loopfunc(x) # both give proper output

print sum(Timer("reducefunc(bits())", "from __main__ import bits,
reducefunc").repeat(20,100))/20
print sum(Timer("loopfunc(bits())", "from __main__ import bits,
loopfunc").repeat(20,100))/20

[Jason Nordwick]

I use reduce to also do indexing, hashing with upsert semantics of lists of key-value pairs, transitioning through a state table, etc...

Somebody else pointed out to me how odd it is of Python to be ditching reduce when Guido van Rossum was hired by Google, and Google is literally built on map and reduce (http://en.wikipedia.org/wiki/Mapreduce).

Here is a code fragment I pulled from what I am currently working on (with a little modification to make things simple):

First build a tree:

>>def byn(a,n): return [[a[i] for i in x] for x in zip(*[range(y,len(a),n) for y in range(n)])]

....

>>def whilep(pred,f,x):

.... while pred(x): x = f(x)
.... return x
....

>>t = whilep(lambda x:1<len(x), lambda x:byn(x,2), map(chr,range(97,97+16)))

t

[[[[['a', 'b'], ['c', 'd']], [['e', 'f'], ['g', 'h']]], [[['i', 'j'], ['k', 'l']], [['m', 'n'], ['o', 'p']]]]]

Now if I had the list [0,1,0,0,1] and needed to find what letter it encodes:

>>t[0][1][0][0][1]

'j'

But sometimes, I want to be able to index branches or the leaves are at different depths, so I essentially have a list of indexes to follow:

>>def indexDepth(a,i): return reduce(lambda x,y: x[y], i, a)

....

>>indexDepth(t,[0,1,0,0,1])

'j'
Also, I completely understand your timings, but you are not timing reduce against a hand coded loop, but instead the operator '+' against the function add, as the function symbol lookup and call seem to have a heavy price. Reduce was one of the nice ways to eliminate some of those lookups.

-j
st********@gmail.com wrote:

Jason Nordwick wrote:

>*mouth agape*

Wow. That really sucks. I make extensive use of reduce. It seems to run more than twice as fast as a for loop.

>>>>t = Timer('bino.reduceadd(bino.bits)', 'import bino')
s = Timer('bino.loopadd(bino.bits)', 'import bino')
t.timeit(10)

1.2373670396656564

>>>>s.timeit(10)

2.6450051612705039

>>>>t.timeit(100)

11.312374896809501

>>>>s.timeit(100)

25.817132345032689

where

bits = map(lambda x:randint(0,1), xrange(1000000))

def reduceadd(v):
return reduce(add, v)

def loopadd(v):
sum = 0
for x in v:
sum = add(sum, x)
return sum

(Yes, I know there are better ways to sum up a list, but I just wanted to test the performance of the loop against reduce. In most of my reduce usages, the function passed to reduce is much more complex.)

[...]

Assuming Guido van Rossum is right and reduce() is only useful for
arithmetic expressions (could you show an example where you use it
else?), you could take advantage of more "built-ins".
To spoiler the result of this, the loop-variant is slightly (in this
test: 2ms) faster.
The results on my amd64 3k+ were:
Reduce: 0.5686828074520.56633643382
For-loop: 0.56633643382

#!/usr/bin/env python
#
#

from random import randint
from timeit import Timer
from operator import add

def bits():
return [randint(0,1) for x in xrange(1000)]
# use def & list comprehension since lambda/map will be removed in
Python 3.0, too
print bits()[0:5]
print bits()[0:5] # it's working.

def reducefunc(x):
return reduce(add,x)
def loopfunc(x):
y = 0
for i in x: y += i
return y

x = bits()
print reducefunc(x)
print loopfunc(x) # both give proper output

print sum(Timer("reducefunc(bits())", "from __main__ import bits,
reducefunc").repeat(20,100))/20
print sum(Timer("loopfunc(bits())", "from __main__ import bits,
loopfunc").repeat(20,100))/20

[Steve Holden]

Jason Nordwick wrote:

I use reduce to also do indexing, hashing with upsert semantics of lists of key-value pairs, transitioning through a state table, etc...

Somebody else pointed out to me how odd it is of Python to be ditching reduce when Guido van Rossum was hired by Google, and Google is literally built on map and reduce (http://en.wikipedia.org/wiki/Mapreduce).

That seems a bit literal. Just because they use a tool called MapReduce
that doesn't imply that thay chose to implement it with the Python map()
and reduce() functions. It's a distributed application, in case you
hadn't noticed ...

regards
Steve
--
Steve Holden [phone] [phone]
Holden Web LLC/Ltd http://www.holdenweb.com
Skype: holdenweb http://holdenweb.blogspot.com
Recent Ramblings http://del.icio.us/steve.holden

[Jason Nordwick]

That isn't what I meant. If there was a a point (and I'm not really sure that I'm even trying to make one), the point was that Google makes heavy use of reduce-like functionality, essentially implementing a distributed reduce across a cluster. From what I hear, they use a lot of Python and hired van Rossum for a reason. It just seems odd (don't read anything into this than mere cocked eyebrows) that the language designer that they hired and obviously have a lot of trust in would decide that reduce was essentially pointless. Google's distributed reduce seems to point in opposite way.

However, if reduce could be rolled into the list comprehension syntax, that would be even better. Or take it that extra step and roll a grouping functionality in there too, then you would have map, reduce, group, and filter all in one construct. You could call it select (joins are merely indexes into other structures).

-j
Steve Holden wrote:

Jason Nordwick wrote:

>I use reduce to also do indexing, hashing with upsert semantics of lists of key-value pairs, transitioning through a state table, etc...

Somebody else pointed out to me how odd it is of Python to be ditching reduce when Guido van Rossum was hired by Google, and Google is literally built on map and reduce (http://en.wikipedia.org/wiki/Mapreduce).

That seems a bit literal. Just because they use a tool called MapReduce
that doesn't imply that thay chose to implement it with the Python map()
and reduce() functions. It's a distributed application, in case you
hadn't noticed ...

regards
Steve