排除重复字符的排列

Question

我正在解决一个免费代码训练营问题 - http://www.freecodecamp.com/challenges/bonfire-no-repeats-please

问题描述如下-

Return the number of total permutations of the provided string that don't have repeated consecutive letters. For example, 'aab' should return 2 because it has 6 total permutations, but only 2 of them don't have the same letter (in this case 'a') repeating.

我知道我可以通过编写一个程序来解决这个问题，该程序创建每个排列，然后过滤掉具有重复字符的排列。

但我有一种痛苦的感觉，我可以用数学方法解决这个问题。

那么第一个问题 - 我可以吗？

第二个问题 - 如果是，我可以使用什么公式？

进一步阐述-

问题中给出的例子是"aab"，该网站说它有六种可能的排列，只有两种符合非重复字符标准：

aab aba baa aab aba baa

这个问题认为每个字符都是独一无二的，所以也许 "aab" 可以更好地描述为 "a1a2b"

本题测试如下（返回符合条件的排列数）-

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

我已经通读了很多 post 有关组合数学和排列的书籍，但似乎正在为自己挖一个更深的洞。但我真的很想尝试有效地解决这个问题，而不是通过一系列所有可能的排列来暴力破解。

我 post 在 math.stackexchange - https://math.stackexchange.com/q/1410184/264492

上编辑了这个问题

解决仅重复一个字符的情况的数学运算非常简单 - 字符总数减去可用空格数乘以重复字符的阶乘。

"aab" = 3！ - 2！ * 2！ = 2
"abcdefa" = 7！ - 6！ * 2！ = 3600

但是我无法找出重复多个字符的情况下的公式。例如"abfdefa"

Answer 1

好吧，我不会在这里为您提供任何数学解决方案。

我猜你知道回溯，正如我从你的 answer.So 中了解到的那样，你可以使用回溯来生成所有排列，并且 在遇到重复时跳过特定排列 。这种方法称为回溯和修剪。

设n为解字符串的长度，比如(a1,a2,....an)。因此，在回溯期间，当仅形成 partial 解决方案时，例如 (a1,a2,....ak) 比较 [=18 处的值=]ak 和 a(k-1)。显然你需要维护对前一封信的引用（这里是 a(k-1)）

如果两者相同则从部分解决方案中突破，没有到达终点并开始从1创建另一个排列.

Answer 2

这是一种思考方式，对我来说似乎仍然有点复杂：减去不允许的邻居的可能性计数。

例如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 3

这似乎是一个足够简单的问题，但我在错误的轨道上花了几个小时才最终找出正确的逻辑。要查找具有一个或多个重复字符的字符串的所有排列，同时保持相同字符的分隔：

以如下字符串开头：

abcdabc

将第一次出现与重复出现分开：

firsts: abcd
repeats: abc

找到第一个的所有排列：

abcd abdc adbc adcb ...

然后，按照以下规则，将重复插入到每个排列中：

Start with the repeated character whose original comes first in the firsts
e.g. when inserting abc into dbac, use b first

Put the repeat two places or more after the first occurance
e.g. when inserting b into dbac, results are dbabc and dbacb

Then recurse for each result with the remaining repeated characters

我看到这个问题有一个重复的字符，其中两个 a 保持分开的 abcdefa 的排列数为 3600。但是，这种计算方式考虑了 abcdefa 和 abcdefa 是两个不同的排列，"because the a's are swapped"。在我看来，这只是一个排列及其两倍，正确答案是1800；下面的算法将 return 两个结果。

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 个 "first" 个字符和 2 个重复字符（A 和 F）的字符串，基于结果数量逻辑的计算结果为：

The 5 "first" characters create 5! = 120 permutations

Each character can be in 5 positions, with 24 permutations each:
A**** (24)
*A*** (24)
**A** (24)
***A* (24)
****A (24)

For each of these positions, the repeat character has to come at least 2 places after its "first", so that makes 4, 3, 2 and 1 places respectively (for the last position, a repeat is impossible). With the repeated character inserted, this makes 240 permutations:
A***** (24 * 4)
*A**** (24 * 3)
**A*** (24 * 2)
***A** (24 * 1)

In each of these cases, the second character that will be repeated could be in 6 places, and the repeat character would have 5, 4, 3, 2, and 1 place to go. However, the second (F) character cannot be in the same place as the first (A) character, so one of the combinations is always impossible:
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

And 960 + 792 + 576 + 312 = 2640, the expected result.

或者，对于像 abfdefa 这样有 2 次重复的任何字符串：

其中 F 是 "firsts".

的数量

要计算没有相同排列的总数（我认为这更有意义），您可以将该数字除以 2^R，其中 R 是数字或重复。

Answer 4

这是一种数学方法，不需要检查所有可能的字符串。

让我们从这个字符串开始：

abfdefa

要找到解决方案，我们必须计算排列总数（无限制），然后减去无效排列。

排列总数

我们要填充多个位置，即等于原始字符串的长度。让我们将每个位置视为一个小盒子。所以，如果我们有

abfdefa

里面有7个字，有7个方框要填。我们可以用 7 个字符中的任何一个填充第一个，用剩下的 6 个字符中的任何一个填充第二个，依此类推。所以没有限制的排列总数是：

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

无效排列

任何两个并排相等字符的排列都是无效的。让我们看看我们有多少。为了计算它们，我们将考虑任何具有相同字符并排的字符都将位于同一个框中。既然他们必须在一起，为什么不把他们当作一个"compound"角色呢？我们的示例字符串有两个重复字符：'a' 出现了两次，'f' 也出现了两次。

'aa'的排列数现在我们只有六个盒子，因为其中一个盒子将填满 'aa':

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

我们还要考虑到两个'a'可以在2中自己排列！（因为我们有两种 'a'）方式。所以，两个 'a' 在一起的排列总数是：

6! * 2! (= 1,440)

'ff'的排列数当然，因为我们也有两个'f'，'ff'的排列数与'aa'的排列数相同：

6! * 2! (= 1,440)

重叠

如果我们只重复一个字符，那么问题就结束了，最终结果将是总计 - 无效排列。

但是，如果我们有一个以上的重复字符，我们就会对某些无效字符串进行两次或更多次计数。我们必须注意，一些将两个 'a' 放在一起的排列也会将两个 'f' 放在一起，反之亦然，因此我们需要将它们加回去。我们如何计算它们？由于我们有两个重复的字符，我们将考虑两个 "compound" 框：一个用于 '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

Answer 5

感谢 Lurai 的宝贵建议。花了一段时间，有点冗长，但这是我的解决方案（当然，它在转换为 JavaScript 后通过了 FreeCodeCamp 的所有测试用例）——为蹩脚的变量名道歉（学习如何成为一个糟糕的程序员；）） :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
    }
}

排除重复字符的排列

Permutations excluding repeated characters

algorithm

combinatorics