Рассчитать пару вхождений

Question

Рассчитать пару вхождений

Допустим, у меня есть следующая строка:

foo,bar,baz
bar,foo
quux,baz,foo

Я хотел бы создать список пар, состоящих более чем из одной пары, поэтому вы получите следующий массив:

[['foo', 'bar'], ['foo', 'baz']],

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

Кто-нибудь может подтолкнуть меня в правильном направлении?
Может быть, с каким-то алгоритмом эффективности или просто примером кода?

Большое спасибо заранее !!!

1

arrays pair php

Решение

Другие решения

<?
$str = 'foo,bar,baz,baz,b
bar,foo,b,a
quux,b,baz,foo,a';


// prepare a working array
$array = array_map(function ($i) { return array_unique(array_map('trim', explode(',', $i))); }, explode("\n", $str));

// find intersects of all arrays
$res = array();
for($i=0; $i < count($array); $i++)
for($j=$i+1; $j < count($array); $j++) {
$temp = array_unique(array_intersect($array[$i], $array[$j]));
sort($temp);     // Reaet indexes
$res[] = $temp;
}

// Gather unique pairs
$pairs = array();
foreach($res as $item)
for($i=0; $i < count($item); $i++)
for($j=$i+1; $j < count($item); $j++) {
$c = true;
foreach($pairs as $p)
if(!array_diff($p, array($item[$i], $item[$j]))) {
$c = false;
break;
}
if($c) $pairs[] = array($item[$i], $item[$j]);
}
print_r($pairs);

результат

[ [b, bar], [b, foo], [bar, foo], [b, baz], [baz, foo], [a,b], [a, foo] ]

Демо на eval

0

Источник

Accepted Answer

Разделяй и властвуй.

Подготовьте список всех пар одной строки, а затем объедините список пар всех строк и выясните, какие повторяются.

$string = <<<STRING
foo,bar,baz
bar,foo
quux,baz,foo
STRING;

$lines = array_map(function ($line) {
// split lines into words
$words = explode(',', $line);

// filter repeats
$words = array_unique($words);

// sort words
sort($words);

return $words;
}, preg_split('/\R/', $string));

function pairs($words) {
$length = count($words);

if ($length < 2) {
throw new Exception('No pairs if length < 2');
}

$pairs = [];

// iterate from start to one before last word
for ($i = 0; $i < $length - 1; $i++) {
// iterate from next word to end
for ($j = $i + 1; $j < $length; $j++) {
$pairs[] = [$words[$i], $words[$j]];
}
}

return $pairs;
}

$allPairs = [];
$nonUniquePairs = [];
foreach ($lines as $words) {
$pairs = pairs($words);
foreach ($pairs as $pair) {
// check if pair is already added and not in $nonUniquePairs array
if (in_array($pair, $allPairs, true) && !in_array($pair, $nonUniquePairs, true)) {
$nonUniquePairs[] = $pair;
}
}

$allPairs = array_unique(array_merge($allPairs, $pairs), SORT_REGULAR);
}

И это будут результаты:

'allPairs' =>
array (size=5)
0 =>
array (size=2)
0 => string 'bar' (length=3)
1 => string 'baz' (length=3)
1 =>
array (size=2)
0 => string 'bar' (length=3)
1 => string 'foo' (length=3)
2 =>
array (size=2)
0 => string 'baz' (length=3)
1 => string 'foo' (length=3)
4 =>
array (size=2)
0 => string 'baz' (length=3)
1 => string 'quux' (length=4)
5 =>
array (size=2)
0 => string 'foo' (length=3)
1 => string 'quux' (length=4)
'nonUniquePairs' =>
array (size=2)
0 =>
array (size=2)
0 => string 'bar' (length=3)
1 => string 'foo' (length=3)
1 =>
array (size=2)
0 => string 'baz' (length=3)
1 => string 'foo' (length=3)

0