Closest-pair problem: Difference between revisions

{{task|Classic CS problems and programs}}

{{Wikipedia|Closest pair of points problem}}

*   [http://www.cs.iupui.edu/~xkzou/teaching/CS580/Divide-and-conquer-closestPair.ppt Closest pair (IUPUI)]

<br><br>

=={{header|360 Assembly}}==

CLOSEST CSECT

USING CLOSEST,R13 base register

PG DS CL80

YREGS

{{out}}

<pre>

[ 0.925092, 0.818220]

</pre>

=={{header|Ada}}==

Dimension independent, but has to be defined at procedure call time

 

closest.adb: (uses brute force algorithm)

with Ada.Text_IO;

 

Ada.Text_IO.Put_Line ("P2: " & Float'Image (Second_Points (2) (1)) & " " & Float'Image (Second_Points (2) (2)));

Ada.Text_IO.Put_Line ("Distance: " & Float'Image (Distance (Second_Points (1), Second_Points (2))));

 

{{out}}

P2: 9.25092E-01 8.18220E-01

Distance: 7.79101E-02</pre>

=={{header|AWK}}==

# syntax: GAWK -f CLOSEST-PAIR_PROBLEM.AWK

BEGIN {

exit(0)

}

{{out}}

<pre>

</pre>

 

To find the closest pair it is sufficient to compare the squared-distances,

it is not necessary to perform the square root for each pair!

FOR I% = 0 TO 9

DATA 0.293786, 0.691701

DATA 0.839186, 0.728260

{{out}}

<pre>Closest pair is 2 and 5 at distance 0.0779101913</pre>

=={{header|C}}==

See [[Closest-pair problem/C]]

 

=={{header|C++}}==

Author: Kevin Bacon

Date: 04/03/2014

print_point(answer.second.second);

return 0;

 

{{out}}

<pre>Min distance (brute): 6.95886 (932.735, 1002.7), (939.216, 1000.17)

Min distance (optimized): 6.95886 (932.735, 1002.7), (939.216, 1000.17)</pre>

=={{header|Clojure}}==

 

(defn distance [[x1 y1] [x2 y2]]

(let [dx (- x2 x1), dy (- y2 y1)]

{yS true} (group-by (fn [[px _]] (< (Math/abs (- xm px)) dmin)) yP)]

(combine yS [dmin pmin1 pmin2])))))

=={{header|Common Lisp}}==

 

Points are conses whose cars are x coördinates and whose cdrs are y coördinates. This version includes the optimizations given in the [http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html McGill description] of the algorithm.

 

(destructuring-bind (x1 . y1) p1

(destructuring-bind (x2 . y2) p2

(multiple-value-bind (pair distance)

(cp (sort (copy-list points) '< :key 'car))

=={{header|Crystal}}==

=={{header|D}}==

===Compact Versions===

std.random, std.traits, std.range, std.complex;

 

writeln("bruteForceClosestPair: ", points.bruteForceClosestPair);

writeln(" closestPair: ", points.closestPair);

{{out}}

<pre>[5+9i, 9+3i, 2+0i, 8+4i, 7+4i, 9+10i, 1+9i, 8+2i, 0+10i, 9+6i]

 

===Faster Brute-force Version===

std.traits;

 

writefln("Closest pair: Distance: %f p1, p2: %f, %f",

abs(pts[ij[0]] - pts[ij[1]]), pts[ij[0]], pts[ij[1]]);

{{out}}

<pre>Closest pair: Distance: 0.019212 p1, p2: 9.74223+119.419i, 9.72306+119.418i</pre>

About 0.12 seconds run-time for brute-force version 2 (10_000 points) with with LDC2 compiler.

 

=={{header|Elixir}}==

# brute-force algorithm:

def bruteForce([p0,p1|_] = points), do: bf_loop(points, {distance(p0, p1), {p0, p1}})

IO.inspect :timer.tc(fn -> Closest_pair.bruteForce(data2) end)

IO.puts "Recursive divide&conquer:"

 

{{out}}

=={{header|F Sharp|F#}}==

Brute force:

let closest_pairs (xys: Point []) =

let n = xys.Length

yield xys.[i], xys.[j] }

|> Seq.minBy (fun (p0, p1) -> (p1 - p0).LengthSquared)

For example:

closest_pairs

[|Point(0.0, 0.0); Point(1.0, 0.0); Point (2.0, 2.0)|]

gives:

(0,0, 1,0)

 

Divide And Conquer:

 

 

open System;

printfn "Closest Pair '%A'. Distance %f" closest (Length closest)

printfn "Took %d [ms]" takenMs

=={{header|Fantom}}==

 

(Based on the Ruby example.)

 

class Point

{

}

}

 

{{out}}

Time taken: 228ms

</pre>

=={{header|Fortran}}==

See [[Closest pair problem/Fortran]]

 

=={{header|Go}}==

'''Brute force'''

 

import (

}

return

'''O(n)'''

// http://www.cs.umd.edu/~samir/grant/cp.pdf

package main

}

return p1, p2

=={{header|Groovy}}==

Point class:

final Number x, y

Point(Number x = 0, Number y = 0) { this.x = x; this.y = y }

Number distance(Point that) { ((this.x - that.x)**2 + (this.y - that.y)**2)**0.5 }

String toString() { "{x:${x}, y:${y}}" }

 

Brute force solution. Incorporates X-only and Y-only pre-checks in two places to cut down on the square root calculations:

assert pointCol

List l = pointCol

}

answer

 

Elegant (divide-and-conquer reduction) solution. Incorporates X-only and Y-only pre-checks in two places (four if you count the inclusion of the brute force solution) to cut down on the square root calculations:

assert pointCol

List xList = (pointCol as List).sort { it.x }

}

answer

 

Benchmark/Test:

 

(1..4).each {

=========================================

"""

 

Results:

Speedup ratio (B/E): 26.3500255493

=========================================</pre>

=={{header|Haskell}}==

BF solution:

 

import System.Random (newStdGen, randomRs)

 

foldl1'' = foldl1'

{{out}}

([[0.8347201880148426,0.40774840545089647],[0.8348731214261784,0.4087113189531284]],9.749825850154334e-4)

=={{header|Icon}} and {{header|Unicon}}==

This is a brute force solution.

It combines reading the points with computing the closest pair seen so far.

 

procedure main()

procedure dSquared(p1,p2) # Compute the square of the distance

return (p2.x-p1.x)^2 + (p2.y-p1.y)^2 # (sufficient for closeness)

=={{header|J}}==

Solution of the simpler (brute-force) problem:

dist =: <@:vecl@:({: -"1 }:)\ NB. calculate all distances among vectors

minpair=: ({~ > {.@($ #: I.@,)@:= <./@;)dist NB. find one pair of the closest points

Examples of use:

0.654682 0.925557

0.409382 0.619391

|0.891663 0.888594|0.0779104|

|0.925092 0.81822| |

The program also works for higher dimensional vectors:

0.559164 0.482993 0.876 0.429769

0.217911 0.729463 0.97227 0.132175

|0.217911 0.729463 0.97227 0.132175|0.708555|

|0.316673 0.797519 0.745821 0.0598321| |

=={{header|Java}}==

 

 

'''Code:'''

 

public class ClosestPair

System.out.println("MISMATCH");

}

 

{{out}}

Brute force (1594 ms): (0.9246533850872104, 0.098709007587097)-(0.924591196030625, 0.09862206991823985) : 1.0689077146927108E-4

Divide and conquer (250 ms): (0.924591196030625, 0.09862206991823985)-(0.9246533850872104, 0.098709007587097) : 1.0689077146927108E-4</pre>

=={{header|JavaScript}}==

Using bruteforce algorithm, the ''bruteforceClosestPair'' method below expects an array of objects with x- and y-members set to numbers, and returns an object containing the members ''distance'' and ''points''.

 

var dx = Math.abs(p1.x - p2.x);

var dy = Math.abs(p1.y - p2.y);

};

}

 

divide-and-conquer method:

 

var Point = function(x, y) {

console.log(JSON.stringify(closestPair(Px, Py))); // {"distance":65.06919393998976,"pair":[{"x":37134,"y":1963},{"x":37181,"y":2008}]}

 

=={{header|jq}}==

{{works with|jq|1.4}}

 

'''Infrastructure''':

# Emit the first input that satisfied the condition

def until(cond; next):

# Euclidean 2d distance

def dist(x;y):

# P is an array of points, [x,y].

# Emit the solution in the form [dist, [P1, P2]]

| .[1]

end;

'''Example from the Mathematica section''':

[[0.748501, 4.09624],

[3.00302, 5.26164],

[1.45428, 0.087596] ];

 

{{Out}}

$jq -M -c -n -f closest_pair.jq

[0.0894096443343775,[[7.46489,4.6268],[7.46911,4.71611]]]

=={{header|Julia}}==

{{works with|Julia|0.6}}

Brute-force algorithm:

N = length(P)

if N < 2 return (Inf, ()) end

end

 

=={{header|Kotlin}}==

 

typealias Point = Pair<Double, Double>

println("Closest pair (optimized) is ${pair2.first} and ${pair2.second}, distance $dist2\n")

}

 

{{out}}

Closest pair (optimized) is (0.891663, 0.888594) and (0.925092, 0.81822), distance 0.07791019135517516

</pre>

=={{header|Liberty BASIC}}==

NB array terms can not be READ directly.

N =10

 

data 0.839186, 0.72826

 

Distance =0.77910191e-1 between ( 0.891663, 0.888594) and ( 0.925092, 0.81822)

=={{header|Maple}}==

 

local

end proc; #Recurse

 

 

> L := RandomTools:-Generate(list(list(float(range=0..1),2),512)):

> ClosestPair(L);

0.002576770304, [[0.4265584800, 0.7443097852], [0.4240649736, 0.7449595321]]

=={{header|Mathematica}} / {{header|Wolfram Language}}==

Block[{pos, dist = N[Outer[EuclideanDistance, data, data, 1]]},

pos = Position[dist, Min[DeleteCases[Flatten[dist], 0.]]];

 

9.52232}, {7.46911, 4.71611}, {5.7819, 2.69367}, {2.34709,

8.74782}, {2.87169, 5.97774}, {6.33101, 0.463131}, {7.46489,

4.6268}, {1.45428, 0.087596}}]

 

 

=={{header|MATLAB}}==

 

This solution is an almost direct translation of the above pseudo-code into MATLAB.

 

N = numel(xP);

end %for

end %if (N <= 3)

 

{{out}}

 

distance =

pair =

 

=={{header|Microsoft Small Basic}}==

s="0.654682,0.925557,0.409382,0.619391,0.891663,0.888594,0.716629,0.996200,0.477721,0.946355,0.925092,0.818220,0.624291,0.142924,0.211332,0.221507,0.293786,0.691701,0.839186,0.728260,"

i=0

TextWindow.WriteLine("is between the points:")

TextWindow.WriteLine(" ["+pxy[ii][1]+","+pxy[ii][2]+"] and")

{{out}}

<pre>

[0.925092,0.818220]

</pre>

 

=={{header|Objective-C}}==

See [[Closest-pair problem/Objective-C]]

=={{header|OCaml}}==

 

 

type point = { x : float; y : float }

Printf.printf "(%f, %f) (%f, %f) Dist %f\n" a.x a.y b.x b.y (dist c)

 

=={{header|Oz}}==

Translation of pseudocode:

fun {Distance X1#Y1 X2#Y2}

{Sqrt {Pow X2-X1 2.0} + {Pow Y2-Y1 2.0}}

{ForAll Points RandomPoint}

{Show Points}

=={{header|PARI/GP}}==

Naive quadratic solution.

my(r=norml2(v[1]-v[2]),at=[1,2]);

for(a=1,#v-1,

);

[v[at[1]],v[at[2]]]

=={{header|Pascal}}==

Brute force only calc square of distance, like AWK etc...

As fast as [[Closest-pair_problem#Faster_Brute-force_Version | D ]] .

{$IFDEF FPC}

{$MODE Delphi}

Writeln('P[',i:4,']= x: ',PointLst[i].ptX:0:8,

' y: ',PointLst[i].ptY:0:8);

//without randomize always same results

//32-Bit

//32-Bit

PointCnt = { 10000*sqrt(10) } 31623;-> real 0m1.112s 10x times runtime</pre>

=={{header|Perl}}==

The divide & conquer technique is about 100x faster than the brute-force algorithm.

use POSIX qw(ceil);

 

}

 

}

}

 

}

 

my ($rx, $ry) = @_;

 

my $midx = ceil($N/2)-1;

my ($al, $bl, $dL) = closest_pair_real(\@PL, \@yR);

my ($ar, $br, $dR) = closest_pair_real(\@PR, \@yL);

 

}

}

}

 

=={{header|Phix}}==

Brute force and divide and conquer (translated from pseudocode) approaches compared

{{out}}

<pre>

Closest pair: {0.0328051,0.0966250} {0.0328850,0.0966250}, distance=0.000120143 (0.14s)

</pre>

=={{header|PicoLisp}}==

(let Min T

(use (Pt1 Pt2)

Min )

(setq Min N Pt1 P Pt2 Q) ) ) )

Test:

<pre>: (scl 6)

(0.839186 . 0.728260) ) )

-> ((891663 . 888594) (925092 . 818220) 77910)</pre>

=={{header|PL/I}}==

/* Closest Pair Problem */

closest: procedure options (main);

end;

end closest;

=={{header|Prolog}}==

'''Brute force version, works with SWI-Prolog, tested on version 7.2.3.

% main predicate, find and print closest point

do_find_closest_points(Points) :-

closest(points(P1,P2,Dist), points(_,_,Dist2), points(P1,P2,Dist)) :-

Dist =< Dist2.

To test, pass in a list of points.

point(0.654682, 0.925557),

point(0.409382, 0.619391),

point(0.839186, 0.728260)

]).

{{out}}

<pre>

false.

</pre>

=={{header|PureBasic}}==

'''Brute force version

Protected N=ArraySize(P()), i, j

Protected mindistance.f=Infinity(), t.d

ProcedureReturn mindistance

EndProcedure

 

Implementation can be as

x.d

y.d

Data.d 0.716629, 0.996200, 0.477721, 0.946355, 0.925092, 0.818220

Data.d 0.624291, 0.142924, 0.211332, 0.221507, 0.293786, 0.691701, 0.839186, 0.72826

{{out}}

<pre>Mindistance= 0.077910

 

Press ENTER to quit</pre>

=={{header|Python}}==

Compute nearest pair of points using two algorithms

times()

times()

 

{{out}} followed by timing comparisons<br>

Time for closestPair 0.119326618327

>>> </pre></div>

=={{header|R}}==

{{works with|R|2.8.1+}}

Brute force solution as per wikipedia pseudo-code

xy = cbind(x,y)

cp = bruteforce(xy)

else bruteforce(pmatrix,n+1,pd)

}

 

Quicker brute force solution for R that makes use of the apply function native to R for dealing with matrices. It expects x and y to take the form of separate vectors.

{

distancev <- function(pointsv)

"\n\tDistance: ",minrow[3],"\n",sep="")

c(distance=minrow[3],x1.x=x[minrow[1]],y1.y=y[minrow[1]],x2.x=x[minrow[2]],y2.y=y[minrow[2]])

 

 

This is the quickest version, that makes use of the 'dist' function of R. It takes a two-column object of x,y-values as input, or creates such an object from seperate x and y-vectors.

 

# takes two-column object(x,y-values), or creates such an object from x and y values

if(!is.null(y)) x <- cbind(x, y)

x2=x[point.pair[2],1],y2=x[point.pair[2],2],

distance=min.dist)

 

y = (sample(-1000.00:1000.00,length(x)))

cp = closest.pairs(x,y)

0.17 0.00 0.19

 

 

Using dist function for brute force, but divide and conquer (as per pseudocode) for speed:

{

if (!is.null(y))

print(closest.pairs.bruteforce(x,y))

cat(sprintf("That took %.2f seconds.\n",proc.time()[3] - tstart))

{{out}}

<pre>

That took 6.38 seconds.

</pre>

=={{header|Racket}}==

The brute force solution using complex numbers

to represent pairs.

#lang racket

(define (dist z0 z1) (magnitude (- z1 z0)))

(displayln (~a "Closest points: " result))

(displayln (~a "Distance: " (dist* result)))

 

The divide and conquer algorithm using a struct to represent points

#lang racket

(struct point (x y) #:transparent)

(match-define (list (point p1x p1y) (point p2x p2y)) (closest-pair points))

(printf "Closest points on a quadratic curve (~a,~a) (~a,~a)\n" p1x p1y p2x p2y)

 

{{out}}

Closest points: (0+1i 1+2i)

Distance: 1.4142135623730951

 

Closest points on a quadratic curve (0,0) (1,1)

 

=={{header|REXX}}==

Programming note: &nbsp; this REXX version allows two (or more) points to be identical, and will

<br>manifest itself as a minimum distance of zero &nbsp; (the variable &nbsp; <big> <tt> '''dd''' </tt> </big> &nbsp; on line 17).

if datatype(seed, 'W') then call random ,,seed /*seed for RANDOM (BIF) repeatability.*/

/*╔══════════════════════╗*/ do j=1 for N /*generate N random points*/

end /*j*/ /*X & Y make the point.*/

/* [↓] use of XJ & YJ speed things up.*/

end /*j*/ /* [↑] when done, A & B are the points*/

$= 'For ' N " points, the minimum distance between the two points: "

/*──────────────────────────────────────────────────────────────────────────────────────*/

sqrt: procedure; parse arg x; if x=0 then return 0; d=digits(); m.=9; numeric form; h=d+6

<pre>

For 100 points, the minimum distance between the two points: ══x══ ══y══ is: 219.228192

[ 7483, 1700]

</pre>

<pre>

For 200 points, the minimum distance between the two points: ══x══ ══y══ is: 39.408121

[17627, 19198]

</pre>

}}

<pre>

[ 6263, 19108]

</pre>

=={{header|Ring}}==

decimals(10)

x = list(10)

next

see "closest pair is : " + mini + " and " + minj + " at distance " + sqrt(min)

Output:

<pre>

closest pair is : 3 and 6 at distance 0.0779101914

</pre>

 

=={{header|Ruby}}==

 

def distance(p1, p2)

x.report("bruteforce") {ans1 = closest_bruteforce(points)}

x.report("recursive") {ans2 = closest_recursive(points)}

'''Sample output'''

<pre>

=={{header|Run BASIC}}==

Courtesy http://dkokenge.com/rbp

dim x(n)

dim y(n)

data 0.211332, 0.221507

data 0.293786, 0.691701

 

=={{header|Scala}}==

import scala.util.Random

 

}

}

 

{{out}}

Divide and conquer (52 ms): (0.4198255166110827, 0.45044969701435)-(0.41984960343173994, 0.4499078600557793) : 5.423720721077961E-4

</pre>

=={{header|Seed7}}==

This is the brute force algorithm:

 

var float: x is 0.0;

var float: y is 0.0;

result := [] (points[savei], points[savej]);

end if;

=={{header|Sidef}}==

sqr(a[0] - b[0]) + sqr(a[1] - b[1])

}

var points = N.of { [1.rand*20 - 10, 1.rand*20 - 10] }

var (af, bf, df) = closest_pair(points)

=={{header|Smalltalk}}==

See [[Closest-pair problem/Smalltalk]]

=={{header|Swift}}==

 

 

struct Point {

guard xP.count > 3 else { return xP.closestPairBruteForce() }

let (yl, yr) = yP.reduce(into: ([Element](), [Element]()), {cur, el in

if el.x > xm {

guard count != 2 else { return (minDistance, closestPoints) }

for j in i+1..<count {

let (iIndex, jIndex) = (index(startIndex, offsetBy: i), index(startIndex, offsetBy: j))

}

 

 

{{out}}

 

<pre>(Point(x: 5.279430517795172, y: 8.85108182685002), Point(x: 5.278427575530877, y: 8.851990433099456))</pre>

=={{header|Tcl}}==

Each point is represented as a list of two floating-point numbers, the first being the ''x'' coordinate, and the second being the ''y''.

 

# retrieve the x-coordinate

set time [time {set ::dist($method) [closest_$method $points]} 1]

puts [format "%-10s %9d %9d %s" $method $::comparisons [lindex $time 0] [lindex $::dist($method) 0]]

{{out}}

<pre>method compares time closest

recursive 14613 488094 0.0015652738546658382</pre>

Note that the <code>lindex</code> and <code>llength</code> commands are both O(1).

=={{header|Ursala}}==

The brute force algorithm is easy.

each remaining pair the sum of the squares of the differences

between corresponding coordinates.

 

The divide and conquer algorithm following the specification

given above is a little more hairy but not much longer.

The <code>eudist</code> library function

is used to compute the distance between points.

#import flo

 

^(fleq-<&l,fleq-<&r); @blrNCCS ~&lrbhthPX2X+ ~&a^& fleq$-&l+ leql/8?al\^(eudist,~&)*altK33htDSL -+

^C/~&rr ^(eudist,~&)*tK33htDSL+ @rlrlPXPlX ~| fleq^\~&lr abs+ minus@llPrhPX,

test program:

 

<

#cast %eeWWA

 

{{out}}

The output shows the minimum distance and the two points separated

(-1.745694e+00,3.276434e+00))

</pre>

=={{header|VBA}}==

 

Private Type MyPoint

Dist = Sqr((p1.X - p2.X) ^ 2 + (p1.Y - p2.Y) ^ 2)

End Function

{{out}}

<pre>For 10 points, runtime : 0 sec.

dist : 2,445694

--------------------------------------------------</pre>

=={{header|Visual FoxPro}}==

CLOSE DATABASES ALL

CREATE CURSOR pairs(id I, xcoord B(6), ycoord B(6))

? "Closest pair is " + TRANSFORM(id1) + " and " + TRANSFORM(id2) + "."

? "Distance is " + TRANSFORM(SQRT(dist2))

{{out}}

<pre>

Closest pair is 3 and 6.

Distance is 0.077910.

</pre>

 

and is perfectly adequate, even for a thousand points.

 

 

proc ClosestPair(P, N); \Show closest pair of points in array P

[0.839186, 0.728260]]; \9

ClosestPair(Data, 10);

 

{{out}}

0.891663,0.888594 -- 0.925092,0.818220

</pre>

 

=={{header|zkl}}==

An ugly solution in both time and space.

fcn init(_x,_y){ var[const] x=_x, y=_y; }

fcn distance(p){ (p.x-x).hypot(p.y-y) }

if(d1 < d2) p1 else p2

});

2.0, 0.0, 8.0, 4.0,

7.0, 4.0, 9.0, 10.0,

0.293786, 0.691701, 0.839186, 0.72826)

.pump(List,Void.Read,Point);

{{out}}

<pre>

L(Point(0.925092,0.81822),Point(0.891663,0.888594),0.0779102)

</pre>

=={{header|ZX Spectrum Basic}}==

{{trans|BBC_BASIC}}

20 FOR i=1 TO 10

30 READ x(i),y(i)

210 DATA 0.211332,0.221507

220 DATA 0.293786,0.691701