#php #cpp #c #алгоритм
Необходимо создать кратчайшую строку, которая содержит в себе все строки из массива.
Пример ниже.
Массив строк: 000, 001, 100, 011
Кратчайшая строка, которая содержит все предыдущие строки: 100011
Интересен сам алгоритм, нежели чем реализация.
Ответы
Ответ 1
Эта задача относится к сложным как в реализации так и в скорости задачам. Она может быть решена с помощью модернизированного алгоритма Ахо-Корасик http://e-maxx.ru/algo/aho_corasick . Конкретные детали реализации там же в предпоследнем абзаце (Нахождение кратчайшей строки, содержащей вхождения одновременно всех образцов) . Важно! сложность будет порядка 2^n где n - количество строк. Может искать эту задачу по запросу shortest common superstring она NP-полная.Ответ 2
Возможна упрощённая постановка задачи. Если у нас есть 2 строки, то вариантов их склеивания четыре: 1. В исходном порядке. 2. В обратном порядке. 3. Первая строка внутри второй. 4. Вторая строка внутри первой. Рассмотрим сочетания из n строк по r строк (которых Сnr). Будем называть их сочетаниями ранга r. Оптимум для каждого такого сочетания достигается при одной из r! внутренних перестановок. Упрощение постановки - в предположении, что каждый новый вариант оптимальной перестановки ранга r+1 можно получить, склеивая одну из оптимальных перестановок ранга r с недостающей строкой. Оптимизация вычислений - в том, что используется массив сочетаний вместо массива размещений (которых в r! раз больше), а для каждой новой перестановки ранга (r+1) проверяется всего r вариантов склеивания вместо (r+1)!. В то же время, это "жадный" вариант без перебора. Поэтому строка результата может оказаться длинее оптимальной. В упрощённой постановке каждое сочетание можно описать уникальным числовым ключом-маской, битовое представление которого содержит единицы в позициях, соответствующих используемым строкам. Ключи предыдущего ранга получаются путём инверсии одной из единиц, а ключи следующего ранга - путём инверсии одного из нулей. Каждому такому ключу соответствует битовая строка результата, которая допускает сжатие каждых 8 битовых символов в один упакованный байтовый. Решение задачи получается путём обхода всех сочетаний с повышением их ранга. Для случая n строк всего получается 2n вариантов сочетаний всех рангов, и это следует из формулы бинома Ньютона для (1+1)n. Так, для случая n = 30 требуется перебрать 230 = 1073741824 сочетаний, а максимальная размерность массива сочетаний достигается при r=15 и равна С3015=155117520. Инициализация проводится для ранга r=2 среди уникальных строк (не входящих в другие строки) путём попарного склеивания. Далее в цикле по r массив сочетаний ранга r трансформируется в массив сочетаний ранга r+1. В конце цикла остаётся массив из одного элемента с ключом из единиц и результирующей строкой. Отличие предлагаемого решения от алгоритма Ахо-Корасик - в том, что перебираются не битовые строки (если при построении бора нет символов, увеличивающих количество поглощаемых образцов, вводится промежуточная вершина), а сочетания исходных образцов. В то же время обход графа в ширину по сложности равнозначен перебору сочетаний. Таким образом, реальная сложность алгоритма Ахо - Корасик при плохом склеивании строк может оказаться равной 2mn, и вопрос о сравнении скорости алгоритмов остаётся актуальным. Программа на языке PHP: set_time_limit(300); function bits($num, $n){ return substr(sprintf("%032b", $num), -$n, $n); } function print_array($text, $arr){ print($text."["); foreach($arr as $key => $item){ printf("%d => \"%s\", " , $key, (string)$item); } print "]"; } function glue($s1, $s2){ global $count_glue; $count_glue++; $len1 = strlen($s1); $len2 = strlen($s2); if($s1 == $s2){ $res = $s1; // строки равны }elseif(($len1 < $len2) && (strpos($s2, $s1) !== false)){ $res = $s2; // первая строка есть подстрока второй }elseif(($len1 > $len2) && (strpos($s1, $s2) !== false)){ $res = $s1; // вторая строка есть подстрока первой }else{ // ищем наибольшие общие фраагменты с краёв $lmin = min($len1,$len2); $len12 = 0; $len21 = 0; for($l = 1; $l<$lmin; $l++){ if(substr($s1, -$l, $l) == substr($s2,0, $l)) $len12 = $l; if(substr($s1, 0, $l) == substr($s2,-$l, $l)) $len21 = $l; } if($len12 > $len21){ $res = $s1.substr($s2, $len12, $len2-$len12); }else{ $res = $s2.substr($s1, $len21, $len1-$len21); } } //print(""$s1" + "$s2" = "$res" "); return $res; } function chars_bits_arrays(){ global $chars2bits, $bits2chars; for($b = 0; $b < 256; $b++){ $chars = chr($b); $bits = sprintf("%08b", $b); $bits2chars[$bits] = $chars; $chars2bits[$b] = $bits; } } function pack_bits($bits){ global $bits2chars; $len_bits = strlen($bits); $cnt_chars = ceil($len_bits/8); $bits8 = str_pad($bits, 8*$cnt_chars, "0"); $chars = chr($len_bits); for($c = 0; $c < $cnt_chars; $c++){ $chars .= $bits2chars[substr($bits8, 8*$c, 8)]; } return $chars; }; function unpack_bits($chars){ global $chars2bits; $end_chars = strlen($chars)-1; $len_bits = ord($chars[0]); $bits = ""; for($c = 1; $c < $end_chars; $c++){ $bits .= $chars2bits[ord($chars[$c])]; } $last_char = $chars2bits[ord($chars[$end_chars])]; $bits .= substr($last_char, 0, $len_bits - 8*($end_chars-1)); return $bits; } function print_packed($text, $str_packed, $n=31){ print($text."["); foreach($str_packed as $key => $item){ printf(""$key" => "%s", " , unpack_bits($item)); } print "]"; } function unique_strings(&$strings){ $cnt = count($strings); $delete = []; for($k1 = 0; $k1 < $cnt; $k1++){ $s1 = $strings[$k1]; $len1 = strlen($s1); for($k2 = 0; $k2 < $k1; $k2++){ $s2 = $strings[$k2]; $len2 = strlen($s2); if($s1 == $s2){ $delete[] = $k1; }elseif(empty($s1) || (($len1 < $len2) && (strpos($s2, $s1) !== false))){ $delete[] = $k1; // первая строка есть подстрока второй }elseif(empty($s2) || (($len2 < $len1) && (strpos($s1, $s2) !== false))){ $delete[] = $k2; // вторая строка есть подстрока первой } } } foreach($delete as $key){ unset($strings[$key]); } $strings = array_slice($strings, 0); } function rank2($strings){ $cnt = count($strings); $result = []; for($k1 = 0; $k1 < $cnt; $k1++){ $s1 = $strings[$k1]; for($k2 = 0; $k2 < $k1; $k2++){ $s2 = $strings[$k2]; $g = glue($s1, $strings[$k2]); $key = (1 << $k1) | (1 << $k2); $result[$key] = pack_bits($g); } } return $result; } function inc_rank(&$supers, &$strings, &$r){ $n = count($strings); $result = []; foreach($supers as $key => $packed){ $super = unpack_bits($packed); $len_super = strlen($super); //print "
$key=>"$super": "; for($k = 0; $k < $n; $k++){ $bit = 1 << $k; if (($key & $bit) == 0){ $key1 = $key | $bit; $s = $strings[$k]; $len_s = strlen($s); if($super == $s){ $result[$key1] = $packed; }else{ //print " $key1 =>"; $g = glue($super, $strings[$k]); if(!array_key_exists($key1, $result)){ $result[$key1] = pack_bits($g); // print "-новое!"; } elseif(strlen($g) < ord($result[$key1][0])){ $result[$key1] = pack_bits($g); // print "-лучше!"; } } } } } return($result); } function the_best_combi($strings){ global $count_glue; $start_timer = microtime(true); $count_glue = 0; print_array("
***** Склеивание массива строк: *****
strings = ", $strings); unique_strings($strings); print_array("
Уникальные строки:
unique_strings = ", $strings); //print "
"; $cnt_strings = count($strings); $supers = rank2($strings); //print_packed("
*** Сочетания ранга 2: ***
", $supers, $cnt_strings); for($r=3; $r <= $cnt_strings; $r++){ //print "
"; $result = inc_rank($supers, $strings, $r); if($result === false){ break; } $supers = $result; //print_packed("
*** Сочетания ранга $r: ***
", $supers, $cnt_strings); } if($result === false){ $new = []; foreach($strings as $str){ $new[] = $str; } $strings = $new; $supers = the_best_combi($strings); } $time = microtime(true) - $start_timer; print "
Время, секунд: $time"; print "
Склеено пар строк: $count_glue"; print_packed("
Результат: ", $supers, $cnt_strings); } $chars2bits = []; $bits2chars = []; chars_bits_arrays(); $count_glue = 0; $strings = ["000", "001", "100", "011"]; the_best_combi($strings); $strings = ["000", "001", "010", "011", "100", "101", "110", "111", "000", "001", "010", "011", "100", "101", "110", "111"]; the_best_combi($strings); $strings = ["0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"]; the_best_combi($strings); $strings = ["010101100", "100010001", "1100010001000", "1000010101100", "01000001010", "1000100101", "0100001100110", "00110111", "1010101000", "0100011001", "001000111010", "1000111011", "00110011100", "11000110001", "10001110111", "1000111001111"]; the_best_combi($strings); Результаты: ***** Склеивание массива строк: ***** strings = [0 => "000", 1 => "001", 2 => "100", 3 => "011", ] Уникальные строки: unique_strings = [0 => "000", 1 => "001", 2 => "100", 3 => "011", ] Время, секунд: 0.00200009346008 Склеено пар строк: 22 Результат: ["15" => "100011", ] ***** Склеивание массива строк: ***** strings = [0 => "000", 1 => "001", 2 => "010", 3 => "011", 4 => "100", 5 => "101", 6 => "110", 7 => "111", 8 => "000", 9 => "001", 10 => "010", 11 => "011", 12 => "100", 13 => "101", 14 => "110", 15 => "111", ] Уникальные строки: unique_strings = [0 => "000", 1 => "001", 2 => "010", 3 => "011", 4 => "100", 5 => "101", 6 => "110", 7 => "111", ] Время, секунд: 0.117007017136 Склеено пар строк: 988 Результат: ["255" => "1110100011", ] ***** Склеивание массива строк: ***** strings = [0 => "0000", 1 => "0001", 2 => "0010", 3 => "0011", 4 => "0100", 5 => "0101", 6 => "0110", 7 => "0111", 8 => "1000", 9 => "1001", 10 => "1010", 11 => "1011", 12 => "1100", 13 => "1101", 14 => "1110", 15 => "1111", ] Уникальные строки: unique_strings = [0 => "0000", 1 => "0001", 2 => "0010", 3 => "0011", 4 => "0100", 5 => "0101", 6 => "0110", 7 => "0111", 8 => "1000", 9 => "1001", 10 => "1010", 11 => "1011", 12 => "1100", 13 => "1101", 14 => "1110", 15 => "1111", ] Время, секунд: 66.4247989655 Склеено пар строк: 524152 Результат: ["65535" => "1111011001010000111", ] ***** Склеивание массива строк: ***** strings = [0 => "010101100", 1 => "100010001", 2 => "1100010001000", 3 => "1000010101100", 4 => "01000001010", 5 => "1000100101", 6 => "0100001100110", 7 => "00110111", 8 => "1010101000", 9 => "0100011001", 10 => "001000111010", 11 => "1000111011", 12 => "00110011100", 13 => "11000110001", 14 => "10001110111", 15 => "1000111001111", ] Уникальные строки: unique_strings = [0 => "1100010001000", 1 => "1000010101100", 2 => "01000001010", 3 => "1000100101", 4 => "0100001100110", 5 => "00110111", 6 => "1010101000", 7 => "0100011001", 8 => "001000111010", 9 => "00110011100", 10 => "11000110001", 11 => "10001110111", 12 => "1000111001111", ] Время, секунд: 15.895909071 Склеено пар строк: 53157 Результат: ["8191" => "100011100111100011101110001001010001100111000010101100011000100010001110101010000010100001100110111", ]
Комментариев нет:
Отправить комментарий