使用算法列出包含重复字母的字符串的唯一排列

Question

例如，字符串“AAABBB”将有以下排列组合： “ABAABB”， “BBAABA”， “ABABAB”， 等等。

什么是生成这些排列组合的好算法？（它的时间复杂度是多少？）

- creampiedonut

---

生成所有排列将花费O(n!)的时间，其中n是字符串的长度。 - Karan Nagpal

请看这个链接：http://demonstrations.wolfram.com/PermutationsLehmerCodeAndLexicographicIndex/ - NinjaGaiden

@KaranNagpal：不会超过n!，而是取决于重复字母的数量。在AAABBB的例子中，有20个唯一的排列，而不是720个。 - Eric Duminil

你可以使用一个Set来跟踪结果，确保没有重复。 - BufBills

查看获取所有可能的唯一排列以获取一些有用的链接和JS实现。 - user6732794

Answer 1

这不是完整的答案，只是一个想法。

如果你的字符串仅由两个字母组成，我会选择二叉树和良好的递归函数。每个节点都是一个对象，包含父节点名称的前缀和后缀A或B，还有名称中A和B字母的数量。

节点构造器从父节点获取A和B的数量以及名称，因此只需要将A或B的数量加1并添加一个字母即可。

如果A或B的数量超过3（在A节点的情况下）或B节点中的数量超过3，或者它们的总和等于起始字符串的长度，则不会构造下一个节点。

现在，您可以收集2棵树的叶子节点（它们的名称），并得到所需的所有排列。

Scala或某些具有类似对象功能的函数式语言非常适合实现此算法。希望这有所帮助或激发一些想法。

- Zildyan

Answer 2

对于一个多重集合，你可以通过位置递归地解决（JavaScript代码）：

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

- גלעד ברקן

Answer 3

由于您实际上想要生成排列而不仅仅是计算它们的数量，因此您可以希望的最佳复杂度为O（输出大小）。

这里有一个很好的解决方案，使用Java编写，满足该限制并且运行非常快，同时消耗可忽略的空间。 它首先对字母进行排序以找到词典顺序最小的排列，然后按照词典顺序生成所有排列。

它被称为Pandita算法：https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

import java.util.Arrays;
import java.util.function.Consumer;


public class UniquePermutations
{
    static void generateUniquePermutations(String s, Consumer<String> consumer)
    {
        char[] array = s.toCharArray();
        Arrays.sort(array);
        for (;;)
        {
            consumer.accept(String.valueOf(array));

            int changePos=array.length-2;
            while (changePos>=0 && array[changePos]>=array[changePos+1])
                --changePos;

            if (changePos<0)
                break; //all done

            int swapPos=changePos+1;
            while(swapPos+1 < array.length && array[swapPos+1]>array[changePos])
                ++swapPos;

            char t = array[changePos];
            array[changePos] = array[swapPos];
            array[swapPos] = t;

            for (int i=changePos+1, j = array.length-1; i < j; ++i,--j)
            {
                t = array[i];
                array[i] = array[j];
                array[j] = t;
            }
        }
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        StringBuilder line = new StringBuilder();
        generateUniquePermutations("banana", s->{
            if (line.length() > 0)
            {
                if (line.length() + s.length() >= 75)
                {
                    System.out.println(line.toString());
                    line.setLength(0);
                }
                else
                    line.append(" ");
            }
            line.append(s);
        });
        System.out.println(line);
    }
}

这是输出结果：

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

- Matt Timmermans