我有一个数组集合,其中包含从 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
最佳答案
我已完全审阅了我的回复:
- **修复了**中的错误:“数组函数computeRepettition(array $a);”
- 如果在第 1 遍中已找到三元组,则**避免**增加重复
- **返回**一个数组的数组,每个三元组的重复次数在'**numberOfRepetition**'中设置,self中的三元组是数组的键
- **支持**由2位或以上数字组成的号码
- **新** `数组函数 iCombination(array $a);` 减少找到三元组的概率,因为顺序并不重要,并且不允许数字重复
- `array function detectorRepetition(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;
}
关于algorithm - 查找数组中重复的三元组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28478327/