\n" ; $v = (int) $line ; $v = ( $v == 0 ) ? -1 * ( $n * $n ) : $v ; array_push ( $brr , $v ) ; } array_push ( $arr, $brr ) ; } fclose ( $handle ) ; return $arr ; } function yield_pairs_all ( $union ) { $qstr = sprintf ( "SELECT id , offered AS o , wanted AS w FROM trade_offer WHERE contract = %s" , $union ) ; $darr = db_get ( $qstr ) ; $ret_arr = array ( ) ; foreach ( $darr as $d ) { $offered = $d [ "o" ] ; $wanted = $d [ "w" ] ; $id = $d [ "id" ] ; #$cur_str = $ret_arr [ $id ] ; #list ( $eo , $ew ) = preg_split ( '/\-/', $cur_str ) ; #$eoarr = str2arr ( $eo ) ; #$ewarr = str2arr ( $ew ) ; #array_push ( $eoarr , $offered ) ; #array_push ( $ewarr , $wanted ) ; #$no = arr2str ( array_unique ( $eoarr ) ) ; #$nw = arr2str ( array_unique ( $ewarr ) ) ; #$ret_arr [ $id ] = "${no}-${nw}" ; $ret_arr [ $id ] = "${offered}-${wanted}" ; } return $ret_arr ; } function offered_is_wanted ( $offered , $wanted , $a_demands_b ) { $combination = "${offered}-${wanted}"; if ( array_search ( $combination , $a_demands_b ) ) return true ; else return false ; } function optimize ( $parr0 , $parr1 ) { $warr = array ( ) ; foreach ( $parr0 as $k0 => $arr0 ) { list ( $of0str , $wn0str ) = preg_split ( '/\-/' , $arr0 ) ; $of0 = str2arr ( $of0str ) ; $wn0 = str2arr ( $wn0str ) ; foreach ( $parr1 as $k1 => $arr1 ) { list ( $of1str , $wn1str ) = preg_split ( '/\-/' , $arr1 ) ; $of1 = str2arr ( $of1str ) ; $wn1 = str2arr ( $wn1str ) ; $of_int = 0 ; $wn_int = 0 ; for ( $k = 0 ; $k < count ( $of0 ) ; $k++ ) for ( $l = 0 ; $l < count ( $of1 ) ; $l++ ) if ( $of0 [ $k ] != '0' && $of0 [ $k ] == $of1 [ $l ] ) $of_int++ ; for ( $k = 0 ; $k < count ( $wn0 ) ; $k++ ) for ( $l = 0 ; $l < count ( $wn1 ) ; $l++ ) if ( $wn0 [ $k ] != '0' && $wn0 [ $k ] == $wn1 [ $l ] ) $wn_int++ ; # make sure everything offered is wanted $mismatch = 0 ; for ( $k = 0 ; $k < count ( $of0 ) ; $k++ ) { $counter = 0 ; for ( $l = 0 ; $l < count ( $wn0 ) ; $l++ ) if ( $of0 [ $k ] != 0 && $of0 [ $k ] != $wn0 [ $l ] ) $counter = $counter + 1 ; for ( $l = 0 ; $l < count ( $wn1 ) ; $l++ ) if ( $of0 [ $k ] != 0 && $of0 [ $k ] != $wn1 [ $l ] ) $counter = $counter + 1 ; if ( $counter == count ( $wn0 ) + count ( $wn1 ) ) $mismatch = $mismatch + 1 ; } for ( $k = 0 ; $k < count ( $of1 ) ; $k++ ) { $counter = 0 ; for ( $l = 0 ; $l < count ( $wn0 ) ; $l++ ) if ( $of1 [ $k ] != 0 && $of1 [ $k ] != $wn0 [ $l ] ) $counter = $counter + 1 ; for ( $l = 0 ; $l < count ( $wn1 ) ; $l++ ) if ( $of1 [ $k ] != 0 && $of1 [ $k ] != $wn1 [ $l ] ) $counter = $counter + 1 ; if ( $counter == count ( $wn0 ) + count ( $wn1 ) ) $mismatch = $mismatch + 1 ; } # perform merger if exists full compatibility $merger = null ; if ( $mismatch == 0 && $of_int == 0 && $wn_int == 0 ) { $merger_of = array_merge ( $of0 , $of1 ) ; $merger_wn = array_merge ( $wn0 , $wn1 ) ; sort ( $merger_of ) ; sort ( $merger_wn ) ; $merger_ofstr = arr2str ( $merger_of ) ; $merger_wnstr = arr2str ( $merger_wn ) ; $warr [ "${k0}.${k1}" ] = "${merger_ofstr}-${merger_wnstr}" ; } } } return array_unique ( $warr ) ; } function cartesian ( $parr0 , $parr1 , $a_demands_b ) { $warr = array ( ) ; foreach ( $parr0 as $k0 => $arr0 ) { list ( $of0str , $wn0str ) = preg_split ( '/\-/' , $arr0 ) ; $of0 = str2arr ( $of0str ) ; $wn0 = str2arr ( $wn0str ) ; foreach ( $parr1 as $k1 => $arr1 ) { list ( $of1str , $wn1str ) = preg_split ( '/\-/' , $arr1 ) ; $of1 = str2arr ( $of1str ) ; $wn1 = str2arr ( $wn1str ) ; $of_int = 0 ; $wn_int = 0 ; for ( $k = 0 ; $k < count ( $of0 ) ; $k++ ) for ( $l = 0 ; $l < count ( $of1 ) ; $l++ ) if ( $of0 [ $k ] != '0' && $of0 [ $k ] == $of1 [ $l ] ) $of_int++ ; for ( $k = 0 ; $k < count ( $wn0 ) ; $k++ ) for ( $l = 0 ; $l < count ( $wn1 ) ; $l++ ) if ( $wn0 [ $k ] != '0' && $wn0 [ $k ] == $wn1 [ $l ] ) $wn_int++ ; # make sure everything offered is wanted $mismatch = 0 ; for ( $k = 0 ; $k < count ( $of0 ) ; $k++ ) { $counter = 0 ; for ( $l = 0 ; $l < count ( $wn0 ) ; $l++ ) if ( ! offered_is_wanted ( $of0 [ $k ] , $wn0 [ $l ] , $a_demands_b ) ) $counter = $counter + 1 ; for ( $l = 0 ; $l < count ( $wn1 ) ; $l++ ) if ( ! offered_is_wanted ( $of0 [ $k ] , $wn1 [ $l ] , $a_demands_b ) ) $counter = $counter + 1 ; if ( $counter == count ( $wn0 ) + count ( $wn1 ) ) $mismatch = $mismatch + 1 ; } for ( $k = 0 ; $k < count ( $of1 ) ; $k++ ) { $counter = 0 ; for ( $l = 0 ; $l < count ( $wn0 ) ; $l++ ) if ( ! offered_is_wanted ( $of1 [ $k ] , $wn0 [ $l ] , $a_demands_b ) ) $counter = $counter + 1 ; for ( $l = 0 ; $l < count ( $wn1 ) ; $l++ ) if ( ! offered_is_wanted ( $of1 [ $k ] , $wn1 [ $l ] , $a_demands_b ) ) $counter = $counter + 1 ; if ( $counter == count ( $wn0 ) + count ( $wn1 ) ) $mismatch = $mismatch + 1 ; } # perform merger if exists full compatibility $merger = null ; if ( $mismatch == 0 && $of_int == 0 && $wn_int == 0 ) { $merger_of = array_merge ( $of0 , $of1 ) ; $merger_wn = array_merge ( $wn0 , $wn1 ) ; sort ( $merger_of ) ; sort ( $merger_wn ) ; $merger_ofstr = arr2str ( $merger_of ) ; $merger_wnstr = arr2str ( $merger_wn ) ; $warr [ "${k0}.${k1}" ] = "${merger_ofstr}-${merger_wnstr}" ; } } } return array_unique ( $warr ) ; } function get_n_traders ( ) { $q_str = "SELECT COUNT ( DISTINCT (trader) ) - 1 AS n_traders FROM voucher" ; $darr = db_get ( $q_str ) ; $n_traders = $darr [ 0 ] [ "n_traders" ] ; return $n_traders ; } function compute_trade_all ( $union ) { $a_demands_b = yield_pairs_all ( $union ) ; #var_dump ( $a_demands_b ) ; $iter = count ( $a_demands_b ) ; $last = cartesian ( $a_demands_b , $a_demands_b , $a_demands_b ) ; $prev = array_slice ( $a_demands_b , 0 ) ; for ( $i = 1 ; $i < $iter ; $i++ ) { $new = optimize ( $last , $prev ) ; if ( count ( $new ) == 0 && $i > 2 ) { // then we're done $new = $last ; break ; } else if ( count ( $new ) == 0 && $i == 1 ) { break ; } $prev = $last ; $last = $new ; } # find minimum optimum value $opt_ix = 0 ; $opt_v = 0 ; for ( $i = 0 ; $i < count ( $new ) ; $i++) { list ( $ofstr , $wnstr ) = preg_split ( '/\-/' , $new [ $i ] ) ; $of = str2arr ( $ofstr ) ; $wn = str2arr ( $wnstr ) ; $of_nz = 0 ; $wn_nz = 0 ; for ( $j = 0 ; $j < count ( $of ) ; $j++) if ( $of [ $j ] != '0' ) $of_nz++ ; for ( $j = 0 ; $j < count ( $wn ) ; $j++) if ( $wn [ $j ] != '0' ) $wn_nz++ ; $cur_v = $of_nz - $wn_nz ; $opt_ix = ( $i == 0 || $cur_v > $opt_v ) ? $i : $opt_ix ; $opt_v = ( $i == 0 || $cur_v > $opt_v ) ? $cur_v : $opt_v ; } reset ( $new ) ; $ret_val = current ( $new ) ; $key_val = key ( $new ) ; for ( $i = 0 ; $i < $opt_ix ; $i++ ) { $ret_val = next ( $new ) ; $key_val = key ( $new ) ; } return array ( $key_val , $ret_val ) ; } for ( $union = 0 ; $union < 10 ; $union++ ) { list ( $key , $tarr ) = compute_trade_all ( $union ) ; var_dump ( $key ) ; var_dump ( $tarr ) ; } ?>