查找字符串的所有唯一的排列而不会产生重复的 [英] Finding all the unique permutations of a string without generating duplicates

问题描述

查找字符串的所有排列是一个著名的斯坦豪斯 - 约翰逊特罗特算法。但是，如果字符串包含重复字符如
AABB，
然后可能的独特的组合将是4！/（2！×2！）= 6

Finding all the permutations of a string is by a well known Steinhaus–Johnson–Trotter algorithm. But if the string contains the repeated characters such as
AABB,
then the possible unique combinations will be 4!/(2! * 2!) = 6

实现这一目标的方法之一是，我们可以将其存储在一个数组左右，然后删除重复的。

One way of achieving this is that we can store it in an array or so and then remove the duplicates.

有没有更简单的方法来修改约翰逊的算法，所以，我们从来没有产生重复排列。 （在最有效的方法）

Is there any simpler way to modify the Johnson algorithm, so that we never generate the duplicated permutations. (In the most efficient way)

推荐答案

使用下面的递归算法：

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;
}

正如你看到的，它很容易

As you see, it is very easy

这篇关于查找字符串的所有唯一的排列而不会产生重复的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！