[Tutor] Re: putting a short list of integers into a (specific)
compact form
kevin parks
kp8 at mac.com
Sun Oct 12 05:46:28 EDT 2003
> 1. Initially, all duplicate elements should be eliminated and the
> elements should
> be written so that they are ascending in order (all integers are
> mapped mod 12).
I should say that i got this part (#1) (see below) and step 4 and my
optional little step 5 is probably pretty
easy. It is the step 2 and 3 parts that i can't get my head round
coding. I guess what i want is to generate
each list (as i have done below) and compare the intervals between each
list element and between the
two list and i am 100000% sure there is some elegant way to do this in
Python, it seems the kind of thing
python was born to handle, with something sexy like bisect or list
comprehension... hmm.... i'll keep thinking
and hope that someone will lend a hand.... maybe once the list is made
then a list of list can be built like:
[0,4,8,9,11]
[4,8,9,11,0]
[8,9,11,0,4]
[9,11,0,4,8]
[11,0,4,8,9]
and each interval can be taken and stored in a list? Hmmm... I just
don't know. I guess that i am just reaching
so that i don't look to silly on the tutor list, but i really don't
know so i should just shut up and see what folks
propose.
-kp--
--
--
#!/usr/bin/env python
import sys
import random
def unique(seq):
try: # attempt fast algorithm
d = {}
for x in seq: d[x] = 0
return d.keys()
except TypeError: # have an unhashable object, use slow algorithm
ret = []
app = ret.append
for x in seq:
if x not in ret: app(x)
return ret
def test():
random.seed(720)
x = range(0, 12, 1)
print x; print
random.shuffle(x)
print x
y= range(0, 12, 1)
print y; print
random.shuffle(y)
print y; print
x.extend(y)
print x; print
x.sort()
print x; print
z=unique(x)
print z; print
if __name__ == "__main__":
test()
> 2. Since there will be as many ways to order them as there are
> elements in
> the list, we want to choose the ordering that has the
> smallest interval from lowest element to highest one.
>
> 3. If there is still a tie under rule #2 we want to pick the list that
> is
> most packed to the left (by finding the intervals between the first
> element
> and the second to last element and comparing the intervals of each
> list in
> the tie, if there is still a tie, compare the intervals between
> first element
> in the lists and the third to last, etc.)
>
> 4. If this still results in a tie for each element, for example in the
> case of:
> [10,1,6] , [1,6,10] , and [6,10,1] we choose [1,6,10], since
> it's first element is 1.
>
> (finally, and optionally, i'll likely need to transpose the answer so
> that
> it starts on 0)
>
> So in a set with the following five possible orderings (here already
> sorted low to high
> and proceeding systematically (again %12)):
>
> [0,4,8,9,11]
> [4,8,9,11,0]
> [8,9,11,0,4]
> [9,11,0,4,8]
> [11,0,4,8,9]
>
> So the interval between the first element and the last is
>
> [0,4,8,9,11] = 0-11 = 11
> [4,8,9,11,0] = 0-4 = 12-4 = 8
> [8,9,11,0,4] = 4-8 = 16 - 8 = 8
> [9,11,0,4,8] = 9-8 = 20-9 = 11
> [11,0,4,8,9] = 9-11 = 21-11 = 10
>
> Here end up with a tie between the second and third orderings above.
> So we go to
> rule #3: We compare the intervals btween the first and next to last
> elements:
>
> second ordering: 11-4 = 7
> third ordering: 0-8 = 4
>
> Since 4 is smaller than 7 we conclude the third ordering [8,9,11,0,4]
> is more packed to the left and
> what we want and there is no need for rule 4 in this case.
>
> I hope that i have stated the question clearly. I would appreciate any
> help folks could give on this. Frankly it is beyond
> what i can do at this point, but i would like to see how others
> approach this in the hopes that my code will work and that
> i might learn something.
>
> Best,
>
> kevin
>
>
> --^----------------------------------------
>
> kp8 @ mac . com
>
More information about the Tutor
mailing list