修改算法以在包含重复项的字符串中生成唯一排列

Question

如果我要使用交换和置换方法来生成排列，我知道如何处理重复项问题 here。

但是，我使用了一种不同的方法，我将当前字符放在任意两个字符之间，在开头和结尾，在没有当前角色。

我如何修改下面的代码，以便在包含重复项的字符串中仅提供唯一的排列

import java.util.ArrayList;

public class Permutations {
    public static void main(String[] args) {
        String str = "baab";
        System.out.println(fun(str, 0));
        System.out.println("number of Permutations =="+fun(str, 0).size());
    }

    static ArrayList<String> fun(String str, int index)
    {
        if(index == str.length())
        {
            ArrayList<String> al = new ArrayList<String>();
            al.add("");
            return al;
        }

        /* get return from lower frame */
        ArrayList<String> rec = fun(str, index+1);

        /* get character here */
        char c = str.charAt(index);

        /* to each of the returned Strings in ArrayList, add str.charAt(j) */
        ArrayList<String> ret = new ArrayList<String>();
        for(int i = 0;i<rec.size();i++)
        {
            String here = rec.get(i);
            ret.add(c + here);
            for(int j = 0;j<here.length();j++)
                ret.add(here.substring(0,j+1) + c + here.substring(j+1,here.length()));
        }
        return ret;
    }
}

此时，"bab"这样的字符串会产生如下输出，多次包含abb和bba。

[bab, abb, abb, bba, bba, bab]
number of Permutations ==6

PS : 我不想使用 hashmap/Set 来跟踪我的重复项并查看它们以前是否遇到过。

Answer 1

当您遍历字符串并在每个位置添加字符时，如果您在字符串中找到与您要插入的字符相同的字符，请在紧接其前插入新字符后中断。这意味着具有相同字符不止一次的字符串只能以一种方式形成（通过以相反的顺序插入），因此不会发生重复。

for(int j = 0;j<here.length();j++)
{
    if(here.charAt(j) == c)
        break;  
    ret.add(here.substring(0,j+1) + c + here.substring(j+1,here.length()));
}

解决这些涉及没有重复项的生成集的问题的一般方法是考虑一个属性每组重复项中只有一个，然后将其作为约束强制执行。例如，在这种情况下，约束是 "all duplicated characters are added in reverse order"（前向顺序同样有效，但您必须翻转循环方向）。对于顺序不重要的组合问题，约束可以是 "items in each list are in ascending order"。等等。

修改算法以在包含重复项的字符串中生成唯一排列

modifying algorithm to generate unique permutations in a string that contains duplicates

java

algorithm

recursion

permutation

dynamic-programming