2

我有一个数组集合，其中包含从 1 到 10 的数字。每个数组的大小为 5。例如

  [1,2,3,4,5]
  [3,4,9,8,2]
  [1,5,7,9,2]
  [1,2,5,9,7]
  ...........
  [3,8,1,6,9]

我应该使用什么算法在这些数组中找到重复的三元组？例如，其中一个结果应该是 1,2,5，因为这个三元组包含在某些数组中。我不介意某些三合会重复了多少次。我最常看 n （可能是 3 或 4 或其他）。

[1,2,3] 与 [3,1,2] 相同，每个数字只允许出现一次。[3,3,4] 无效。

如果我们假设有 10 个或更多数字的数组，这个问题会变得更难，这样每个数组都可以有三元组的组合。只是思考的食物

 [1,3,5,19,45,11,12,13,9,31]

 [1,3,5,32,46,15,12,18,29,37]

 result : (1,3,5) (1,3,12) (3,5,12) etc
4

2 回答 2

1

我会用蛮力去。取决于您如何定义“三元组”（[1,2,3] 与 [3,2,1] 不同吗？[3,3,3] 是否可以接受？）从 C(10,3)=120 到1000 个可能的三元组，每个数组生成 C(5,3)=10 个三元组。

为三元组准备一个（散列）计数器表，遍历数组，随时更新计数器，选择计数最大的三元组。

于 2015-02-12T14:02:57.407 回答
1

我已经完全审查了我的回复：

  • **已修复的错误**：`array function computeRepettition(array $a);`
    • **避免**如果在 pass-1 中已找到三元组，则重复增加
    • **返回**一个数组数组，每个三元组的重复次数在'**numberOfRepetition**'中设置，self中的三元组是数组的key
    • **支持**由2位或更多位组成的数字
  • **新增** `array function iCombination(array $a);`减少找到三元组的概率，因为顺序不重要，不允许重复数字
  • **更新** `array function detectRepetition(array $a);`检测所有可以找到的三元组
<?php
define ("MIN_LENGTH_VECTOR"     , 3  );
define ("KEY_SEPERATOR"         , '-');

$src2D = array (

     array(1,3,5,19,45,11,12,13,9, 100,31),   
     array(1,3,5,32,46,15,100, 12,18,29,37),
     array(1222,32222,5,3222222,4622222,1522222,100, 12,182222,292222,372222));
var_dump (computeRepetition ($src2D));

function computeRepetition ($src2D) {
    $repetition = array ();
    for ($i=0 ; $i<count($src2D)-1 ; $i++) {

        foreach ($repetition as &$rep) {
            $rep['escape'] = TRUE;
        }

        for ($j=$i+1 ; $j<count($src2D) ; $j++) {
            $t = buildTruth ($src2D[$i], $src2D[$j]);
            $r = detectRepetition ($t);

            if (is_null ($r)) continue;

            $comb = iCombination ($r);

            foreach ($comb as $cb) {
                if (isset ($repetition[$cb]['escape']) &&  $repetition[$cb]['escape'] === TRUE) continue;
                if (array_key_exists ($cb, $repetition)) {
                    $repetition[$cb]['numberOfRepetition']++;
                } else {
                    $repetition[$cb]['numberOfRepetition'] = 2;
                    $repetition[$cb]['escape']             = FALSE;
                }
            }
        }
    }
    return $repetition;
}   

function detectRepetition ($t) {
    $a = array ();
    foreach ($t as $key => $value) {
        if ($value === TRUE) {
            $a[] = $key;
        }
    }
    if (count($a) < MIN_LENGTH_VECTOR) return NULL; 
    return $a;
}

function iCombination ($array) {
    $res = array ();
    sort ($array, SORT_NUMERIC);

    for ($i = 0 ; $i < count ($array) - 2 ; $i++) {
        for ($k = $i + 1 ; $k < count ($array) - 1 ; $k++) {
            for ($l = $k + 1 ; $l < count ($array) ; $l++) {
                $res[] = $array[$i] . KEY_SEPERATOR . $array[$k] . KEY_SEPERATOR . $array[$l]; 
            }
        }           
    }
    return $res;
}


function buildTruth ($vec1, $vec2) {
    foreach ($vec1 as $v) {
        $t[$v] = FALSE;
    }
    foreach ($vec2 as $v) {
        if (isset ($t[$v]) && $t[$v] === FALSE ) $t[$v] = TRUE ;
    }
    return $t;
}
于 2015-02-13T12:56:30.060 回答