Проверка на вхождение одного вектора в другой

[denisOg]

Есть два вектора
$v1 = array(1,0,1,0,1,1,0,1,1,0);
$v2 = array(1,0,1,0,1,0,0,0,0,0);

Как узнать входит ли вектор $v2 в вектор $v1?
В данном примере входит.

ПС в задачи есть массив веторов и один вектор (от юзера), который собственно и нужно проверить на вхождние в любой из векторов в массиве

 

[Вурдалак]

Для того, чтобы узнать входит или не входит, нужно сначала дать этому определение. Кажется, будто ты имел в виду, что любая координата вектора $v2 должна быть меньше и равна соответствующей координате вектора $v1. Для этого существует цикл for.

 

[denisOg]

Для того, чтобы узнать входит или не входит, нужно сначала дать этому определение. Кажется, будто ты имел в виду, что любая координата вектора $v2 должна быть меньше и равна соответствующей координате вектора $v1. Для этого существует цикл for.

Да, я так и думал, что прийдется через for сверять каждый элемент векторов, но может есть какая нибудь функция php для проверки множеств или может математический алгоритм есть какой нить...

 

[MiksIr]

Э... ваще ничего не понял. Если речь о векторе как о индексном массиве, то понятие вхождения - это нахождение одной последовательности внутри другой.

 

[Breeze]

когда вижу 1 и 0 всегда хочется сделать вот так =)

$v1 = bindec("1010110110");
$v2 = bindec("1010100000");

if ( $v1 == ($v1 | $v2) ) {
echo "входит";
}

не знаю уж насколько верно, но идея такая

 

[WBS]

Два варианта решения с замерами скорости работы:

<?

function arr2int ($arr) {
// преобразует последовательность единиц и нулей (массив $arr) в число
	$num = 0;
	foreach ($arr as $val) {
		if ($val) $num = ($num << 1) + 1;
		else $num <<= 1;
	}
	return $num;
}

function in_vec1 ($arr1, $arr2) {
// проверяет, входит ли $arr1 в $arr2
	$size = count($arr1);
	for ($i=0; $i<=$size; $i++)
		if ($arr1[$i]>$arr2[$i])
			return FALSE;
	return TRUE;
}

function in_vec2 ($arr1, $arr2) {
// проверяет, входит ли $arr1 в $arr2
	$v2 = arr2int($arr2);
	return $v2 == ($v2 | arr2int($arr1));
}


$v1 = array(1,0,1,0,1,1,0,1,1,0);
$v2 = array(1,0,1,0,1,0,0,0,0,0);
$v3 = array(1,1,1,0,1,0,0,0,0,0);

$t1 = microtime(1);

for ($i=0; $i<1000000; $i++)
	in_vec1($v2, $v1);
$t2 = microtime(1);

for ($i=0; $i<1000000; $i++)
	in_vec1($v3, $v1);
$t3 = microtime(1);

for ($i=0; $i<1000000; $i++)
	in_vec2($v2, $v1);
$t4 = microtime(1);

for ($i=0; $i<1000000; $i++)
	in_vec2($v3, $v1);
$t5 = microtime(1);

$t_diff1 = $t2-$t1;
$t_diff2 = $t3-$t2;
$t_diff3 = $t4-$t3;
$t_diff4 = $t5-$t4;

print("
in_vec1 (\$v2 входит в \$v1) - {$t_diff1}<br>
in_vec1 (\$v3 не входит в \$v1) - {$t_diff2}<p>
in_vec2 (\$v2 входит в \$v1) - {$t_diff3}<br>
in_vec2 (\$v3 не входит в \$v1) - {$t_diff4}
");

?>

Результаты:

in_vec1 ($v2 входит в $v1) - 19.76014995575
in_vec1 ($v3 не входит в $v1) - 0.60267615318298
in_vec2 ($v2 входит в $v1) - 3.2096939086914
in_vec2 ($v3 не входит в $v1) - 3.2341151237488

 

[denisOg]

WBS
Спасибо за подробный отчет
Я написал мини функцию на подобие вашей

function in_vec1 ($arr1, $arr2) {
// проверяет, входит ли $arr1 в $arr2
    $size = count($arr1);
    for ($i=0; $i<=$size; $i++)
        if ($arr1[$i]>$arr2[$i])
            return FALSE;
    return TRUE;
}