Перестановки за исключением повторяющихся символов

Question

Я работаю над проблемой Free Code Camp - http://www.freecodecamp.com/challenges/bonfire-no-repeats-please

Описание проблемы заключается в следующем -

Возвращает количество полных перестановок предоставленной строки, дона» t повторяются последовательные буквы. Например, «aab» должен вернуть 2, потому что он имеет 6 полных перестановок, но только 2 из них не имеют повторяющуюся букву (в данном случае «a»).

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

Но у меня есть это грызущее чувство, что я могу решить это математически.

Первый вопрос, тогда - можно?

Второй вопрос - Если да, то какую формулу я мог бы использовать?

Для дальнейшей разработки -

Примера, приведенный в задаче «ааЪ», который говорится на сайте имеется шесть возможных перестановок, только две встречи неповторных критерии характера:

ааЪ аба бея ааЪ аба бея

проблемы видит каждый символ как уникальный, так, может быть, «AAB» может лучше охарактеризовать как «a1a2b»

тестов для этой задачи заключаются в следующих (возвращая число перестановок, которые соответствуют ЧРИ Teria) -

"aab" should return 2 
"aaa" should return 0 
"abcdefa" should return 3600 
"abfdefa" should return 2640 
"zzzzzzzz" should return 0 

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

Я отправил этот вопрос на math.stackexchange - https://math.stackexchange.com/q/1410184/264492

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

• "aab" = 3! - 2! * 2! = 2
• "abcdefa" = 7! - 6! * 2! = 3600

Но попытка выяснить формулу для случаев, когда повторяется более одного символа, ускользнула от меня. например "abfdefa"

Answer 1

Вот один из способов подумать об этом, который все еще кажется мне немного сложным: вычесть количество возможностей с запрещенными соседями.

Например abfdefa:

There are 6 ways to place "aa" or "ff" between the 5! ways to arrange the other five 
letters, so altogether 5! * 6 * 2, multiplied by their number of permutations (2). 

Based on the inclusion-exclusion principle, we subtract those possibilities that include 
both "aa" and "ff" from the count above: 3! * (2 + 4 - 1) choose 2 ways to place both 
"aa" and "ff" around the other three letters, and we must multiply by the permutation 
counts within (2 * 2) and between (2). 

So altogether, 

7! - (5! * 6 * 2 * 2 - 3! * (2 + 4 - 1) choose 2 * 2 * 2 * 2) = 2640 

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

Общим способом, который может достичь некоторого улучшения над решением грубой силы, является перечислить способы чередования букв с повторами, а затем умножить на способы разделения остальных вокруг них с учетом пробелов, которые должны быть заполнены , Пример, abfdefa, может выглядеть примерно так:

afaf/fafa => (5 + 3 - 1) choose 3 // all ways to partition the rest 
affa/faaf => 1 + 4 + (4 + 2 - 1) choose 2 // all three in the middle; two in the middle, one anywhere else; one in the middle, two anywhere else 
aaff/ffaa => 3 + 1 + 1 // one in each required space, the other anywhere else; two in one required space, one in the other (x2) 

Наконец, умножить на подсчетов перестановок, так вообще:

2 * 2! * 2! * 3! * ((5 + 3 - 1) choose 3 + 1 + 4 + (4 + 2 - 1) choose 2 + 3 + 1 + 1) = 2640 

Answer 2

Ну, у меня не будет математического решения для вас здесь.

Я думаю, вы знаете, возвратов, как я percieved от вашего answer.So вы можете использовать с возвратами для генерации всех перестановок и пропуская определенную перестановку всякий раз, когда повторения встречается.Этот метод называется Backtracking и Обрезка.

Пусть п быть длина строки решения, скажем, (а1, а2, .... п). Так что во время, когда откат был сформирован только частичное решение, скажем (а1, а2, .... к) сравнивает значения в ак и а (к-1). Очевидно, что вам нужно maintaion ссылку на предыдущее письмо (здесь (к-1))

Если оба одинаковы, то вспыхивают от частичного решения, не доходя до конца и начать создавать еще одну перестановку a .

Answer 3

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

Start со строкой как:

abcdabc

Seperate первые мест где с повторениями :

Firsts: ABCD
повторов: а

Найти все перестановки из первых:

ABCD ABDC adbc ADCB ...

Затем, один за другим, вставьте повторы в каждую перестановку, следуя этим правилам:

• Начните с повторным характером, чей оригинал приходит первым в
  новинок например при вставке abc в dbac, использовать b первого
• Поместите повторить два или более мест после первого
  вхождения, например, при вставке b в dbac, результаты dbabc и dbacb
• Тогда рекурсию для каждого результата с остальными повторяющимися символами

Я видел этот вопрос с одним повторным характером, где число перестановок abcdefa где два a сохраняются отдельно, задано как 3600. Однако этот способ подсчета считает abcdefa и abcdefa двумя отличительными перестановками, «потому что они меняются». На мой взгляд, это всего лишь одна перестановка и ее двойная, а правильный ответ - 1800; приведенный ниже алгоритм вернет оба результата.

function seperatedPermutations(str) { 
 
    var total = 0, firsts = "", repeats = ""; 
 
    for (var i = 0; i < str.length; i++) { 
 
     char = str.charAt(i); 
 
     if (str.indexOf(char) == i) firsts += char; else repeats += char; 
 
    } 
 
    var firsts = stringPermutator(firsts); 
 
    for (var i = 0; i < firsts.length; i++) { 
 
     insertRepeats(firsts[i], repeats); 
 
    } 
 
    alert("Permutations of \"" + str + "\"\ntotal: " + (Math.pow(2, repeats.length) * total) + ", unique: " + total); 
 

 
    // RECURSIVE CHARACTER INSERTER 
 
    function insertRepeats(firsts, repeats) { 
 
     var pos = -1; 
 
     for (var i = 0; i < firsts.length, pos < 0; i++) { 
 
      pos = repeats.indexOf(firsts.charAt(i)); 
 
     } 
 
     var char = repeats.charAt(pos); 
 
     for (var i = firsts.indexOf(char) + 2; i <= firsts.length; i++) { 
 
      var combi = firsts.slice(0, i) + char + firsts.slice(i); 
 
      if (repeats.length > 1) { 
 
       insertRepeats(combi, repeats.slice(0, pos) + repeats.slice(pos + 1)); 
 
      } else { 
 
       document.write(combi + "<BR>"); 
 
       ++total; 
 
      } 
 
     } 
 
    } 
 

 
    // STRING PERMUTATOR (after Filip Nguyen) 
 
    function stringPermutator(str) { 
 
     var fact = [1], permutations = []; 
 
     for (var i = 1; i <= str.length; i++) fact[i] = i * fact[i - 1]; 
 
     for (var i = 0; i < fact[str.length]; i++) { 
 
      var perm = "", temp = str, code = i; 
 
      for (var pos = str.length; pos > 0; pos--) { 
 
       var sel = code/fact[pos - 1]; 
 
       perm += temp.charAt(sel); 
 
       code = code % fact[pos - 1]; 
 
       temp = temp.substring(0, sel) + temp.substring(sel + 1); 
 
      } 
 
      permutations.push(perm); 
 
     } 
 
     return permutations; 
 
    } 
 
} 
 

 
seperatedPermutations("abfdefa");

Расчета на основании этой логики числа результатов для строки, как abfdefa, с 5 "первым" символами и 2 повторяющихся символы (A и F), будут:

• 5 «первых» персонажей создают 5! = 120 перестановок
• Каждый символ может быть в 5 положениях, с 24 перестановок каждый:
  A**** (24)
  *A*** (24)
  **A** (24)
  ***A* (24)
  ****A (24)
• Для каждого из этих положений символ повторения должен иметь не менее 2-х мест после его «первого», так что он составляет 4, 3, 2 и 1 места соответственно (для последней позиции повторение невозможно). При повторном характере вставленной, это делает 240 перестановок:
  A***** (24 * 4)
  *A**** (24 * 3)
  **A*** (24 * 2)
  ***A** (24 * 1)
• В каждом из них случаи, второй символ, который будет повторен, может быть в 6 местах, а символ повторения будет иметь 5, 4, 3, 2 и 1 место.Однако второй символ (F) не может находиться в том же месте, что и первый символ (A), поэтому одна из комбинаций всегда невозможна:
  A****** (24 * 4 * (0 + 4 + 3 + 2 + 1)) = 24 * 4 * 10 = 960
  *A***** (24 * 3 * (5 + 0 + 3 + 2 + 1)) = 24 * 3 * 11 = 792
  **A**** (24 * 2 * (5 + 4 + 0 + 2 + 1)) = 24 * 2 * 12 = 576
  ***A*** (24 * 1 * (5 + 4 + 3 + 0 + 1)) = 24 * 1 * 13 = 312
• И 960 + 792 + 576 + 312 = 2640, ожидаемый результат.

Или, для любой строки, как abfdefa с 2 повторами:

где F есть число "первых".

Чтобы вычислить общее количество без идентичных перестановок (что, я думаю, имеет смысл), вы разделите это число на 2^R, где R - число или повторяется.

Answer 4

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

Давайте начнем с этой строкой:

abfdefa

Чтобы найти решение, мы должны вычислить общее число перестановок (без ограничений), а затем вычесть недопустимые.

---

ВСЕГО подстановок

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

abfdefa

, который имеет 7 символов, есть семь ящиков для заполнения. Мы можем заполнить первое с любым из 7 символов, второе - с любым из оставшихся 6 и т. Д. Таким образом, общее число перестановок без ограничений составляет:

7 * 6 * 5 * 4 * 3 * 2 * 1 = 7! (= 5.040)

---

НЕДЕЙСТВИТЕЛЬНЫЕ подстановок

Любая перестановка с двумя равными символами бок о бок не является действительным. Посмотрим, сколько из них у нас есть. Чтобы вычислить их, мы будем считать, что любой символ, который имеет один и тот же символ рядом, будет в том же поле. Как они должны быть вместе, почему бы не считать их чем-то вроде «сложного» характера? В нашей строке примера есть два повторяющихся символа: «a» появляется дважды, а «f» также появляется дважды.

Количество перестановок с 'аа' Теперь у нас есть только шесть ящиков, так как один из них будет наполнен 'аа':

6 * 5 * 4 * 3 * 2 * 1 = 6!

Мы также должны учитывать, что два «а» могут быть сами перестроены в 2! (поскольку у нас есть два «а») пути. Таким образом, общее количество перестановок с двумя «а» вместе составляет:

6! * 2! (= 1.440)

Количество перестановок с «FF» Конечно, мы также имеем два «F», то число перестановок с «FF» будет таким же, как те, с «аа ':

6! * 2! (= 1.440)

---

перекрывается

Если бы мы повторили только один символ, проблема закончена, и конечный результат будет TOTAL - НЕДЕЙСТВИТЕЛЬНЫЕ перестановками.

Но, если у нас есть более одного повторяющегося символа, мы подсчитали некоторые из недопустимых строк два или более раз. Мы должны заметить, что некоторые из перестановок с двумя «а» вместе также будут иметь два «f» вместе, и наоборот, поэтому нам нужно добавить их обратно. Как их считать? Поскольку у нас есть два повторяющихся символа, мы рассмотрим два «сложных» поля: один для вхождений «aa» и другого для «ff» (оба одновременно). Итак, теперь мы должны заполнить 5 коробок: один с 'aa', другой с 'ff' и 3 с остальными 'b', 'd' и 'e'. Кроме того, каждый из этих «aa» и «bb» можно переставить в 2! пути. Таким образом, общее количество перекрытий составляет:

5! * 2! * 2! (= 480)

---

Конечный раствор

Окончательное решение этой проблемы будет:

ВСЕГО - НЕвЕРНЫЙ + перекрывается

И это:

7! - (2 * 6! * 2!) + (5 * * 2! * 2!) = 5,040 - 2 * 1,440 + 480 = 2,640

Answer 5

Спасибо Lurai за отличное предложение.Это потребовало времени и немного продолжительное, но вот мое решение (оно проходит все тестовые примеры на FreeCodeCamp после перехода на JavaScript, конечно) - извинения за имена дрянных переменных (обучение тому, как быть плохим программистом тоже;)): D

import java.util.ArrayList; 
import java.util.HashMap; 
import java.util.Map; 

public class PermAlone { 

    public static int permAlone(String str) { 
     int length = str.length(); 
     int total = 0; 
     int invalid = 0; 
     int overlap = 0; 
     ArrayList<Integer> vals = new ArrayList<>(); 
     Map<Character, Integer> chars = new HashMap<>(); 

     // obtain individual characters and their frequencies from the string 
     for (int i = 0; i < length; i++) { 
      char key = str.charAt(i); 
      if (!chars.containsKey(key)) { 
       chars.put(key, 1); 
      } 
      else { 
       chars.put(key, chars.get(key) + 1); 
      } 
     } 

     // if one character repeated set total to 0 
     if (chars.size() == 1 && length > 1) { 
      total = 0; 
     } 
     // otherwise calculate total, invalid permutations and overlap 
     else { 
      // calculate total 
      total = factorial(length); 

      // calculate invalid permutations 
      for (char key : chars.keySet()) { 
       int len = 0; 
       int lenPerm = 0; 
       int charPerm = 0; 
       int val = chars.get(key); 
       int check = 1; 
       // if val > 0 there will be more invalid permutations to calculate 
       if (val > 1) { 
        check = val; 
        vals.add(val); 
       } 
       while (check > 1) { 
        len = length - check + 1; 
        lenPerm = factorial(len); 
        charPerm = factorial(check); 
        invalid = lenPerm * charPerm; 
        total -= invalid; 
        check--; 
       } 
      } 

      // calculate overlaps 
      if (vals.size() > 1) { 
       overlap = factorial(chars.size()); 
       for (int val : vals) { 
        overlap *= factorial(val); 
       } 
      } 

      total += overlap; 
     } 
     return total; 
    } 

    // helper function to calculate factorials - not recursive as I was running out of memory on the platform :? 
    private static int factorial(int num) { 
     int result = 1; 
     if (num == 0 || num == 1) { 
      result = num; 
     } 
     else { 
      for (int i = 2; i <= num; i++) { 
       result *= i; 
      } 
     } 
     return result; 
    } 

    public static void main(String[] args) { 
     System.out.printf("For %s: %d\n\n", "aab", permAlone("aab")); // expected 2 
     System.out.printf("For %s: %d\n\n", "aaa", permAlone("aaa")); // expected 0 
     System.out.printf("For %s: %d\n\n", "aabb", permAlone("aabb")); // expected 8 
     System.out.printf("For %s: %d\n\n", "abcdefa", permAlone("abcdefa")); // expected 3600 
     System.out.printf("For %s: %d\n\n", "abfdefa", permAlone("abfdefa")); // expected 2640 
     System.out.printf("For %s: %d\n\n", "zzzzzzzz", permAlone("zzzzzzzz")); // expected 0 
     System.out.printf("For %s: %d\n\n", "a", permAlone("a")); // expected 1 
     System.out.printf("For %s: %d\n\n", "aaab", permAlone("aaab")); // expected 0 
     System.out.printf("For %s: %d\n\n", "aaabb", permAlone("aaabb")); // expected 12 
     System.out.printf("For %s: %d\n\n", "abbc", permAlone("abbc")); //expected 12 
    } 
}