"number-in-base" ``oneliner''

[Alex Martelli]

I hesitate a bit to post this, but... on the Italian Python NG, somebody
was asking whether there was any way to convert an integer number x into
a string which represents it in an arbitrary base N (given a sequence
with a len of N that gives the digits to use) as "a single expression".

I haven't found a really general way, much less a clear one, but, the
best I have so far is...:

def number_in_base(x, N, digits, maxlen=99):
return '-'[x>=0:] + (
(x and ''.join([digits[k%N] for i in range(maxlen)
for k in [abs(x)//N**i] if k>0])[::-1]
) or digits[0])

Besides the lack of clarity, the obvious defect of this approach is that
darned 'maxlen' parameter -- but then, since I can have only a 'for',
not a 'while', in a list comprehension or generator expression, and I
don't think recursion qualifies as 'a single expression'...:-(

Anyway, improvements and suggestions welcome, thanks!


Alex

 

[Bengt Richter]

I hesitate a bit to post this, but... on the Italian Python NG, somebody
was asking whether there was any way to convert an integer number x into
a string which represents it in an arbitrary base N (given a sequence
with a len of N that gives the digits to use) as "a single expression".

I haven't found a really general way, much less a clear one, but, the
best I have so far is...:

def number_in_base(x, N, digits, maxlen=99):
return '-'[x>=0:] + (
(x and ''.join([digits[k%N] for i in range(maxlen)
for k in [abs(x)//N**i] if k>0])[::-1]
) or digits[0])

Besides the lack of clarity, the obvious defect of this approach is that
darned 'maxlen' parameter -- but then, since I can have only a 'for',
not a 'while', in a list comprehension or generator expression, and I
don't think recursion qualifies as 'a single expression'...:-(

Anyway, improvements and suggestions welcome, thanks!

Maybe something useful in this? Not very tested (and not terribly clear either ;-)
... return x==0 and digits[0] or '-'[:x<0] + ''.join([d for d in iter(
... lambda qr=[abs(x),0]:qr[0] and (
... qr.__setslice__(0,2,divmod(qr[0],N)) or digits[qr[1]])
... , 0)][::-1])
... '-1111110'

Even less tested, and using a list subtype with overridden next to do the same:
... return x==0 and digits[0] or '-'[:x<0] + ''.join([d for d in type('',(list,),{
... '__iter__':lambda s:s, 'next':lambda s
... s[0] is 0 and iter([]).next() or
... s.__setslice__(0,2,divmod(s[0],N)) or digits[s[1]])
... })([abs(x),0])][::-1])
... '1'

;-)

Regards,
Bengt Richter

 

[Bengt Richter]

I hesitate a bit to post this, but... on the Italian Python NG, somebody
was asking whether there was any way to convert an integer number x into
a string which represents it in an arbitrary base N (given a sequence
with a len of N that gives the digits to use) as "a single expression".

I haven't found a really general way, much less a clear one, but, the
best I have so far is...:

def number_in_base(x, N, digits, maxlen=99):
return '-'[x>=0:] + (
(x and ''.join([digits[k%N] for i in range(maxlen)
for k in [abs(x)//N**i] if k>0])[::-1]
) or digits[0])

Besides the lack of clarity, the obvious defect of this approach is that
darned 'maxlen' parameter -- but then, since I can have only a 'for',
not a 'while', in a list comprehension or generator expression, and I
don't think recursion qualifies as 'a single expression'...:-(

Anyway, improvements and suggestions welcome, thanks!

Maybe something useful in this? Not very tested (and not terribly clear either ;-)
... return x==0 and digits[0] or '-'[:x<0] + ''.join([d for d in iter(
... lambda qr=[abs(x),0]:qr[0] and (
... qr.__setslice__(0,2,divmod(qr[0],N)) or digits[qr[1]])
... , 0)][::-1])
... '-1111110'

Even less tested, and using a list subtype with overridden next to do the same:
... return x==0 and digits[0] or '-'[:x<0] + ''.join([d for d in type('',(list,),{
... '__iter__':lambda s:s, 'next':lambda s
... s[0] is 0 and iter([]).next() or
... s.__setslice__(0,2,divmod(s[0],N)) or digits[s[1]])
... })([abs(x),0])][::-1])
... '1'

;-)

Regards,
Bengt Richter

 

[Bengt Richter]

]

Maybe something useful in this? Not very tested (and not terribly clear either ;-)
... return x==0 and digits[0] or '-'[:x<0] + ''.join([d for d in iter(
... lambda qr=[abs(x),0]:qr[0] and (
... qr.__setslice__(0,2,divmod(qr[0],N)) or digits[qr[1]])
... , 0)][::-1])
...

Alternatively, a little more compactly (though I feel guilty about the -1 ;-):
... return '-'[:x<0] + ''.join(list(iter(lambda qr=[abs(x),-1]: (qr[0] or qr[1]<0) and (
... qr.__setslice__(0,2,divmod(qr[0],N)) or digits[qr[1]]), False))[::-1])
... '0'

Regards,
Bengt Richter

 

[Alex Martelli]

def number_in_base(x, N, digits, maxlen=99):
return '-'[x>=0:] + (
(x and ''.join([digits[k%N] for i in range(maxlen)
for k in [abs(x)//N**i] if k>0])[::-1]
) or digits[0])

...
range(maxlen) can be replaced with range(int(math.log(x) / math.log(N))

+ 1).

Right! I had missed that because I was focusing on builtin names only.
Thanks!

Also, and perhaps you are already aware, number_in_base(x, 1, '0')

Yes, I was aware that the pre condition N>=2 (as well as other
preconditions, such as len(digits) >= N) are not checked; sorry for not
making that clear.

doesn't produce the correct output with the above algorithm, although I
believe it will if you switch to using math.log().

With math.log it raises a ZeroDivisionError -- arguably more correct
than a bunch of 0's, yes. It's interesting that the math.log
application does catch such errors as N<2;-).


Alex

 

[Bengt Richter]

]

Maybe something useful in this? Not very tested (and not terribly clear either ;-)

def number_in_base(x, N, digits):

... return x==0 and digits[0] or '-'[:x<0] + ''.join([d for d in iter(
... lambda qr=[abs(x),0]:qr[0] and (
... qr.__setslice__(0,2,divmod(qr[0],N)) or digits[qr[1]])
... , 0)][::-1])
...

Alternatively, a little more compactly (though I feel guilty about the -1 ;-):
... return '-'[:x<0] + ''.join(list(iter(lambda qr=[abs(x),-1]: (qr[0] or qr[1]<0) and (
... qr.__setslice__(0,2,divmod(qr[0],N)) or digits[qr[1]]), False))[::-1])
...

Yet another, prefixing digits instead of joining reversed list:
... return '-'[:x<0]+reduce(lambda s,c:c+s, iter(lambda qr=[abs(x),-1]: (qr[0] or qr[1]<0)
... and (qr.__setslice__(0,2,divmod(qr[0],N)) or digits[qr[1]]), False))
... '-1111110'

Regards,
Bengt Richter

 

[Andrea Griffini]

range(maxlen) can be replaced with range(int(math.log(x) / math.log(N)) + 1).

Log accepts the base as second argument.

def number_in_base(x, N=10, digits="0123456789ABCDEF"):
return '-'[x>=0:]+"".join(
[digits[abs(x)/N**i%N]
for i in xrange(1+int(math.log(abs(x)+1,N)))
if N**i<=abs(x)][::-1]) or digits[0]

Also, and perhaps you are already aware, number_in_base(x, 1, '0') doesn't produce the correct output with the above algorithm, although I believe it will if you switch to using math.log().

It doesn't handle roman numerals either... but so ?
You can't count using base 1 with positional systems.

Andrea

 

[Jeremy Bowers]

You can't count using base 1 with positional systems.

Well, you can, sort of. You end up with the integers, obviously, and the
result has a rather striking resemblance to the modern foundations of
number theory, in which there is only one number, 0, and the "increment"
function which returns a number one larger. If you want three, it is
expressed increment(increment(increment(0))), which is rather similar to
the base-1 number "111".

Zero in this system would probably be a null string, making increment this:

def increment(number):
return "1" + number

(And abracadabra, I'm back on topic for the newsgroup, albeit tenuously )

Some people say base 2 is the most natural base in the universe. But you
can certainly make a claim for base 1, based on its correspondence to
number theory, from which we build the rest of math. (Most people never
dig this deep; it was one of my favorite classes in Comp. Sci., though,
and we're probably the only people other than mathematicians to offer the
course.)

 

[Brian van den Broek]

Hi all,

warning: off topic nitpicking below!

Jeremy Bowers said unto the world upon 2004-10-30 13:29:

Well, you can, sort of. You end up with the integers, obviously, and the
result has a rather striking resemblance to the modern foundations of
number theory, in which there is only one number, 0, and the "increment"
function which returns a number one larger. If you want three, it is
expressed increment(increment(increment(0))), which is rather similar to
the base-1 number "111".

I take it you didn't mean 0 was the only number, but rather the only
primitive number. (Alternatively " '0' is the only individual constant"
in the cant I prefer.)

I am also surprised to see "increment" -- I come to that material with
working in Philosophy of Mathematics and Logic, but almost every
presentation I have ever seen uses "successor". (I'm going off of
philosophical and mathematical logic presentations.)

I do so wish that terminology is the whole area would just stabilize
already!

Zero in this system would probably be a null string, making increment this:

def increment(number):
return "1" + number

(And abracadabra, I'm back on topic for the newsgroup, albeit tenuously )

Some people say base 2 is the most natural base in the universe. But you
can certainly make a claim for base 1, based on its correspondence to
number theory, from which we build the rest of math. (Most people never
dig this deep; it was one of my favorite classes in Comp. Sci., though,
and we're probably the only people other than mathematicians to offer the
course.)

I've never taken a single comp. sci. course, so I will both claim and
commit disciplinary bias: serious undergrad logic/foundations of maths
courses do happen in Philosophy, too

On the other hand, I'm a bit surprised that these things get taught in
comp. sci. This past summer when teaching Intro to Logic, I encountered
at least one fourth-year comp. sci. student who had no idea what an
axiomatic system was :-|

print "We now return you to your usual programing"

Best to all,

Brian vdB

 

[Jeremy Bowers]

I take it you didn't mean 0 was the only number, but rather the only
primitive number. (Alternatively " '0' is the only individual constant"
in the cant I prefer.)

*shrug* Can't say I get worked up over the difference there. Regardless,
you "can't" write "3". (Of course you can define it, but that's true of
everything.)

I am also surprised to see "increment" -- I come to that material with
working in Philosophy of Mathematics and Logic, but almost every
presentation I have ever seen uses "successor". (I'm going off of
philosophical and mathematical logic presentations.)

Yeah, that would be right. Couldn't recall the exact name.

I've never taken a single comp. sci. course, so I will both claim and
commit disciplinary bias: serious undergrad logic/foundations of maths
courses do happen in Philosophy, too

Gonna nit pick myself here: "Most people". I think adding Philosophers and
dilettantes and the rare electrical engineer isn't likely to change the
"most".

On the other hand, I'm a bit surprised that these things get taught in
comp. sci. This past summer when teaching Intro to Logic, I encountered
at least one fourth-year comp. sci. student who had no idea what an
axiomatic system was :-|

Graduate level. And many of the grads hated it. There is a chasm between
the average Comp. Sci. student and the average professor; it isn't so bad
at the grad level but it is still there. I'm not sure if it's worse than
most disciplines, but I am inclined to believe it is, since Comp Sci
typically can't really work out if it is math or engineering (wide
consensus is that while there are scientific aspects to it, it probably
shouldn't have it in the name), and there are, in my experience, fairly
clean divisions of each student and professor into one camp or another. I
was one of the exceedingly rare students who could do both quite well, and
freely translate between them.

 

[Bengt Richter]

]

Maybe something useful in this? Not very tested (and not terribly clear either ;-)

def number_in_base(x, N, digits):
... return x==0 and digits[0] or '-'[:x<0] + ''.join([d for d in iter(
... lambda qr=[abs(x),0]:qr[0] and (
... qr.__setslice__(0,2,divmod(qr[0],N)) or digits[qr[1]])
... , 0)][::-1])
...

Alternatively, a little more compactly (though I feel guilty about the -1 ;-):

def number_in_base(x, N=10, digits='0123456789ABCDEF'):

... return '-'[:x<0] + ''.join(list(iter(lambda qr=[abs(x),-1]: (qr[0] or qr[1]<0) and (
... qr.__setslice__(0,2,divmod(qr[0],N)) or digits[qr[1]]), False))[::-1])
...

Yet another, prefixing digits instead of joining reversed list:
... return '-'[:x<0]+reduce(lambda s,c:c+s, iter(lambda qr=[abs(x),-1]: (qr[0] or qr[1]<0)
... and (qr.__setslice__(0,2,divmod(qr[0],N)) or digits[qr[1]]), False))
...

My best shot so far (unless I goofed ;-):
... return '-'[:x<0]+''.join([digits[r] for x in [[abs(x)]]
... for x[0],r in iter(lambda:divmod(x[0], N), (0,0))][::-1]) or '0'
... '0'

Regards,
Bengt Richter

 

[Bengt Richter]

previous versions ...]

Silly last best shot put the quotient in an unneeded box. Sorry for all the
self-followups. I think I'll call this my best version (so far ;-):
... return '-'[:x<0]+''.join([digits[r] for q in [abs(x)]
... for q,r in iter(lambda:divmod(q, N), (0,0))][::-1]) or '0'
... '0'

Regards,
Bengt Richter

 

[Bengt Richter]

]
Goofed ;-/

def number_in_base(x, N=10, digits='0123456789ABCDEF'):
return '-'[:x<0]+''.join([digits[r] for q in [abs(x)]
for q,r in iter(lambda:divmod(q, N), (0,0))][::-1]) or digits[0]

(Shouldn't have hardwired '0' in place of digits[0])

It must be time to eat ... sorry.

Regards,
Bengt Richter

 

[Andrea Griffini]

Hi all,

warning: off topic nitpicking below!

Jeremy Bowers said unto the world upon 2004-10-30 13:29:

I take it you didn't mean 0 was the only number, but rather the only
primitive number. (Alternatively " '0' is the only individual constant"
in the cant I prefer.)

I am also surprised to see "increment" -- I come to that material with
working in Philosophy of Mathematics and Logic, but almost every
presentation I have ever seen uses "successor". (I'm going off of
philosophical and mathematical logic presentations.)

Also the representation used in that context is normally
"0,s0,ss0" or a similar one; anyway using TWO symbols.

In math, or anywhere you need precision, it's important
to weight the words; I said "positional" and normally the
unary counting method is not considered "positional".
There are a lot of methods for representing numbers, both
historically used (roman, for example) or just theorically
possible. When the word "base" is used the assumption is a
positional system; and 1 cannot be used as base in a
positional system. More to the point the objection that
the code that Alex wrote didn't handle "unary" counting
is IMO quite pointless as that counting system is not
more related to the positional than the ancient roman
counting system.

Of course anyone can give the the words whatever meaning,
it just gets harder to communicate.

Also, if ones really wants to support another different
number representation system after a generic positional
I would prefer the roman one, that's still used nowdays.

Andrea

 

[Bengt Richter]

I hesitate a bit to post this, but... on the Italian Python NG, somebody
was asking whether there was any way to convert an integer number x into
a string which represents it in an arbitrary base N (given a sequence
with a len of N that gives the digits to use) as "a single expression".

I haven't found a really general way, much less a clear one, but, the
best I have so far is...:

def number_in_base(x, N, digits, maxlen=99):
return '-'[x>=0:] + (
(x and ''.join([digits[k%N] for i in range(maxlen)
for k in [abs(x)//N**i] if k>0])[::-1]
) or digits[0])

Besides the lack of clarity, the obvious defect of this approach is that
darned 'maxlen' parameter -- but then, since I can have only a 'for',
not a 'while', in a list comprehension or generator expression, and I
don't think recursion qualifies as 'a single expression'...:-(

Anyway, improvements and suggestions welcome, thanks!

Not sure if I got filtered out replying to myself, what with an accidental dupe
and all the incremental changes and corrections ;-/ Anyway, I guess you could say
there's a "while" implicit in iter(f, sentinel) that you _can_ do within
a list comprehension ;-)

To sum up, my final version (hope it doesn't still have a bug ;-) was:

def number_in_base(x, N=10, digits='0123456789ABCDEF'):
return '-'[:x<0]+''.join([digits[r] for q in [abs(x)]
for q,r in iter(lambda:divmod(q, N), (0,0))][::-1]) or digits[0]

BTW, will anything that works in a list comprehension work in a generator expression
(assuming one does not depend on the generator expression having leftover outside
side effect bindings like the LC version)?

Regards,
Bengt Richter

 

[Alex Martelli]

Not sure if I got filtered out replying to myself, what with an accidental
dupe and all the incremental changes and corrections ;-/ Anyway, I guess
you could say there's a "while" implicit in iter(f, sentinel) that you
_can_ do within a list comprehension ;-)

Yep, excellent suggestion, tx. I went with the logarithm suggestion,
but in other cases the two-arguments iter could surely be the best way
to hide a 'while callable() != sentinel:' in a list comprehension!-)


Alex

 

[Dan Bishop]

range(maxlen) can be replaced with range(int(math.log(x) / math.log(N)) + 1).

Log accepts the base as second argument.

def number_in_base(x, N=10, digits="0123456789ABCDEF"):
return '-'[x>=0:]+"".join(
[digits[abs(x)/N**i%N]
for i in xrange(1+int(math.log(abs(x)+1,N)))
if N**i<=abs(x)][::-1]) or digits[0]

Also, and perhaps you are already aware, number_in_base(x, 1, '0') doesn't produce the correct output with the above algorithm, although I believe it will if you switch to using math.log().

It doesn't handle roman numerals either...

That's easy enough to implement ;-)

roman = lambda n: 'M' * (n // 1000) + ('', 'C', 'C', 'CCC', 'CD', 'D',
'DC', 'DCC', 'DCCC', 'CM')[n // 100 % 10] + ('', 'X', 'XX', 'XXX',
'XL', 'L', 'LX', 'LXX', 'LXXX', 'XC')[n // 10 % 10] + ('', 'I', 'II',
'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX')[n % 10]

I'm sure there's a shorter way, though.

 

[Steven Bethard]

BTW, will anything that works in a list comprehension work in a generator
expression (assuming one does not depend on the generator expression having
leftover outside side effect bindings like the LC version)?

Well, I'm not confident enough to say *anything* (though I've used them freely
in my code since 2.4a1 was released and have never had any problems) but they
seem to work for this problem:
.... return '-'[:n<0]+''.join(reversed(list(
.... digits[r]
.... for q in [abs(n)]
.... for q, r in iter(lambda: divmod(q, b), (0, 0))))) or digits[0]
.... '1100100'

Of course, you don't really gain anything by doing this with a generator
expression since you have to reverse the list.

In Python 3000, the list(genexp) syntax will be exactly equivalent to a list
comprehension[1], at which point, it won't matter.

Steve

[1] http://www.python.org/peps/pep-3000.html#core-language

 

[Andrea Griffini]

roman = lambda n: 'M' * (n // 1000) + ('', 'C', 'C', 'CCC', 'CD', 'D',
'DC', 'DCC', 'DCCC', 'CM')[n // 100 % 10] + ('', 'X', 'XX', 'XXX',
'XL', 'L', 'LX', 'LXX', 'LXXX', 'XC')[n // 10 % 10] + ('', 'I', 'II',
'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX')[n % 10]

I'm sure there's a shorter way, though.

This is a bit shorter ...

roman = lambda x: "".join(["".join(map(lambda c: "IVXLCDM"[ord(c) -
ord("A")+2*N], "/A/AA/AAA/AB/B/BA/BAA/BAAA/AC".split("/")[x//10**N %
10])) for N in (3, 2, 1, 0)])

Andrea

 

[Andrea Griffini]

This is a bit shorter ...

roman = lambda x: "".join(["".join(map(lambda c: "IVXLCDM"[ord(c) -
ord("A")+2*N], "/A/AA/AAA/AB/B/BA/BAA/BAAA/AC".split("/")[x//10**N %
10])) for N in (3, 2, 1, 0)])

No idea why I initially thougt about using ASCII codes... this
is simpler and shorter...

roman = lambda x: "".join(["".join(map(lambda c: "IVXLCDM"[int(c)
+2*N],"/0/00/000/01/1/10/100/1000/02".split("/")[x//10**N % 10]))
for N in (3, 2, 1, 0)])

Andrea