python program to find maximal in 2d array

Question

I am trying to write program that print maximal points of the input but it is not giving correct output.

Definition of maximal- Given a set of points P = {p1,p2,...,pn} in 2-space, each represented by its x and y integer coordinates, output the set of the maximal points of P, that is, those points pi, such that pi is not dominated by any other point of P (not both coordinate are dominated)

Example input:

p1(5,7),p2(47,84),p3(89,4),(46,54),(100,1)

Example outut:

p2(47,84),(89,4),(100,1)

The idea of my program is to first sort the point according to x axis then compare the y coordinate.

a=[[5,7],[47,84],[89,4][46,54],[100,1]]

#sort according to x axis
mylist.sort(key=lambda x: x[0])

#compare y coordinate of i to all element right to i
for i in reversed(range(len(a)):
   j=i+1
   while (j<len(a)): 
        if(mylist[i][1]>mylist[j][1]):
             j+=1
   if(j==len(a)):
          print(mylist[i])

Your definition of maximal is completely unclear to me. What do you mean by "dominated" and "not both coordinate are dominated"? — Rory Daulton
– Rory Daulton, Commented May 26, 2018 at 12:02
why do you set up 'a' like this? you generate an array of arrays instead of passing just the vector-tuple as you have in the example input. So it would be like this a =[(5,7),(47,84)] and so on or even better just pass it the points a=[p1,p2,p3] and acess them via a[index_of_a][index_of_p]. egg a[0][0] ... to find out more read about tuples. — The Fool
– The Fool, Commented May 26, 2018 at 12:08
@TheFool Initially I am trying to solve with simple 2d array not using set of points. — Pritesh Singh
– Pritesh Singh, Commented May 26, 2018 at 12:15

simonz · Accepted Answer · 2018-05-26 12:09:50Z

4

That's really not how you'd do that in Python. Use language elements that help you express what's going on, that way the code gets more understandable and, as a bonus, more concise. You want to find all elements of a for which no other element of a is greater in both coordinates:

a=[[5,7],[47,84],[89,4],[46,54],[100,1]]
for point in a:
  if not any(map(lambda p: p[0] > point[0] and p[1] > point[1], a)):
    print(point)

You could also use a list comprehension instead of map, which might be a bit more efficient:

a=[[5,7],[47,84],[89,4],[46,54],[100,1]]
for point in a:
  if not any([p[0] > point[0] and p[1] > point[1] for p in a]):
    print(point)

edited May 26, 2018 at 12:09

answered May 26, 2018 at 12:03

simonz

1916 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

python program to find maximal in 2d array

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related