有没有一个公式可以找到在一个集合中实现唯一性所需的最短长度

Is there a formula to find shortest length required to achieve uniqueness across a set

本文关键字：实现 唯一性 集合 一个 有一个      更新时间：2023-09-26

我希望能够计算实现完全唯一性所需的最短子字符串的长度。

比方说，我有一个由32个字符的UUID组成的可变长度列表，但我想实现的是在引用过程中缩短它们的长度，使其仅与在其集合中实现唯一性所需的长度一样长。例如，如果我有以下一组UUID（插入管道以说明答案）。。。

428|07082e1f445e79501bebfa87396af 
723|0785bffaf4747865c202dd0924c7f
b65|634be909d4e5590aa0cdc97251eef
3c4|d94c683624d75a273e3186ec65b78
09e|bd42af0404bcf90413e11c5b40fbb
011|004743d65466dae8a9a6bc814ef4b
1f1|889e04e3a453fbf57521de0a70b60
1ac|44707af8d4681875171ad47c61037
42f|7a6236deb4a9ead32ab2e816d73a3
83a|fe22086064eec87704127622b8165

我只需要前三个字符就可以获得与使用完整的32个字符串相同的唯一性级别。

我很好奇是否有一个公式可以达到这个值。我知道我可以把它放在几个嵌套的循环中，但我想知道是否有更优雅或更编程的方法来实现这一点。

编辑：为了清楚起见，管道只是为了说明我只需要3个字符就可以实现唯一性。公式/方法的结果应该是一个长度相等的数组，其中只有从给定集合派生的最短字符串，在这种情况下，只有前三个字符。想象一下，我想在URL中使用这些，并且我不能有任何歧义，但仍然希望能够引用相同的记录，就像我在每种情况下都使用了完整的字符串一样。

第2版：实际上。。。据我所想，不需要结果数组，只需要一个整数，以字符为单位的最小长度。

我设法创建了一些代码来实现这一点。看看：

  • 代码1: 
function check_un($array){
    $arr = $array;
    $len = 1;
    $tmp = array();
    while (list($key, $value) = each($arr)) {
        $v = substr($value, 0, $len);
        if (isset($tmp[$v])) {
            $tmp = array();
            $len++;
            reset($arr); // start again
        }
        $tmp[$v] = true;
    }
    $tmp = array_keys($tmp);
    array_shift($tmp);
    return $tmp;
}

基本上，前面的代码检查作为关键字的给定子字符串是否已经设置，这意味着它是重复的。这样，它会转到数组的开头，并开始再次检查更多的字母。

  • 代码2:（较小，但较慢）
function check_un($array){
    $array = array_values($array);
    $len = 1;
    $tmp = array();
    for($i = 0; $i < strlen($array[0]); $i++){
        if( count(array_unique( $tmp = array_map(function($v) use($len){ return substr($v, 0, $len); }, $array ) )) != count($array) ){
            $len++;
        }else{
            break;
        }
    }
    return $tmp; // this was set in the array_map part
}

基本上，前面的代码检查给定子字符串长度的唯一元素的数量是否与原始数组的数量相同。这样，如果有任何重复，数量就会更小，这意味着我们需要使用更多的位置。

过去有一个代码3（我第一次尝试），但它只在编辑历史中可用

你可以用这个测试它们：

$values = array(
    '42807082e1f445e79501bebfa87396af',
    '7230785bffaf4747865c202dd0924c7f',
    'b65634be909d4e5590aa0cdc97251eef',
    '3c4d94c683624d75a273e3186ec65b78',
    '09ebd42af0404bcf90413e11c5b40fbb',
    '011004743d65466dae8a9a6bc814ef4b',
    '1f1889e04e3a453fbf57521de0a70b60',
    '1ac44707af8d4681875171ad47c61037',
    '42f7a6236deb4a9ead32ab2e816d73a3',
    '83afe22086064eec87704127622b8165'
    //,'42807082e1f445e795aaaaaaaaaaaaa' // add this to test with more letters
);
$val = check_un($values);

结果（对于两种情况）：

Array
(
    [0] => 428
    [1] => 723
    [2] => b65
    [3] => 3c4
    [4] => 09e
    [5] => 011
    [6] => 1f1
    [7] => 1ac
    [8] => 42f
    [9] => 83a
)

点击此处查看他们的行动：

  • 代码1
  • 代码2

您可以更改返回值以仅获取$len变量。

您可以使用Array.prototype.reduce()、Object.hasOwnProperty()递归；创建一个对象来存储唯一字符集的值，如果名称不是对象的属性，则将对象名称设置为前两个字符，否则设置前n个字符，直到对象中的每个属性都是唯一的

var arr = ["42807082e1f445e79501bebfa87396af " 
           , "7230785bffaf4747865c202dd0924c7f" 
           , "b65634be909d4e5590aa0cdc97251eef" 
           , "3c4d94c683624d75a273e3186ec65b78"   
           , "09ebd42af0404bcf90413e11c5b40fbb" 
           , "011004743d65466dae8a9a6bc814ef4b" 
           , "1f1889e04e3a453fbf57521de0a70b60" 
           , "1ac44707af8d4681875171ad47c61037" 
           , "42f7a6236deb4a9ead32ab2e816d73a3" 
           , "83afe22086064eec87704127622b8165"];
var obj = {};
arr.reduce((o, uuid) => {
  var n = 1;
  (function re(key) {
    var curr = uuid.slice(0, key);
    if (!o.hasOwnProperty(curr)) {
      o[curr] = uuid;
    } else {
      re(key + 1)
    }
  }(n))
  return obj
}, obj);
console.log(obj, "arr length:", arr.length
           , "obj keys length:", Object.keys(obj).length);

相关文章：