visla
BAN USERI like the smell of old good problems in the morning while I am drinking coffee.
This question tells - given the set of points meaning the points are already available and also it says find the first K points and not Kth point closest to 0,0. My approach to this is to calculate the distances of every point to the 0,0 by creating distanceSquared array. Then this array gets sorted by distance from 0,0 by using quick sort algorithm O(n log n). As a result first K points are printed out. Space complexity is O(2n) and time complexity is O(2n log n).
<?php
$points = array(
array(10,10),
array(15,12),
array(20,250),
array(1,5),
array(56, 4)
);
function partition(&$distancesSq, $left, $right, $pivotIndex)
{
$storeIndex = $left;
$pivotValue = $distancesSq[$pivotIndex][1];
// swap pivot to right
$tmp = $distancesSq[$pivotIndex]; $distancesSq[$pivotIndex] = $distancesSq[$right]; $distancesSq[$right] = $tmp;
for($i = $left; $i < $right; $i++)
if ($distancesSq[$i][1] < $pivotValue)
{
$tmp = $distancesSq[$storeIndex];
$distancesSq[$storeIndex] = $distancesSq[$i];
$distancesSq[$i] = $tmp;
$storeIndex++;
}
// move pivot to storeIndex
$tmp = $distancesSq[$right];
$distancesSq[$right] = $distancesSq[$storeIndex];
$distancesSq[$storeIndex] = $tmp;
return $storeIndex;
}
// Quick sort distances.
function sortDistances(&$distancesSq, $left, $right)
{
if ($left < $right)
{
$pivotIndex = (int)($left + ($right-$left)/2);
$newPivotIndex = partition($distancesSq, $left, $right, $pivotIndex);
sortDistances($distancesSq, $left, $newPivotIndex-1);
sortDistances($distancesSq, $newPivotIndex+1, $right);
}
}
function findClosest($k, $points)
{
// Find distances from 0,0
$distancesSq = array();
for($i = 0; $i < count($points); $i++)
{
$distancesSq[] = array($i, $points[$i][0]*$points[$i][0] + $points[$i][1]*$points[$i][1]);
}
// Now find the first K points close to 0,0.
// Sort all distances using quick sort O(n log n)
sortDistances($distancesSq, 0, count($distancesSq)-1);
// Display the first $k points
for($i = 0; $i < $k; $i++)
echo "{" . $points[$distancesSq[$i][0]][0] . "," . $points[$distancesSq[$i][0]][1] . "}\n";
}
findClosest(2, $points);
?>
Here is the simple solution in PHP:
<?php
$set = array(1,2,3,4,5);
function displaySets($set, $level, $maxLevel, $fromIndex, $setString)
{
if ($level == 0) $setString = "{";
if ($level == $maxLevel)
{
echo $setString . '}';
}
else
{
for($i = $fromIndex; $i < count($set); $i++)
{
$setString2 = $setString . $set[$i];
if ($level+1 < $maxLevel) $setString2 .= ',';
displaySets($set, $level+1, $maxLevel, $i+1, $setString2);
}
}
}
function findPowerSets($set)
{
for($i = 0; $i <= count($set); $i++)
displaySets($set, 0, $i, 0, "");
}
findPowerSets($set);
We have few spaces were we operate. Object space - transformations are done only to an object, world space - transformations apply to objects and positions of objects in the world. 3x3 matrix is enough to perform any transformation inside the object space since the object is at the origin. But lets say we want to move that object somewhere in the world and transform it also. We would need to do two operations if we are working only within 3x3 matrix to perform that, one to transform the object and the other to translate the object. In order to change the origin of transformation we need fourth dimension. Since working and keeping two separate states (transformation and translation) is not convinient it is better to store state of object in the world space in 4x4. it is more convenient for the use and the math will work when we decide to multiply 4x4 matrices to keep all the transformations/translations together.
- visla September 27, 2013