列出具有重复字母的字符串的唯一排列的算法 [英] Algorithm to list unique permutations of string with duplicate letters

问题描述

例如，字符串"AAABBB"将具有以下排列: "ABAABB"， "BBAABA"， "ABABAB"， 等等

For example, string "AAABBB" will have permutations: "ABAABB", "BBAABA", "ABABAB", etc

什么是生成排列的好的算法? (它的时间复杂度是多少?)

What's a good algorithm for generating the permutations? (And what's its time complexity?)

推荐答案

对于多集，您可以按位置(JavaScript代码)递归求解:

For a multiset, you can solve recursively by position (JavaScript code):

function f(multiset,counters,result){
  if (counters.every(x => x === 0)){
    console.log(result);
    return;
  }

  for (var i=0; i<counters.length; i++){
    if (counters[i] > 0){
      _counters = counters.slice();
      _counters[i]--;
      f(multiset,_counters,result + multiset[i]);
    }
  }
}

f(['A','B'],[3,3],'');

这篇关于列出具有重复字母的字符串的唯一排列的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！