Количество аранжировок без последовательной буквы то же самое

Question

Этот вопрос относится к моему вопросу here. Я пытаюсь получить следующий подсчет программно, чтобы проверить правильность моей математики.

Сколько расположения букв в слове PQRDDDEEEEFFFFF нет без какого-либо последовательного письма того же самое?

Как определить этот счет с помощью php-программы?

Мой подход

1. генерироваться все возможные перестановки с помощью алгоритма кучного и хранится в массиве (алгоритм, используемый кучного как он найден быстрее)
2. удалены все дубликаты с помощью array_unique функции
3. Итерации по массиву идентифицировали строки, в которых смежные буквы одинаковы, используя regexp/(.)\1/ и скопировали строки, в которых смежные буквы не совпадают с новым массивом.
4. Новый массив имеет список элементов, который требуется.

Мой подход работает нормально. Но для больших строк (строки более 10 символов) проблемы памяти возникают из-за большого количества перестановок, поэтому программа не работает.

Есть ли альтернативный подход для определения этого программного обеспечения?

Примечание:

Ищу графа только и не список строк

Answer 1

Вот некоторые Python, что гораздо более эффективно, чем ваш метод, хотя и по-прежнему экспоненциальной (извините, не знаю PHP):

from collections import Counter 


def instancekey(letters): 
    return tuple(sorted(Counter(letters).values())) 


memo = {} 


def permcount(letters): 
    if not letters: 
     return 1 
    key = instancekey(letters) 
    count = memo.get(key) 
    if count is None: 
     count = 0 
     for letter, lettercount in Counter(letters).items(): 
      rest = letters 
      for i in range(lettercount): 
       j = rest.find(letter) 
       rest = rest[:j] + rest[j + 1:] 
       if i % 2 == 0: 
        count += permcount(rest) 
       else: 
        count -= permcount(rest) 
     memo[key] = count 
    return count 

Есть две идеи здесь. Первый заключается в том, чтобы выполнить счет рекурсивно через включение-исключение. Для каждой буквы на входе мы накапливаем количество возможностей, начинающихся с этой буквы. Наивно, достаточно рассчитать возможности для остальных букв, но это не приводит к ограничению, что первые две буквы равны. Таким образом, мы применяем коррекцию - вычитаем количество возможностей, где две буквы удалены. Эта коррекция требует коррекции, после чего мы приходим к inclusion-exclusion formula.

Вторая идея заключается в том, чтобы использовать memoization для значительного сокращения количества оценок функций. Учитывая это слово как PQRDDDEEEEFFFFF, мы считаем

P: 1 
Q: 1 
R: 1 
D: 3 
E: 4 
F: 5 

, а затем опустить письма (потому что они не имеют значения) и сортировать значения:

1,1,1,3,4,5. 

Answer 2

Python

Python является одним из самых популярных открытых источников (бесплатно) языков для работая с большими и сложными наборами данных, необходимыми для больших данных. Он стал очень популярным в последние годы, потому что он является гибким и относительно простым в освоении. Как и самое популярное программное обеспечение с открытым исходным кодом, у него также большое и активное сообщество, занимающееся улучшением продукта и популяризацией его с новыми пользователями. Бесплатный курс Академии Кодекса проведет вас через основы за 13 часов.

Источники:

http://www.datasciencecentral.com/profiles/blogs/ten-top-languages-for-crunching-big-data https://www.continuum.io/why-python

Answer 3

Вы можете переопределить как проблема графа. Граф будет иметь узлы для каждой буквы в вашем наборе «PQRDDEEEEFFFFF» и не разрешать пути с автопилами обратно к одной и той же букве или между узлами, которые представляют одну и ту же букву. Затем вы перечислили бы все нециклические пути длиной 15 через ваш граф. Это должно значительно уменьшить объем памяти вашего кода, и вы не будете генерировать никаких «слов» с последовательными буквами, которые необходимо отбросить. С быстрым поиском google я нашел несколько различных алгоритмов обхода графика в php, доступных в Интернете. Вы можете быстро настроить его в своих целях.

Для значительного повышения производительности вы можете использовать стратегии memoization. то естьначиная с «F», перестановки из других «F» узлов одинаковы, и то же самое относится к подпутьям. Есть некоторые алгоритмы тура рыцаря с воспоминаниями, которые также могут быть адаптированы к этой проблеме.

Answer 4

чистый метод является перебирает его , Просто подсчитайте в базе N, где N - количество различных букв. Количество мест, необходимых в базовом номере N, - это всего лишь количество букв. Затем примените ограничения для числа каждой допустимой буквы и не имея двух последовательных одинаковых.

Это некрасиво и не быстро, но оно даст правильные ответы.

Здесь в PHP:

$letters = 'PQRDDDEEEEFFFFF'; 

$letter_counts = CountLetters($letters); 

echo CountCombinations($letter_counts); 

function CountLetters($letters) { 
    $letter_counts = array(); 
    foreach (str_split($letters) as $letter) { 
     if (isset($letter_counts[$letter])) { 
      $letter_counts[$letter]++; 
     } else { 
      $letter_counts[$letter] = 1; 
     } 
    } 
    return array_values($letter_counts); 
} 

function CountCombinations($allowable) { 
    $max = count($allowable) - 1; 
    $total_places = 0; 
    for ($index = 0; $index <= $max; $index++) { 
     $total_places += $allowable[$index]; 
    } 

    $counter = array_fill(0, $total_places, 0); 

    $combinations = 0; 
    do { 
     $ok = true; 

     // count the number of each character in this combination 
     $bins = array_fill(0, $max + 1, 0); 
     for ($index = 0; $index < $total_places; $index++) { 
      $bins[$counter[$index]]++; 
     } 

     // ensure the counts match the number allowable for each 
     for ($index = 0; $index <= $max; $index++) { 
      if ($bins[$index] != $allowable[$index]) { 
       $ok = false; 
       break; 
      } 

     } 

     // ensure that no two consecutive are the same 
     if ($ok) { 
      for ($index = 0; $index <= ($total_places - 2); $index++) { 
       if ($counter[$index] == $counter[$index + 1]) { 
        $ok = false; 
        break; 
       } 
      } 
     } 

     if ($ok) { 
      $combinations++; 
     } 

     // find the next combination (i.e. count in base N) 
     for ($index = 0; $index <= ($total_places - 1); $index++) { 
      $counter[$index] = $counter[$index] + 1; 
      if ($counter[$index] <= $max) { 
       break; 
      } else { 
       $counter[$index] = 0; 
      } 
     } 
    } while ($index < $total_places); 

    return $combinations; 
}