解释 HashMap 的使用：编写一个方法来计算一个字符串的所有排列，该字符串的字符不一定是唯一的

Question

我遇到了下面的问题，没有完全理解HashMap的用法，包括map.put(c, count - 1)和map.put(c, count)?

这几行

谁能解释一下？

Permutations with Duplicates: Write a method to compute all permutations of a string whose characters are not necessarily unique. The list of permutations should not have duplicates.

public static HashMap<Character, Integer> getFreqTable(String s) {
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        for (char c : s.toCharArray()) {
            if (!map.containsKey(c)) {
                map.put(c, 0);
            }
            map.put(c, map.get(c) + 1);
        }
        return map;
    }
    
    public static void getPerms(HashMap<Character, Integer> map, String prefix, int remaining, ArrayList<String> result) {
        if (remaining == 0) {
            result.add(prefix);
            return;
        }
        
        for (Character c : map.keySet()) {
            int count = map.get(c);
            if (count > 0) {
                map.put(c,  count - 1);
                printPerms(map, prefix + c, remaining - 1, result);
                map.put(c,  count);
            }
        }
    }
    
    public static ArrayList<String> getPerms(String s) {
        ArrayList<String> result = new ArrayList<String>();
        HashMap<Character, Integer> map = getFreqTable(s);
        getPerms(map, "", s.length(), result);
        return result;
    }
    
    public static void main(String[] args) {
        String s = "aab";
        ArrayList<String> result = getPerms(s);     
        System.out.println(result.toString());
    }

更新感谢@trincot 的回答。

抱歉没说清楚。我了解 HashMap 的用法，但我一直在寻找将它用于此排列问题的原因，特别是输入中的 duplicate 数字。

比如使用HashMap和递归回溯的推理可以解决这个问题。我调试并跟踪了 getPerms 但我无法自然地理解回溯逻辑。回溯控制是否可以生成某些排列。但是我自己想不出来

下面是getPerms第一部分的踪迹。 X 表示 if 未执行，因为 a 或 b 为零。

aab -> aab,aba,baa
a2 b1  

"" 3   
  a:2
    a:1, 
     p(a,2)
        a:0
           p(aa,1)
           a: X aaa
           b: b=0
              p(aab,0)
                re: aab
              b=1
          a=1
        b:1
         b=0
          p(ab,1)
            a:0
              a=0
               p(aba,0)
                a:1
            b:0
             X abb
      a=2
   b:1

更新 2

下面是另一个示例，解释了为什么使用 HashMap 有助于

没有HashMap

   ab
    [aa, ab, ba, bb]
    
    ab
     a
      a b
       aa  
       bb
     b 
      b a 
       ba
       bb

和HashMap

ab   
[ab, ba]

这告诉我们使用 HashMap 和回溯避免输入中的重复

Answer 1

getFreqTable 将创建一个 HashMap，它的键是输入的字符，值是相应字符的出现次数。所以对于输入“aacbac”，这个函数returns一个可以描述如下的HashMap：

"a": 3 
"b": 1
"c": 2

这是 HashMap 的一种非常常见的用法。由于它提供了键（在本例中为字符）的快速查找和新键的快速插入，因此它是计算输入中每个字符出现次数的理想解决方案。

然后这个映射就是用来对select个字符进行一个排列。每当一个字符被 selected 用于排列时，它的计数器就会减少：

map.put(c,  count - 1);

并且当从递归回溯时（这将产生以该字符 c 作为前缀的所有排列），该计数器将再次恢复：

map.put(c,  count);

只要某个字符的计数器为 0，就不能再对它进行 select 排列。这就是为什么会出现这种情况：

if (count > 0)

我希望这能解释清楚。

附录

通过维护重复字母的计数，该算法避免人为区分这些重复字母，由此排列“aa”将被视为与“相同” aa”，只是因为这两个字母互换了。计数器的递减不介意重复项的确切来源（输入中的位置）。它只是“取其中之一，无论哪个”。

解释 HashMap 的使用：编写一个方法来计算一个字符串的所有排列，该字符串的字符不一定是唯一的

Explain the use of HashMap: Write a method to compute all permutations of a string whose characters are NOT necessarily unique

algorithm

recursion

dynamic-programming

recursive-backtracking

附录