4

如果我有两个不同的数组，而我所能做的就是检查数组中的两个元素是否相等（换句话说，没有比较函数（除了相等）来对元素进行排序），是否有任何有效的方法来检查一个数组是否是另一个数组的排列？

4

7 回答 7

5

像 Jared 的蛮力解决方案这样的词应该有效，但它是 O(n^2)。

如果元素是可散列的，则可以实现 O(n)。

def isPermutation(A, B):
    """
    Computes if A and B are permutations of each other.
    This implementation correctly handles duplicate elements.
    """
    # make sure the lists are of equal length
    if len(A) != len(B):
        return False

    # keep track of how many times each element occurs.
    counts = {}
    for a in A:
        if a in counts: counts[a] = counts[a] + 1
        else: counts[a] = 1

    # if some element in B occurs too many times, not a permutation
    for b in B:
        if b in counts:
            if counts[b] == 0: return False
            else: counts[b] = counts[b] - 1
        else: return False

    # None of the elements in B were found too many times, and the lists are
    # the same length, they are a permutation
    return True

根据字典的实现方式（作为哈希集与树集），这将需要 O(n) 用于哈希集或 O(n log n) 用于树集。

于 2012-04-04T02:13:52.483 回答
3

这个实现可能是错误的，但总体思路应该是正确的。我刚刚开始使用python，所以这也可能是一种非常规或非pythonic的风格。

def isPermutation(list1, list2):
    # make sure the lists are of equal length
    if (len(list1) is not len(list2)):
        return False

    # keep track of what we've used
    used = [False] * len(list1)

    for i in range(len(list1)):
        found = False

        for j in range(len(list1)):
            if (list1[i] is list2[j] and not used[j]):
                found = True
                used[j] = True
                break

        if (not found):
            return False

    return True
于 2012-04-04T01:56:22.340 回答
0

如果您的对象类型的散列有意义，您可以使用临时散列集插入数组 A 中的所有项目。然后在遍历数组 B 时，确保每个项目都已经在临时散列集中。

这应该比简单的嵌套 O(n^2) 循环更快（ O(n) ）。（除了小型或琐碎的数据集，更简单的朴素算法可能会胜过它）

请注意，这将占用 O(n) 额外的内存，并且这种方法仅在您没有重复项（或不想将它们计为比较的一部分）时才有效

于 2012-04-04T01:49:12.050 回答
0

假设两个数组的长度相等，并且一个元素可能多次出现在数组中，您可以创建另一个长度相同的 boolean 类型的数组，初始化为 false。

然后遍历其中一个数组并为每个元素检查该元素是否出现在另一个数组中相应布尔值为假的位置——如果出现，则将相应的布尔值设置为真。如果第一个数组中的所有元素都可以这样计算，那么两个数组相等，否则不相等（并且您发现至少有一个差异）。

内存需求为O(n)，时间复杂度为O(n^2)

于 2012-04-04T02:02:04.440 回答
0

因为我还不能发表评论（没有足够的代表），所以我将在这里提到这一点作为对其他答案之一的回复：Python 的 set() 不能很好地处理对象。

如果您有可散列的对象，则此代码应该适合您：

def perm(a, b):
        dicta = {}; dictb = {}
    for i in a:
            if i in dicta: dicta[i] += 1
            else: dict[i] = 1
    for i in b:
        if i in dictb: dictb[i] += 1
        else: dict[i] = 1
    return dicta == dictb

构造 a 中对象的 hashmap 以及它们出现的次数。对于 b 中的每个元素，如果该元素不在 hashmap 中或出现不匹配，则它不是排列。否则，它是一个排列。

>>> perm([1,2,4], [1,4,2])
True
>>> perm([1,2,3,2,1], [1,2,1,2,3])
True
>>> perm([1,2,4], [1,2,2])
False
于 2012-04-04T02:10:40.257 回答
0

// C# 代码，l1 和 l2 是非排序列表

        private static bool AreListContainedEachOther(List<int> l1, List<int> l2)
        {​
            if (l1.Equals(null) || l2.Equals(null))​
                return false;​
​
            bool isContained = true;​
​
            foreach (int n in l1)​
            {​
                if (!l2.Contains(n))​
                    return false;​
            }​
​
            return isContained;​
        }
于 2019-07-16T23:45:13.120 回答
0

前面的答案很棒。只需添加，在 Python 中，就像在 Python 中一样，它真的很简单。

如果 ：

  1. 数组的长度相等。
  2. 数组 B 中没有不存在于数组 A 中的元素。
  3. 没有任何元素在数组 B 中的出现次数比在数组 A 中的次数多。

数组是彼此的排列

from collections import defaultdict


def is_permutation(a, b):
    if len(a) != len(b):
        return False
    counts = defaultdict(int)
    for element in a:
        counts[element] += 1
    for element in b:
        if not counts[element]:
            return False
        counts[element] -= 1
    return True
于 2020-03-01T07:58:07.540 回答