Блог

Я наткнулся на вопрос ниже, не до конца понимаю использование HashMap , включая строки map.put(c, count - 1) и map.put(c, count) ?

Кто-нибудь может объяснить?

Перестановки с дубликатами: Напишите метод для вычисления всех перестановок строки, символы которой не обязательно уникальны. Список перестановок не должен содержать дубликатов.

 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 resu<
    }
    
    public static void main(String[] args) {
        String s = "aab";
        ArrayList<String> result = getPerms(s);     
        System.out.println(result.toString());
    }
 

Обновить
Спасибо @trincot за его ответ.

Извините, что не уточнил. Я понимаю использование HashMap, но я искал обоснование для его использования для этого вопроса о перестановках, особенно с повторяющимися числами во входных данных.

Например, рассуждения о том, почему использование хэш-карты и рекурсивного отслеживания может решить эту проблему. Я отладил и отследил getPerms , но я не могу понять логику обратного хода естественным образом. Функция обратного отслеживания определяет, может ли быть сгенерирована какая-либо перестановка. Но я не смогу придумать это, если сделаю это сам.

Ниже приведен след первой части getPerms . X означает, если не выполняется, потому 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 помогает

без хэш-карты

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

с помощью хэш-карты

 ab   
[ab, ba] 
 

Это говорит об использовании хэш-карты и обратном отслеживании, чтобы избежать дублирования во входных данных

getFreqTable Будет создана хэш-карта, в которой в качестве ключей используются символы ввода, а в качестве значений-количество встречаемости соответствующего символа. Таким образом, для ввода «aacbac» эта функция возвращает хэш-карту, которую можно описать следующим образом:

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

Это очень распространенное использование хэш-карты. Поскольку он обеспечивает быстрый поиск ключа (в данном случае символа) и быструю вставку нового ключа, это идеальное решение для подсчета появления каждого символа во входных данных.

Затем эта карта используется для выбора символов для перестановки. Всякий раз, когда символ выбирается для использования в перестановке, его счетчик уменьшается:

 map.put(c,  count - 1);
 

И при возврате от рекурсии (которая приведет ко всем перестановкам с этим символом c в качестве префикса) этот счетчик снова восстанавливается:

 map.put(c,  count);
 

Всякий раз, когда счетчик для определенного символа равен 0, он больше не может быть выбран для перестановки. Вот почему существует это условие:

 if (count > 0)
 

Я надеюсь, что это все объясняет.

Дополнение

Поддерживая количество повторяющихся букв, этот алгоритм позволяет избежать искусственного различия между этими повторяющимися буквами, при котором перестановка «aa» будет считаться такой же, как «aa», только потому, что эти две буквы были заменены друг на друга. Уменьшение счетчика не имеет значения, откуда именно взялся этот дубликат (позиция на входе). Это просто «берет одного из них, неважно какого».