Algorithm to list unique permutations of string with duplicate letters

Question

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?)

Answer 1

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],'');