help how to sort a list in order of 'n' in python without usinginbuilt functions??

[Carlos Nepomuceno]

lol http://search.dilbert.com/comic/Random Nine

----------------------------------------

Date: Sat, 25 May 2013 19:14:57 +1000
Subject: Re: help how to sort a list in order of 'n' in python without using inbuilt functions??
From: (e-mail address removed)
To: (e-mail address removed)

----------------------------------------

Date: Sat, 25 May 2013 19:01:09 +1000
Subject: Re: help how to sort a list in order of 'n' in python without using inbuilt functions??
From: (e-mail address removed)
To: (e-mail address removed) [...]
Very good. You are now in a position to get past the limitations of a
restricted-environment eval/exec. Avoiding builtins is actually a fun
skill to hone.

ChrisA

I'm glad he didn't ask for a Pseudo-RNG without built-ins!

def random_number():
return 7

ChrisA

 

[Mark Lawrence]

lol

def absolute(x):
return x if x>0 else -x

def reach(x):
y=[]
z=0
while z<x:
y.append(z)
z+=1
return y

In my book this is another fail as lists are inbuilt (yuck!) and so is
the add function that'll be called for z+=1.

 

[Roy Smith]

Note:
the list only contains 0's,1's,2's
need to sort them in order of 'n'

What do you mean by "need to sort them in order of 'n'". Are you saying
that you need to sort them into numerical order? Or that you need to
running time of the algorithm to be O(n)?

I'm assuming the later, in which case this is starting to sound like a
classic interview question.

Assuming you can accept an unstable sort, there's an easy solution. I'm
not aware of any solution if you require a stable sort. Perhaps that's
enough of a hint?

 

[Roy Smith]

ya steven i had done the similar logic but thats not satisfying my professor
he had given the following constrains
1. No in-built functions should be used
2. we are expecting a O(n) solution
3. Don't use count method

A couple of points here:

1) In general, people on mailing lists are not into doing homework
problems for other people.

2) If you're going to bring us a homework problem, at least describe the
whole problem up front. It really doesn't help to dribble out new
requirements one at a time.

3) (e-mail address removed) already posted a pointer to the wikipedia
article describing the required algorithm in detail.

4) I don't know what "no built-in functions should be used" means. I
assume it means, "don't call sort()"? If you can't even call
int.__lt__(), it's going to be really hard to do this.

 

[Dave Angel]

A couple of points here:

1) In general, people on mailing lists are not into doing homework
problems for other people.

2) If you're going to bring us a homework problem, at least describe the
whole problem up front. It really doesn't help to dribble out new
requirements one at a time.

3) (e-mail address removed) already posted a pointer to the wikipedia
article describing the required algorithm in detail.

4) I don't know what "no built-in functions should be used" means. I
assume it means, "don't call sort()"? If you can't even call
int.__lt__(), it's going to be really hard to do this.

The OP has already admitted that he didn't want a sort at all. He wants
to COUNT the items, not sort them. So nothing in his orginal post
relates to the real homework assignment.

 

[Steven D'Aprano]

def random_number():
return 7

I call shenanigans! That value isn't generated randomly, you just made it
up! I rolled a die *hundreds* of times and not once did it come up seven!

 

[Steven D'Aprano]

ya steven i had done the similar logic but thats not satisfying my
professor he had given the following constrains
1. No in-built functions should be used

The above does not use any built-in functions.

2. we are expecting a O(n) solution

The above is O(n).

3. Don't use count method

The above does not use the count method.

 

[Fábio Santos]

On 25 May 2013 15:35, "Steven D'Aprano" <

I call shenanigans! That value isn't generated randomly, you just made it
up! I rolled a die *hundreds* of times and not once did it come up seven!

Try flipping a coin. I flipped one a couple of times and got the seventh
face once.

 

[Jussi Piitulainen]

What do you mean by "need to sort them in order of 'n'". Are you
saying that you need to sort them into numerical order? Or that you
need to running time of the algorithm to be O(n)?

I'm assuming the later, in which case this is starting to sound like
a classic interview question.

Assuming you can accept an unstable sort, there's an easy solution.
I'm not aware of any solution if you require a stable sort. Perhaps
that's enough of a hint?

Surely it's assumed that each element of the input list can be
classified as 0, 1, or 2 in O(1) time. If O(n) auxiliary space can be
allocated in O(n) time, just put the 0's in their own list in the
order they are encountered, 1's in their own list in the order they
are encountered, 2's in their own list in the order they are
encountered, then put the 0's back into the input list in the order
they are encountered in their auxiliary list, followed by the 1's,
followed by the 2's. Stable and O(n), no?

Even ( [ x for x in input if x.key == 0 ] +
[ x for x in input if x.key == 1 ] +
[ x for x in input if x.key == 2 ] ).
I suppose a list comprehension is not technically a function any more
than a loop is.

(Neither stability nor O(1) space has been required yet, I think.)

 

[Mark Lawrence]

I call shenanigans! That value isn't generated randomly, you just made it
up! I rolled a die *hundreds* of times and not once did it come up seven!

Lies, damn lies and statistics?

 

[Chris Angelico]

I call shenanigans! That value isn't generated randomly, you just made it
up! I rolled a die *hundreds* of times and not once did it come up seven!

You've obviously never used a REAL set of dice. Now, I have here with
me a set used for maths drill (to be entirely accurate, what I have
here is the company's stock of them, so there are multiples of each of
these - anyone need to buy dice?) with everything except the classic 1
through 6 that everyone knows:

* Six sides, faces marked 7 through 12
* Six sides, faces marked "+x-\xf7+" and a "wild" marker (yes, two of +)
* Ten sides, numbered 0 through 9
* Eight sides, numbered 1 through 8
* Twelve sides, as above
* Twenty sides, as above

Now, tabletop roleplayers will recognize the latter four as the ones
notated as d10, d8, d12, and d20, but these are NOT for gameplay, they
are for serious educational purposes! Honest!

Anyway, all of those can roll a 7... well, one of them has to roll a
\xf7, but close enough right? Plus, if you roll 2d6 (that is, two
regular six-sided dice and add them up), 7 is statistically the most
likely number to come up with. Therefore it IS random.

ChrisA

 

[Carlos Nepomuceno]

----------------------------------------

To: (e-mail address removed)
From: (e-mail address removed)
Subject: Re: help how to sort a list in order of 'n' in python without using inbuilt functions??
Date: Sat, 25 May 2013 13:01:06 +0100 [...]
In my book this is another fail as lists are inbuilt (yuck!) and so is
the add function that'll be called for z+=1.

Indeed! It's a joke Mark! lol

 

[Carlos Nepomuceno]

----------------------------------------

From: (e-mail address removed)
Subject: Re: help how to sort a list in order of 'n' in python without using inbuilt functions??
Date: Sat, 25 May 2013 14:28:33 +0000
To: (e-mail address removed)



I call shenanigans! That value isn't generated randomly, you just made it
up! I rolled a die *hundreds* of times and not once did it come up seven!

lol It worked fine on my d8! lol

 

[Carlos Nepomuceno]

----------------------------------------

Date: Sun, 26 May 2013 01:41:58 +1000
Subject: Re: help how to sort a list in order of 'n' in python without using inbuilt functions??
From: (e-mail address removed)
To: (e-mail address removed)



You've obviously never used a REAL set of dice. Now, I have here with
me a set used for maths drill (to be entirely accurate, what I have
here is the company's stock of them, so there are multiples of each of
these - anyone need to buy dice?) with everything except the classic 1
through 6 that everyone knows:

* Six sides, faces marked 7 through 12
* Six sides, faces marked "+x-\xf7+" and a "wild" marker (yes, two of+)
* Ten sides, numbered 0 through 9
* Eight sides, numbered 1 through 8
* Twelve sides, as above
* Twenty sides, as above

Now, tabletop roleplayers will recognize the latter four as the ones
notated as d10, d8, d12, and d20, but these are NOT for gameplay, they
are for serious educational purposes! Honest!

Anyway, all of those can roll a 7... well, one of them has to roll a
\xf7, but close enough right? Plus, if you roll 2d6 (that is, two
regular six-sided dice and add them up), 7 is statistically the most
likely number to come up with. Therefore it IS random.

ChrisA

def f(x):
    return x+1

or you can just go:

f(roll_d6())

 

[Chris Angelico]

def f(x):
return x+1

or you can just go:

f(roll_d6())

Hmm. Interesting. So now we have a question: Does adding 1 to a random
number make it less random? It adds determinism to the number; can a
number be more deterministic while still no less random?

Ah! I know. The answer comes from common sense:

a = random() # a is definitely a random number
a -= random() # a is no longer random, we subtracted all the randomness from it

Of course, since number-number => number, a is still a number. And so
we can conclude that adding 1 to a random dice roll does indeed leave
all the randomness still in it. But wait! That means we can do
better!!

a = random() # a is a random number
a *= 5 # a is clearly five times as random now!

ChrisA

 

[Carlos Nepomuceno]

----------------------------------------

Date: Sun, 26 May 2013 03:23:44 +1000
Subject: Re: help how to sort a list in order of 'n' in python without using inbuilt functions??
From: (e-mail address removed)
To: (e-mail address removed)



Hmm. Interesting. So now we have a question: Does adding 1 to a random
number make it less random? It adds determinism to the number; can a
number be more deterministic while still no less random?

Ah! I know. The answer comes from common sense:

a = random() # a is definitely a random number
a -= random() # a is no longer random, we subtracted all the randomness from it

Of course, since number-number => number, a is still a number. And so
we can conclude that adding 1 to a random dice roll does indeed leave
all the randomness still in it. But wait! That means we can do
better!!

a = random() # a is a random number
a *= 5 # a is clearly five times as random now!

ChrisA

It depends if the result (any operation) is in the required range.

For example: "int(random.random()+1)" it's not random at all!

But "int(random.random()*1000)" my look random if it fits your needs.

 

[Carlos Nepomuceno]

----------------------------------------

Date: Fri, 24 May 2013 23:05:17 -0700
Subject: Re: help how to sort a list in order of 'n' in python without using inbuilt functions??
From: (e-mail address removed) [...]

ya steven i had done the similar logic but thats not satisfying my professor
he had given the following constrains
1. No in-built functions should be used
2. we are expecting a O(n) solution
3. Don't use count method

PS: If you find something faster please let me know!

 

[Steven D'Aprano]

You've obviously never used a REAL set of dice.

You're right, all my dice are eight-sided and complex:

1+0i
1+1i
1-1i
-1+0i
-1+1i
-1-1i





But seriously, I have various D&D style gaming dice, d4, d6, d8, d12, d20
and d30. But I thought the opportunity for a joke was more important than
pedantic correctness

Now, I have here with me
a set used for maths drill (to be entirely accurate, what I have here is
the company's stock of them, so there are multiples of each of these -
anyone need to buy dice?)

Are you serious? What's the cost, posted to Melbourne?

with everything except the classic 1 through 6 that everyone knows:

* Six sides, faces marked 7 through 12
* Six sides, faces marked "+x-\xf7+" and a "wild" marker
(yes, two of +)

Oh, you mean ÷ (division sign)! Why didn't you say so?

And another thing, shame on you, you mean × not x. It's easy to find too:

py> from unicodedata import lookup
py> print(lookup("MULTIPLICATION SIGN"))
×

* Ten sides, numbered 0 through 9
* Eight sides, numbered 1 through 8
* Twelve sides, as above
* Twenty sides, as above

Now, tabletop roleplayers will recognize the latter four as the ones
notated as d10, d8, d12, and d20, but these are NOT for gameplay, they
are for serious educational purposes! Honest!

Anyway, all of those can roll a 7... well, one of them has to roll a
\xf7, but close enough right?

I don't think so...

Plus, if you roll 2d6 (that is, two
regular six-sided dice and add them up), 7 is statistically the most
likely number to come up with. Therefore it IS random.

Yes, but if you subtract them the most common is 0, if you multiply the
most common are 6 or 12, and if you divide the most common is 1. If you
decide on the operation randomly, using the +-×÷+ die above (ignoring
wildcards), the most common result is 6. The probability of getting a 7
is just 1/15.

from collections import Counter
from operator import add, sub, mul, truediv as div
ops = (add, sub, mul, div, add)
Counter(op(i, j) for op in ops for i in range(1, 7) for j in range(1, 7))

 

[Steven D'Aprano]

Does adding 1 to a random
number make it less random? It adds determinism to the number; can a
number be more deterministic while still no less random?

Ah! I know. The answer comes from common sense:

[snip spurious answer]

I know you're being funny, but in fact adding a constant to a random
variable still leaves it equally random. Adding, multiplying, dividing or
subtracting a constant from a random variable X just shifts the possible
values X can take, it doesn't change the shape of the distribution.
However, adding two random variables X and Y does change the
distribution. In fact, a very cheap way of simulating an almost normally
distributed random variable is to add up a whole lot of uniformly
distributed random variables. Adding up 12 calls to random.random(), and
subtracting 6, gives you a close approximation to a Gaussian random
variable with mean 0 and standard deviation 1.

 

[Chris Angelico]

You're right, all my dice are eight-sided and complex:

1+0i
1+1i
1-1i
-1+0i
-1+1i
-1-1i

Now THAT is a dice of win!

Are you serious? What's the cost, posted to Melbourne?

$1 each, postage probably $5 for any number. Or there may even be
option to pick up / hand deliver, depending on where in Melb you are.

http://www.kepl.com.au/ - company's winding down, but we still have stock.

Oh, you mean ÷ (division sign)! Why didn't you say so?

I tend to stick to ASCII in these posts.

And another thing, shame on you, you mean × not x. It's easy to find too:

py> from unicodedata import lookup
py> print(lookup("MULTIPLICATION SIGN"))
×

I'm aware of that, but see above, I stick to ASCII where possible. The
faces would be better represented with some of the other digits (the
bolded ones, perhaps), but I used the ASCII digits.

Yes, but if you subtract them the most common is 0, if you multiply the
most common are 6 or 12, and if you divide the most common is 1. If you
decide on the operation randomly, using the +-×÷+ die above (ignoring
wildcards), the most common result is 6. The probability of getting a 7
is just 1/15.

from collections import Counter
from operator import add, sub, mul, truediv as div
ops = (add, sub, mul, div, add)
Counter(op(i, j) for op in ops for i in range(1, 7) for j in range(1, 7))

LOL! I never thought to go THAT far into the analysis..... Nice one!

ChrisA