c - 查找字符串的所有唯一排列而不生成重复项

通过众所周知的Steinhaus-Johnson-Trotter算法查找字符串的所有排列。但是，如果字符串包含重复的字符，例如
AABB，
那么可能的唯一组合将是4!/(2!* 2!)= 6

实现此目的的一种方法是，我们可以将其存储在大约一个数组中，然后删除重复项。

有没有更简单的方法来修改Johnson算法，这样我们就永远不会生成重复的排列。 (以最有效的方式)

最佳答案

使用以下递归算法:

PermutList Permute(SymArray fullSymArray){
    PermutList resultList=empty;
    for( each symbol A in fullSymArray, but repeated ones take only once) {
       PermutList lesserPermutList=  Permute(fullSymArray without A)
       for ( each SymArray item in lesserPermutList){
            resultList.add("A"+item);
       }
    }
    return resultList;
}

如您所见，这非常容易