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

Ответ 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

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

Общим способом, который может добиться некоторого улучшения над решением грубой силы, является перечислить способы чередования букв с повторами, а затем умножить на способы разделения остальных вокруг них с учетом пробелов, которые необходимо заполнить. Пример 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

Ответ 2

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

Начните с этой строки:

abfdefa

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

ОБЩИЕ ПОЛОЖЕНИЯ

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

abfdefa

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

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

НЕВЕРНЫЕ ПЕРМАТИКИ

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

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

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

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

6! * 2! (= 1,440)

Число перестановок с 'ff' Конечно, поскольку у нас также есть два "f" , число перестановок с "ff" будет таким же, как и с "aa" :

6! * 2! (= 1,440)

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

Если бы у нас был только один символ, проблема закончилась, и конечным результатом будет TOTAL - INVALID перестановки.

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

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

ЗАКЛЮЧИТЕЛЬНОЕ РЕШЕНИЕ

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

TOTAL - INVALID + OVERLAPS

И это:

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

Ответ 3

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

Начните с строки, например:

abcdabc

Отделите первые записи от повторов:

firsts: abcd
repeat: abc

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

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");

Ответ 4

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

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

Пусть n - длина строки решения, скажем (a1, a2,.... a n). Поэтому во время обратного отслеживания, когда было создано только partial решение, скажем (a1, a2,.... a k), сравните значения в ak и а (к-1). Очевидно, вам нужно указать ссылку на предыдущую букву (здесь a (k-1))

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

Ответ 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
    }
}