home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / theory / 2729 < prev    next >
Encoding:
Text File  |  1992-12-20  |  1.5 KB  |  46 lines
  1. Newsgroups: comp.theory,cs.bboard,cs.research
  2. Path: sparky!uunet!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!ira.uka.de!sol.ctr.columbia.edu!news.cs.columbia.edu!duanyang
  3. From: duanyang@cs.columbia.edu (Duanyang Guo)
  4. Subject: a problem
  5. Message-ID: <BzFt63.DEz@cs.columbia.edu>
  6. Sender: news@cs.columbia.edu (The Daily News)
  7. Organization: Columbia University Department of Computer Science
  8. Date: Fri, 18 Dec 1992 04:15:38 GMT
  9. Lines: 35
  10.  
  11. I met a problem recently. 
  12.  
  13. given an integer vector (x1, x2, ..., xn), could you find 
  14. an efficient ALGORITHM to get minimum M and  an integer vector
  15. (y1, y2, ..., yn) so that the following holds: 
  16. (1). (y1, ..., yn) is a PERMUTATION VECTOR from [0, M-1]: 
  17.      yi does not equal to yj, if i does not equal to j; 
  18.      all yi belongs to [0,M-1];
  19. (2)  ((x1+y1) mod M, (x2+y2) mod M, ..., (xn+yn) mod M) is also a 
  20.      PERMUTATION VECTOR from [0, M-1] as defined above. 
  21.  
  22. -----------------------
  23.  
  24. because (x1, x2, ..., xn) is equivalent to (x1+1, x2+2, ..., xn+n) 
  25. in term of finding M and solution, we can assume xi>=0 for 1<=i<=n.
  26.  
  27. I can get some kind of upper-bound about M, such as 
  28. n+max{xi}-min{xi}. 
  29.  
  30. A follow-up question is, for multiple integer vectors, find out
  31. common M and vector Y which has the same property. This question 
  32. is most interesting to me. 
  33.  
  34. could anyone point some references about it? it looks like so 
  35. plain! any results in PERMUTATION GROUP can help? 
  36.  
  37. I guess it is NP-complete. Any NP-complete problem in the similiar
  38. manner? 
  39.  
  40.  
  41.  
  42.  
  43. -- 
  44. Duanyang Guo    Computer Science Department, Columbia University
  45.  
  46.