如何找到排列满足以下条件的字符串的方法数？
How to find number of ways of permuting a string satisfying the below conditions?
我得到了一个字符串，比方说- "abcd"。
现在我必须找到所有可以通过置换其字符生成的字符串，这样 -
- There are exactly four mismatches in the generated strings and,
- The mismatches exists in pair, for e.g-
字符串 - "abcd" 有三个这样的排列 -
"badc","cdab","dcba".
说明-
让我们考虑"abcd"和"badc"。现在正好有四个与 不匹配，即 (a,b),(b,a),(c, d),(d,c) 并且这些不匹配成对存在。
请注意 "abcde" 有十五个这样的排列-
acbed,adebc,aedcb,baced,badce,baedc,cbaed,cdabe,ceadb,dbeac,dcbae,decab,ebdca ,ecbda,edcba
我哪里失败了？-
我只是手动查找字符串，但是对于大长度的字符串来说这真的很耗时。因此，我需要一个有效的解决方案。
如果你有一个长度为 n 的字符串，由 n 个不同的字母组成，那么你找到的数字是：n * (n - 1) * (n - 2) * (n - 3) / 8.
原因：有C(n, 4)种方法可以从n个字母中选择4个不匹配的地方，并且对于每个这样的四元组，有三种方法将它们配对。
因此结果是C(n, 4) * 3 = n * (n - 1) * (n - 2) * (n - 3) / 8。
这里假设字符串中的所有字母都不相同。从您对问题的描述中不清楚字母是否可以重复。如果是这种情况，请对此答案发表评论。然后我会更新答案。
编辑：现在假设字母可以重复。情况比较复杂。我这里就画个草图吧。
假设字符串包含 m 个不同的字母，分别出现 a_1, ..., a_m 次。另外，为数字 C(a_i, 2) 写 b_i。
分三种情况：
- 情况1：四个错配形成两个相同的对，例如两个 a 和两个 b 被置换。
在本例中，我们有 sum{b_i * b_j : 1 <= i < j <= m} 个不同的字符串。这等于 (sum{b_i}^2 - sum{b_i ^2}) / 2，一个可以在 O(m) 时间内求值的表达式。
- 情况2：四个不匹配包含三个不同的字母，例如一个 a 与一个 b 配对，另一个 a 与一个 配对c.
在这种情况下，首先选择两对中共同的字母，假设它是第 i 个字母；然后必须选择其他两个字母。
所有a_i的总和写s，所有b_i的总和写t。如果我们从剩余的 s - a_i 个字母中选择任意两个字母，我们必须排除这两个字母相同的情况，这种情况有 t - b_i 个可能性。因此，有 C(s - a_i, 2) - (t - b_i) 种不同的方式来选择其他两个字母，因此有 b_i * (C(s - a_i, 2) - (t - b_i)) 种不同的字符串。在这种情况下，对所有 i 求和得出不同字符串的总数。它仍然可以在 O(m) 时间内评估。
- 案例 3：四个不同的字母，例如一个a和一个b一对，一个c和一个d 再组成一对。
思路是一样的。首先，考虑从所有 s 个字母中选择 4 个任意字母的可能性。那么我们要排除几种情况：
我。所有四个字母都相同，这有 sum{C(a_i, 4)} 个案例；
二。三个字母相同，第四个不同，这有sum{C(a_i, 3) * (s - a_i)}例；
三。两个字母相同，另外两个也相同，这正是情况1中计算出的数字；
四。两个字母相同，另外两个不同，这正是情况2中计算出的数字。
所以，从所有 s 个字母中选择四个不同字母的可能性总数是：C(s, 4) - [i] - [ii] - [iii] - [iv]。和以前一样，这个数字应该乘以 3 以产生不同字符串的数量，因为每个四元组给出 3 个不同的字符串。
总而言之，时间复杂度是O(m)，显然是最优的。
我得到了一个字符串，比方说- "abcd"。 现在我必须找到所有可以通过置换其字符生成的字符串，这样 -
- There are exactly four mismatches in the generated strings and,
- The mismatches exists in pair, for e.g-
字符串 - "abcd" 有三个这样的排列 - "badc","cdab","dcba".
说明-
让我们考虑"abcd"和"badc"。现在正好有四个与 不匹配，即 (a,b),(b,a),(c, d),(d,c) 并且这些不匹配成对存在。
请注意 "abcde" 有十五个这样的排列- acbed,adebc,aedcb,baced,badce,baedc,cbaed,cdabe,ceadb,dbeac,dcbae,decab,ebdca ,ecbda,edcba
我哪里失败了？-
我只是手动查找字符串，但是对于大长度的字符串来说这真的很耗时。因此，我需要一个有效的解决方案。
如果你有一个长度为 n 的字符串，由 n 个不同的字母组成，那么你找到的数字是：n * (n - 1) * (n - 2) * (n - 3) / 8.
原因：有C(n, 4)种方法可以从n个字母中选择4个不匹配的地方，并且对于每个这样的四元组，有三种方法将它们配对。
因此结果是C(n, 4) * 3 = n * (n - 1) * (n - 2) * (n - 3) / 8。
这里假设字符串中的所有字母都不相同。从您对问题的描述中不清楚字母是否可以重复。如果是这种情况，请对此答案发表评论。然后我会更新答案。
编辑：现在假设字母可以重复。情况比较复杂。我这里就画个草图吧。
假设字符串包含 m 个不同的字母，分别出现 a_1, ..., a_m 次。另外，为数字 C(a_i, 2) 写 b_i。
分三种情况：
- 情况1：四个错配形成两个相同的对，例如两个 a 和两个 b 被置换。
在本例中，我们有 sum{b_i * b_j : 1 <= i < j <= m} 个不同的字符串。这等于 (sum{b_i}^2 - sum{b_i ^2}) / 2，一个可以在 O(m) 时间内求值的表达式。
- 情况2：四个不匹配包含三个不同的字母，例如一个 a 与一个 b 配对，另一个 a 与一个 配对c.
在这种情况下，首先选择两对中共同的字母，假设它是第 i 个字母；然后必须选择其他两个字母。
所有a_i的总和写s，所有b_i的总和写t。如果我们从剩余的 s - a_i 个字母中选择任意两个字母，我们必须排除这两个字母相同的情况，这种情况有 t - b_i 个可能性。因此，有 C(s - a_i, 2) - (t - b_i) 种不同的方式来选择其他两个字母，因此有 b_i * (C(s - a_i, 2) - (t - b_i)) 种不同的字符串。在这种情况下，对所有 i 求和得出不同字符串的总数。它仍然可以在 O(m) 时间内评估。
- 案例 3：四个不同的字母，例如一个a和一个b一对，一个c和一个d 再组成一对。
思路是一样的。首先，考虑从所有 s 个字母中选择 4 个任意字母的可能性。那么我们要排除几种情况：
我。所有四个字母都相同，这有 sum{C(a_i, 4)} 个案例；
二。三个字母相同，第四个不同，这有sum{C(a_i, 3) * (s - a_i)}例；
三。两个字母相同，另外两个也相同，这正是情况1中计算出的数字；
四。两个字母相同，另外两个不同，这正是情况2中计算出的数字。
所以，从所有 s 个字母中选择四个不同字母的可能性总数是：C(s, 4) - [i] - [ii] - [iii] - [iv]。和以前一样，这个数字应该乘以 3 以产生不同字符串的数量，因为每个四元组给出 3 个不同的字符串。
总而言之，时间复杂度是O(m)，显然是最优的。