I'm trying to calculate the permutation of the word banana, but the code I made calculates it incorrectly, it doesn't take into account the letters that are repeated in the word, in words that the letters are not repeated works normally.

List<String> permute(String word, int l, int r) {
  List<String> output = [];
  if (l == r) {
    print(word);
    output.add(word);
  } else {
    for (int i = l; i <= r; i  ) {
      word = swap(word, l, i);
      output = output   permute(word, l   1, r);
      word = swap(word, l, i);
    }
  }
  return output;
}

String swap(String a, int i, int j) {
  List<String> charArray = a.split('');
  String temp = '';

  temp = charArray[i];
  charArray[i] = charArray[j];
  charArray[j] = temp;
  return charArray.join();
}

In my current code I get 720 possibilities, but according to the calculators it should be 60 because of the letters that are repeated, how can I solve this?

CodePudding user response：

List<List<T>> getPermutations<T extends Object>(List<T> list) {
  if (list.length > 2) {
    var _result = <List<T>>[];
    for (var i = 0; i < list.length; i  ) {
      var _set = list.toList();
      var _e = _set.removeAt(i);
      _result.addAll(getPermutations(_set).map((e) => e..insert(0, _e)));
    }
    return _result;
  }
  if (list.length < 2) return [list];

  return [list, [list[1],list[0]]];
}

void makePermutationsFrom(String word) {
  final result = getPermutations(word.split('')).map((e) => e.join()).toSet();
  print(result.length);
  print(result);
}

void main(List<String> args) {
  makePermutationsFrom('banana');
}

Output:

60
{banana, banaan, bannaa, baanna, baanan, baaann, bnaana, bnaaan, bnanaa, bnnaaa, abnana, abnaan, abnnaa, abanna, abanan, abaann, anbana, anbaan, anbnaa, anabna, anaban, ananba, ananab, anaabn, anaanb, annbaa, annaba, annaab, aabnna, aabnan, aabann, aanbna, aanban, aannba, aannab, aanabn, aananb, aaabnn, aaanbn, aaannb, nbaana, nbaaan, nbanaa, nbnaaa, nabana, nabaan, nabnaa, naabna, naaban, naanba, naanab, naaabn, naaanb, nanbaa, nanaba, nanaab, nnbaaa, nnabaa, nnaaba, nnaaab}

CodePudding user response：

it turned out that if you filter the list before returning the problem is solved

return output.toSet().toList();

or

if (!output.contains(word)) {
  output = output   permute(word, l   1, r);
}