Есть ли формула для поиска кратчайшей длины, необходимой для достижения уникальности по множеству

Question

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

Допустим, у меня есть переменная длина списка из 32 символов UUID, но то, что я хотел бы достичь, сокращает их во время ссылки только до тех пор, пока это необходимо для достижения уникальности в их наборе. Например, если у меня есть следующий набор UUID (в трубах, вставленных иллюстрировать ответ) ...

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

я потребовала бы только первые три символов для достижения того же уровня уникальности, как если бы я был использовали все 32 символьные строки.

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

Редактирование: только для того, чтобы быть ясным, трубы должны только показать, что я могу достичь уникальности только после трех символов. Результатом формулы/метода должен быть массив равной длины с только кратчайшими строками, полученными из данного набора, в этом случае только первые три символа. Представьте, что я хочу использовать их в URL-адресе и что у меня не может быть двусмысленности, но все же хочу иметь возможность ссылаться на одни и те же записи, как если бы я использовал полную строку в каждом случае.

EDIT2: Фактически ... поскольку я думаю об этом, нет необходимости в массиве результатов, только целое число, минимальная длина, требуемая в символах.

Answer 1

Мне удалось создать несколько кодов для достижения этого. Посмотрите:

• Код 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 
) 

Увидеть их в действии здесь:

• Code 1;
• Code 2.

---

Вы можете изменить возвращаемое значение, чтобы получить только переменную $len.

Answer 2

Вы можете использовать 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);