Closest-pair problem: Difference between revisions

 

 

'''bruteForceClosestPair''' of P(1), P(2), ... P(N)

'''endif'''

 

 

'''closestPair''' of (xP, yP)

 

 

=={{header|Ada}}==

 

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))));

 

<pre>Closest Points:

P1: 8.00000E+00 4.00000E+00

P2: 9.25092E-01 8.18220E-01

Distance: 7.79101E-02</pre>

=={{header|AWK}}==

# syntax: GAWK -f CLOSEST-PAIR_PROBLEM.AWK

BEGIN {

exit(0)

}

<pre>

distance between (0.891663,0.888594) and (0.925092,0.818220) is 0.0779102

</pre>

FOR I% = 0 TO 9

DATA 0.293786, 0.691701

DATA 0.839186, 0.728260

<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

std::copy(std::begin(xP), std::begin(xP) + (N / 2), std::back_inserter(xL));

std::copy(std::begin(xP) + (N / 2), std::end(xP), std::back_inserter(xR));

auto yL = std::vector<point_t>();

auto yR = std::vector<point_t>();

print_point(answer.second.second);

return 0;

 

<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|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|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

{

}

}

 

<pre>

$ fan closestPoints 1000

Time taken: 228ms

</pre>

=={{header|Fortran}}==

See [[Closest pair problem/Fortran]]

=={{header|Go}}==

'''Brute force'''

 

import (

"math"

"math/rand"

)

 

 

const n = 1000

 

func d(p1, p2 xy) float64 {

}

 

func main() {

points := make([]xy, n)

for i := range points {

}

p1, p2 := closestPair(points)

}

return

'''O(n)'''

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

package main

"math"

"math/rand"

)

 

// size of bounding box for points.

// x and y will be random with uniform distribution in the range [0,scale).

 

// point struct

}

 

func d(p1, p2 xy) float64 {

}

 

func main() {

points := make([]xy, n)

for i := range points {

}

p1, p2 := closestPair(points)

// construct map as a histogram:

// key is index into mesh. value is count of points in cell

for ip, p := range s1 {

key := int64(p.x*invB)*mx + int64(p.y*invB)

}

// construct s2 = s1 less the points without neighbors

nx := []int64{-mx - 1, -mx, -mx + 1, -1, 0, 1, mx - 1, mx, mx + 1}

for i, p := range s1 {

invB := 1 / dxi

mx := int64(scale*invB) + 1

for i, p := range s {

key := int64(p.x*invB)*mx + int64(p.y*invB)

nx := []int64{-mx - 1, -mx, -mx + 1, -1, 0, 1, mx - 1, mx, mx + 1}

var min = scale * 2

for _, ofs := range nx {

for _, iq := range hm[p.key+ofs] {

}

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:

 

 

 

 

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

 

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");

}

 

<pre>java ClosestPair 10000

Generated 10000 random points

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);

};

}

 

=={{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)

 

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)

 

 

distance =

pair =

 

 

=={{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|Perl}}==

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|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|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

<pre>Mindistance= 0.077910

Point 1= 0.891663: 0.888594

 

Press ENTER to quit</pre>

=={{header|Python}}==

Compute nearest pair of points using two algorithms

times()

times()

 

(Note how the two algorithms agree on the minimum distance, but may return a different pair of points if more than one pair of points share that minimum separation):

<div style="height:30ex;overflow:scroll"><pre>[(5+9j), (9+3j), (2+0j), (8+4j), (7+4j), (9+10j), (1+9j), (8+2j), 10j, (9+6j)]

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))

<pre>

How many points?

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)))

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

Distance: 1.4142135623730951

 

 

 

 

 

</pre>

 

=={{header|Ruby}}==

 

def distance(p1, p2)

def closest_bruteforce(points)

mindist, minpts = Float::MAX, []

end

end

 

def closest_recursive(points)

0.upto(yP.length - 2) do |i|

(i+1).upto(yP.length - 1) do |k|

end

end

end

 

points = Array.new(100) {Point.new(rand, rand)}

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

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

 

=={{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}}==

 

 

 

}

 

 

=={{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|Smalltalk}}==

See [[Closest-pair problem/Smalltalk]]

 

=={{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]]

<pre>method compares time closest

bruteforce 49995000 512967207 0.0015652738546658382

recursive 14613 488094 0.0015652738546658382</pre>

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

=={{header|Ursala}}==

after deleting equal pairs and attaching to the left of

each remaining pair the sum of the squares of the differences

between corresponding coordinates.

 

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

 

The output shows the minimum distance and the two points separated

by that distance. (If the brute force algorithm were used, it would

(-2.132372e+00,2.358850e+00),

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

</pre>

 

=={{header|XPL0}}==

 

 

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

[0.839186, 0.728260]]; \9

ClosestPair(Data, 10);

 

<pre>

2 -- 5

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 closestPoints(points){

pairs:=Utils.Helpers.pickNFrom(2,points);

triples.reduce(fcn([(_,_,d1)]p1,[(_,_,d2)]p2){

2.0, 0.0, 8.0, 4.0,

7.0, 4.0, 9.0, 10.0,

1.0, 9.0, 8.0, 2.0,

 

closestPoints(points).println(); //-->L(Point(8,4),Point(7,4),1)

0.624291, 0.142924, 0.211332, 0.221507,

0.293786, 0.691701, 0.839186, 0.72826)