[Numpy-discussion] A bit long, but would appreciate anyone's help, if time permits!

Colin J. Williams cjw at sympatico.ca
Sat Jul 24 07:18:04 CDT 2004


Hee-Seng Kye wrote:

> Hi.  Like my previous post, my question is not directly related to Numpy, 

True, but numarray can be of help.

> but I couldn't help posting it since many people here deal with 
> numbers.  I have a question that requires a bit of explanation.  I 
> would highly appreciate it if anyone could read this and offer any 
> suggestions, whenever time permits.
>
> I'm trying to write a program that 1) gives all possible rotations of 
> an ordered list, 2) chooses the ordering that has the smallest 
> difference from first to last element of the rotation, and 3) 
> continues to compare the difference from first to second-to-last 
> element, and so on, if there was a tie in step 2.
>
> The following is the output of a function I wrote.  The first 6 lines 
> are all possible rotations of [0,1,3,6,7,10], and this takes care of 
> step 1 mentioned above.  The last line provides the differences (mod 
> 12).  If the last line were denoted as r, r[0] lists the differences 
> from first to last element of each rotation (p0 through p5), r[1] the 
> differences from first to second-to-last element, and so on.
>
> >>> from normal import normal
> >>> normal([0,1,3,6,7,10])
> [0, 1, 3, 6, 7, 10]    #p0
> [1, 3, 6, 7, 10, 0]    #p1
> [3, 6, 7, 10, 0, 1]    #p2
> [6, 7, 10, 0, 1, 3]    #p3
> [7, 10, 0, 1, 3, 6]    #p4
> [10, 0, 1, 3, 6, 7]    #p5
>
> [[10, 11, 10, 9, 11, 9], [7, 9, 9, 7, 8, 8], [6, 6, 7, 6, 6, 5], [3, 
> 5, 4, 4, 5, 3], [1, 2, 3, 1, 3, 2]]     #r
>
> Here is my question.  I'm having trouble realizing step 2 (and 3, if 
> necessary).  In the above case, the smallest number in r[0] is 9, 
> which is present in both r[0][3] and r[0][5].  This means that p3 and 
> p5 and only p3 and p5 need to be further compared.  r[1][3] is 7, and 
> r[1][5] is 8, so the comparison ends here, and the final result I'm 
> looking for is p3, [6,7,10,0,1,3] (the final 'n' value for 'pn' 
> corresponds to the final 'y' value for 'r[x][y]').
>
> How would I find the smallest values of a list r[0], take only those 
> values (r[0][3] and r[0][5]) for further comparison (r[1][3] and 
> r[1][5]), and finally print a p3?
>
> Thanks again for reading this.  If there is anything unclear, please 
> let me know.
>
> Best,
> Kye
>
> My code begins here: 

[snip]
The following reproduces your result, but I'm not sure that it does what 
you want to do.

Best wishes.

Colin W.

# Kye.py
#normal.py
def normal(s):
    s.sort()
    r = []
    q = []
    v = []

    for x in range(0, len(s)):
        k = s[x:]+s[0:x]
        r.append(k)

    for y in range(0, len(s)):
        print r[y], '\t'
        d = []
        for yy in range(len(s)-1, 0, -1):
            w = (r[y][yy]-r[y][0])%12
            d.append(w)
        q.append(d)

    for z in range(0, len(s)-1):
        d = []
        for zz in range(0, len(s)):
            w = q[zz][z]
            d.append(w)
        v.append(d)
    print '\n', v

def findMinima(i, lst):
  global diff
  print 'lst:', lst, 'i:', i
  res= []
  dataRow= diff[i].take(lst)
  fnd= dataRow.argmin()
  val= val0= dataRow[fnd]
  while val == val0:
    fndRes= lst[fnd]                  # This will become the result iff 
no dupicate found
    res.append(fnd)
    dataRow[fnd]= 100
    fnd= dataRow.argmin()
    val0= dataRow[fnd]
  if len(res) == 1:
    return fndRes
  else:
    ret= findMinima(i-1, res) 
    return ret

def normal1(s):
  import numarray.numarraycore as _num
  import numarray.numerictypes as _nt
  global diff
  s= _num.array(s)
  s.sort()
  rl= len(s)
  r= _num.zeros(shape= (rl, rl), type= _nt.Int)
  for i in range(rl):
    r[i, 0:rl-i]= s[i:]
    if i:
      r[i, rl-i:]= s[0:i]
  subtr= r[0].repeat(5, 1).resize(6, 5)
  subtr.transpose()
  neg= r[1:] < subtr
  diff= r[1:]-subtr + 12 * neg
 
  return 'The selectect rotation is:', r[findMinima(diff._shape[0]-1, 
range(diff._shape[1]))]

if __name__ == '__main__':
  print normal1([0,1,3,6,7,10])


>
> #normal.py
> def normal(s):
>     s.sort()
>     r = []
>     q = []
>     v = []
>
>     for x in range(0, len(s)):
>         k = s[x:]+s[0:x]
>         r.append(k)
>
>     for y in range(0, len(s)):
>         print r[y], '\t'
>         d = []
>         for yy in range(len(s)-1, 0, -1):
>             w = (r[y][yy]-r[y][0])%12
>             d.append(w)
>         q.append(d)
>
>     for z in range(0, len(s)-1):
>         d = []
>         for zz in range(0, len(s)):
>             w = q[zz][z]
>             d.append(w)
>         v.append(d)
>     print '\n', v
>
>
>
> -------------------------------------------------------
> This SF.Net email is sponsored by BEA Weblogic Workshop
> FREE Java Enterprise J2EE developer tools!
> Get your free copy of BEA WebLogic Workshop 8.1 today.
> http://ads.osdn.com/?ad_id=4721&alloc_id=10040&op=click
> _______________________________________________
> Numpy-discussion mailing list
> Numpy-discussion at lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/numpy-discussion
>





More information about the Numpy-discussion mailing list