udovicic · August 29, 2015 14:03
diff --git a/fragment.php b/fragment.php
 <?php
 /**
 * Using PHP syntax, partition the array A into two arrays B and C in a way that that the difference between the
 * sum of elements in B and the sum of elements in C is minimized.
 *
 * @author Stjepan Udovičić ([email protected])
 */

 /** Predefined array */
 $A = array(
 //    1, 2, 3, 1000
    72, 79, 84, 46, 14, 4, 62, 88, 58, 21, 16, 27, 13, 52, 96, 70, 28, 75,
    76, 45, 5, 71, 43, 87, 64, 95, 72, 22, 43, 15, 25, 70, 64, 93, 56, 90,
    84, 31, 49, 71, 29, 46, 6, 17, 81, 21, 75, 44, 2, 45, 67, 57, 93, 72,
    39, 74, 43, 53, 40, 45, 87, 23, 44, 52, 1, 56, 32, 26, 32, 67, 42
 );

 $numElements = count($A);
 $targetSum = (int)(array_sum($A) / 2); // Targeted sum is halfs of sum(A)
 $C = $A;
 arsort($C);
 $largestNum = array_shift(array_slice($C, 0, 1));
 $executionTime = microtime(true);
 $diff = 0;

 for ($i=0; $i<$largestNum; $i++) {
    /**
     * By incrementing $i, one is incrementing allowed difference between sum of fragmented arrays.
     * Max difference is equal to largest values from initial array
     */

    $B = fragment($A, $targetSum-$i);
    if ($B) {
        /** Result has been found, termineate search */
        $diff = $i;
        break;
    }
 }
 $executionTime = microtime(true) - $executionTime;

 /**
 * Remove elements of $B from $C to get final $C array.
 */
 foreach($B as $num) {
    foreach ($C as $i => $n) {
        if ($n == $num) {
            unset($C[$i]);
            break;
        }
    }
 }

 /**
 * Recursive function which does all the magic
 *
 * @param $set array Operating|initial set of elements
 * @param $targetSum int Targeted sum of elements
 * @param array $partial Working set of elements. Initially not set
 * @return array|bool False, or resulting array
 */
 function fragment($set, $targetSum, $partial=array())
 {
    $tempSum = array_sum($partial);

    if ($tempSum == $targetSum) {
        /** Result has been found */
        return $partial;
    } else if ($tempSum > $targetSum) {
        /** Sum is to large, drop combinations */
        return false;
    }

    for ($i=0; $i<count($set); $i++) {
        /**
         * This is hard to explain shortly. For details watch 45min video by Julie Zelenski on
         * Programming Abstractions Course (CS106B) in the Stanford Computer Science Department.
         * https://www.youtube.com/watch?v=NdF1QDTRkck
         */
        $temp = $partial;
        $temp[] = $set[$i];
        $remaining = array_slice($set, $i+1);

        $solution = fragment($remaining, $targetSum, $temp);
        if ($solution != false) {
            /** In case that previous call return result, escape recursion */
            return $solution;
        }
    }

    /** No result has been found */
    return false;
 }
 ?>
 <!doctype html>
 <html lang="en">
 <head>
    <meta charset="UTF-8">
    <title>Fragmentation solution</title>
    <style>
        pre {white-space: pre-wrap;}
    </style>
 </head>
 <body>
    <h1>Initial array</h1>
    <pre>
        input array = [<?php echo implode(', ', $A) ?>]
        array size = <?php echo $numElements ?>

        targeted sum = <?php echo $targetSum ?>
    </pre>

    <h1>Solution</h1>
    <pre>
        Results in <?php echo number_format($executionTime, 5) ?>s
        Diff <?php echo $diff ?>

        
        array #1
        content = [<?php echo implode(', ', $B) ?>]
        array size = <?php echo count($B) ?>


        array #2
        content = [<?php echo implode(', ', $C) ?>]
        array size = <?php echo count($C) ?>
    </pre>
 </body>
 </html>
	<?php
	/**
	* Using PHP syntax, partition the array A into two arrays B and C in a way that that the difference between the
	* sum of elements in B and the sum of elements in C is minimized.
	*
	* @author Stjepan Udovičić ([email protected])
	*/

	/** Predefined array */
	$A = array(
	// 1, 2, 3, 1000
	72, 79, 84, 46, 14, 4, 62, 88, 58, 21, 16, 27, 13, 52, 96, 70, 28, 75,
	76, 45, 5, 71, 43, 87, 64, 95, 72, 22, 43, 15, 25, 70, 64, 93, 56, 90,
	84, 31, 49, 71, 29, 46, 6, 17, 81, 21, 75, 44, 2, 45, 67, 57, 93, 72,
	39, 74, 43, 53, 40, 45, 87, 23, 44, 52, 1, 56, 32, 26, 32, 67, 42
	);

	$numElements = count($A);
	$targetSum = (int)(array_sum($A) / 2); // Targeted sum is halfs of sum(A)
	$C = $A;
	arsort($C);
	$largestNum = array_shift(array_slice($C, 0, 1));
	$executionTime = microtime(true);
	$diff = 0;

	for ($i=0; $i<$largestNum; $i++) {
	/**
	* By incrementing $i, one is incrementing allowed difference between sum of fragmented arrays.
	* Max difference is equal to largest values from initial array
	*/

	$B = fragment($A, $targetSum-$i);
	if ($B) {
	/** Result has been found, termineate search */
	$diff = $i;
	break;
	}
	}
	$executionTime = microtime(true) - $executionTime;

	/**
	* Remove elements of $B from $C to get final $C array.
	*/
	foreach($B as $num) {
	foreach ($C as $i => $n) {
	if ($n == $num) {
	unset($C[$i]);
	break;
	}
	}
	}

	/**
	* Recursive function which does all the magic
	*
	* @param $set array Operating\|initial set of elements
	* @param $targetSum int Targeted sum of elements
	* @param array $partial Working set of elements. Initially not set
	* @return array\|bool False, or resulting array
	*/
	function fragment($set, $targetSum, $partial=array())
	{
	$tempSum = array_sum($partial);

	if ($tempSum == $targetSum) {
	/** Result has been found */
	return $partial;
	} else if ($tempSum > $targetSum) {
	/** Sum is to large, drop combinations */
	return false;
	}

	for ($i=0; $i<count($set); $i++) {
	/**
	* This is hard to explain shortly. For details watch 45min video by Julie Zelenski on
	* Programming Abstractions Course (CS106B) in the Stanford Computer Science Department.
	* https://www.youtube.com/watch?v=NdF1QDTRkck
	*/
	$temp = $partial;
	$temp[] = $set[$i];
	$remaining = array_slice($set, $i+1);

	$solution = fragment($remaining, $targetSum, $temp);
	if ($solution != false) {
	/** In case that previous call return result, escape recursion */
	return $solution;
	}
	}

	/** No result has been found */
	return false;
	}
	?>
	<!doctype html>
	<html lang="en">
	<head>
	<meta charset="UTF-8">
	<title>Fragmentation solution</title>
	<style>
	pre {white-space: pre-wrap;}
	</style>
	</head>
	<body>
	<h1>Initial array</h1>
	<pre>
	input array = [<?php echo implode(', ', $A) ?>]
	array size = <?php echo $numElements ?>

	targeted sum = <?php echo $targetSum ?>
	</pre>

	<h1>Solution</h1>
	<pre>
	Results in <?php echo number_format($executionTime, 5) ?>s
	Diff <?php echo $diff ?>


	array #1
	content = [<?php echo implode(', ', $B) ?>]
	array size = <?php echo count($B) ?>


	array #2
	content = [<?php echo implode(', ', $C) ?>]
	array size = <?php echo count($C) ?>
	</pre>
	</body>
	</html>