检查两个字符串是否是Python中彼此的排列

我正在检查是否有两个字符串a并且b是彼此的排列,我想知道在Python中执行此操作的理想方法是什么.从Python的禅宗,"应该有一个 - 最好只有一个 - 显而易见的方式",但我看到至少有两种方式:

sorted(a) == sorted(b)

和

all(a.count(char) == b.count(char) for char in a)

但是第一个是慢的时候(例如)第一个char a无处可去b,而第二个是实际排列时更慢.

有更好的方法(无论是更多的Pythonic,还是平均更快的意义上)的方式呢？或者我应该从这两个中选择,具体取决于我期望最常见的情况？

1> namin..：

---

这是一种O(n)的方法,渐近地比你建议的两种方式更好.

import collections

def same_permutation(a, b):
    d = collections.defaultdict(int)
    for x in a:
        d[x] += 1
    for x in b:
        d[x] -= 1
    return not any(d.itervalues())

## same_permutation([1,2,3],[2,3,1])
#. True

## same_permutation([1,2,3],[2,3,1,1])
#. False

---

正如namin所说,它渐近更好 - 而且你不需要测量,只是为了证明它对O(n log(n))是O(n).

2> S.Lott..：

---

"但是当(例如)a的第一个字符在b中无处时,第一个更慢."

这种退化案例的性能分析并不是一个好主意.想到各种不起眼的特殊情况,这是一个失去时间的老鼠洞.

只进行O型"整体"分析.

总的来说,排序是O(n log(n)).

该a.count(char) for char in a溶液是Ô(Ñ ²).每个计数通过都是对字符串的全面检查.

如果一些模糊的特殊情况碰巧更快 - 或更慢,那可能很有趣.但只有当你知道你不明显的特殊情况的频率时才重要.在分析排序算法时,重要的是要注意,相当数量的排序涉及的数据已经按照正确的顺序(通过运气或巧妙的设计),因此对预排序数据的排序性能很重要.

在你不起眼的特殊情况下("a的第一个字母在b中无处可去")这是否经常发生？如果它只是你想到的特殊情况,请把它放在一边.如果这是关于您的数据的事实,那么请考虑它.

3> 小智..：

---

启发式地,你可能最好根据字符串大小将它们分开.

伪代码:

returnvalue = false
if len(a) == len(b)
   if len(a) < threshold
      returnvalue = (sorted(a) == sorted(b))
   else
       returnvalue = naminsmethod(a, b)
return returnvalue

如果性能至关重要,字符串大小可以大或小,那么这就是我要做的.

根据输入大小或类型分割这样的东西是很常见的.算法有不同的优点或缺点,使用另一个更好的方法是愚蠢的......在这种情况下,Namin的方法是O(n),但是具有比O(n log n)排序方法更大的常数因子.

---

而不是设置returnvalue,只需返回.

4> Robert Gambl..：

---

我认为第一个是"明显"的方式.它更短,更清晰,并且在许多情况下可能更快,因为Python的内置排序是高度优化的.

5> ʞɔıu..：

---

你的第二个例子实际上不会起作用:

all(a.count(char) == b.count(char) for char in a)

仅当b不包含不在a中的额外字符时才会起作用.如果字符串中的字符重复,它也会重复工作.

如果您想知道两个字符串是否是相同唯一字符的排列,只需执行以下操作:

set(a) == set(b)

要纠正你的第二个例子:

all(str1.count(char) == str2.count(char) for char in set(a) | set(b))

set()对象重载按位OR运算符,以便它将计算为两个集合的并集.这将确保您仅为每个字符循环遍历两个字符串的所有字符.

也就是说,sorted()方法更简单,更直观,也是我会使用的方法.