arrays - 2 つの配列が互いの順列であるかどうかを確認する方法 (並べ替え機能なし)

Question

2つの異なる配列があり、配列内の2つの要素が等しいかどうかを確認することしかできない場合（つまり、要素を並べ替えるための比較関数（等号を超える）はありません）、確認する効率的な方法はありますか一方の配列が他方の配列の順列であるかどうか?

Answer 1

この実装は間違っているかもしれませんが、一般的な考え方は正しいはずです。私は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

Answer 2

オブジェクト タイプのハッシュが理にかなっている場合は、一時ハッシュ セットを使用して、配列 A からすべての項目を挿入できます。次に、配列 B を反復処理するときに、各項目が既に一時ハッシュ セットに含まれていることを確認します。

これは、単純なネストされた O(n^2) ループよりも高速 ( O(n) ) になるはずです。(より単純な単純なアルゴリズムがそれよりも優れている可能性がある、小規模または自明なデータセットを除く)

これには O(n) 余分なメモリが必要であり、このアプローチは重複がない場合 (または比較の一部としてカウントしたくない場合) にのみ機能することに注意してください。