2

非常に大きなデータセットがあり、すべてのデータセットを満たす最小のセットを見つけようとしています。最終セットには、すべてのデータセットに含まれる1つの値が含まれている必要があります

データの小さなサンプルは次のようになります

[0] => Array
    (
        [0] => 21
        [1] => 21
        [2] => 21
    )

[1] => Array
    (
        [0] => 29
    )

[2] => Array
    (
        [0] => 27
    )

[3] => Array
    (
        [0] => 21
        [1] => 21
        [2] => 21
        [3] => 39
        [4] => 39
        [5] => 43
    )

[4] => Array
    (
        [0] => 29
        [1] => 33
        [2] => 33
        [3] => 43
    )

この場合、21、27、および29を返すロジックが必要です。返される値は、すべての配列に一致する値の最小数である必要があります。私はPHPプログラマーなので、この関数をPHPで記述しています。

4

1 に答える 1

2

このアルゴリズムに従うことができます：

テスト後に更新

$data=array(
            array(21,29,27,57,22),
            array(22,21,23,24,25,26),
            array(31)
            );

$map = array(); // keep a map of values and how many times they occur in other sets
foreach ($data as $setid => $set) {
    foreach (array_unique($set) as $v) {
        $map[$v][$setid] = true;
    }
}

function reverseCount(array $a, array $b)
{
    return count($b) - count($a);
}

// sort reversed on intersection count
uasort($map, 'reverseCount');

// after sorting the first number will be the one that occurs the most
// keep track of which sets have been hit
$setmap = array(); $n = count($data);
foreach ($map as $v => $sets) {
    $hits = 0;
    foreach ($sets as $setid => $dummy) {
        if (!isset($setmap[$setid])) {
            --$n;
            ++$hits;
            $setmap[$setid] = true;
        } else {
            continue;
        }
    }
    if ($hits) {
        echo "value $v\n";
        if (!$n) {
            // all sets are hit
            break;
        }
    }
}

今回テストしました。これは欲張り近似アルゴリズムと見なされるため、常に正しい結果が得られるとは限りません。

しかし、それがあなたに何ができるかについての考えを与えることを願っています。何かがあなたを混乱させるか、私がそれについて完全に間違っているかどうか私に知らせてください:)

于 2012-05-19T14:37:46.197 に答える