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

Question

如果我使用交换和排列方法生成排列，我可以处理重复的问题，如此处所示。

然而，我使用了一种不同的方法，在不包括当前字符的所有生成排列中，在任意两个字符之间，放置当前字符在起始位置和结束位置。

如何修改下面的代码，使其只返回一个包含重复字符的字符串的唯一排列。

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

注意：我不想使用哈希映射/集合来跟踪我的重复项并查看是否先前遇到。

- saltandwater

---

这不是来自Codechef的问题吗？ - Vaibhav Bajaj

@VaibhavBajaj，你好。正如我所说，我知道解决这个问题的方法，但我正在寻找对这个特定实现的修改。 - saltandwater

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

一种解决涉及没有重复项的生成集问题的通用方法是考虑每个重复项集合中只有一个特定属性，并将其作为约束条件。例如，在这种情况下，约束条件是“所有重复字符按相反顺序添加”（正向顺序同样有效，但您必须翻转循环方向）。对于顺序不重要的组合问题，约束条件可以是“每个列表中的项按升序排列”，等等。

- samgak

---

这太优雅了。绝对棒！ - saltandwater

刚有一个问题。假设我们的字符串是babcd。假设我已经生成了所有24个和abcd的排列，现在我要在每个位置插入b。根据你的逻辑，对于像abcd这样的字符串，在添加'b'后，我们生成1）babcd和2）abbcd，但之后就停止了。我的问题是，忽略像ab + 'b' + cd == abbcd这样的排列是有意义的。但是，我们如何忽略前面的组合，例如abc + b + d == abcbd呢？我画了递归图，看到这些是在另一个框架中生成的。但是所有这些是如何被处理的呢？ - saltandwater

这将通过生成acbd并将b插入第二个位置来处理，这不会违反规则。 - samgak

这意味着在字符串中，只能在已有的该字符实例之前添加该字符。例如，在字符串abcd中添加b以形成babcd是可以的。在字符串abcd中添加b以形成abcbd则不可以。 - samgak

另一种看待它的方式是：假设您对字符串abb进行排列，并获得两个重复的bab。其中一个是通过在ab的开头添加b形成的，另一个是通过在ba的末尾添加b形成的。禁止第二个可以消除重复。 - samgak