java - 通过删除生成所有可能的排列

Question

我需要通过删除字符串的一个或多个大字符来生成所有可能的唯一排列，而小字符应保持不变。

输入示例:

AalAADBdBBDkCeCCA

现在我需要生成所有可能的排列

• 一次或多次删除一个大字符
• 结合删除 1 到 n 个 BIG 字符，每个字符删除 0 到 m 次(n = 输入中直接字符的数量，m = 字符出现的次数)。
• 保留小字符不变

我只对独特的排列感兴趣，也就是说，如果第二个或第三个(已修复!最初我写了第一个和第二个)A被删除没有区别。当然，如果删除第一个或最后一个 A，结果会有所不同。

排列示例:

AalAADBdBBDkCeCCA // original input also counts as permutation
AalAADBdBB kCeCCA // last D removed
 alAAD dBBDkCeCCA // first A and first B removed
Aal  D dBBDkCeC A  // second and third A removed, first B and last C removed

我正在使用 Guava ，以防万一这有帮助。一个简单的 Java 解决方案也可以。

如果这种排列有一个名称，以及一些给出唯一排列总数的数学公式，我也会感兴趣，这样人们就可以验证排列算法结果(至少在排列的正确数量方面)。

该示例是一个简化的问题，可以假设输入已经可以作为字符列表或任何其他预解析格式而不是合并的字符串使用。

感谢您对此的任何提示!

更新:

我想我找到了解决方案，欢迎反馈。想法:提取每个大字符的索引(位置)。将它们放在一个集合中，创建该集合的幂集P。这给出了可能删除的所有排列(包括重复，例如 1,2 和 2,1 以及如果 1 = 2 = 相同的大字符)

Answer 1

我对你的更新有一些类似的想法，但也许你的结果比我的更优雅，因为我没有过滤掉任何东西

我首先制作了一种包含字符串中所有大写字母的二进制表(我们可以忽略小写字母，因为它们从未被触及)。

从非常简单的示例开始，然后逐步完善。在二进制表中，0 表示保留该字符，1 表示删除该字符。

例如对于 A 的字符串(或任何只有 1 个大写字母的字符串，例如 aaaAa)2 种排列

A
0
1

对于 AB(或具有 2 个大写字母 aaaAaBbb 的字符串)4 种排列

AB
00
10
01
11

对于 ABC 8 排列

ABC
000
100
010
110
001
101
011
111

ABCD 16 排列

ABCD
0000
1000
0100
1100
0010
1010
0110
1110
0001
1001
0101
1101
0011
1011
0111
1111

您会看到这些是 2^1, 2^2, 2^3, 2^4 2^numberOfUppercaseCharacters

这为您提供了排列总数，而无需消除重复问题。您可能会不优雅地实现一种蛮力方法，该方法循环遍历每个字符位置并在该字符处关闭 - 并将输出字符串保存到一个集合中。因为它在一组中，所以不会添加重复项。

所以获取你的输入字符串 解析它以获取每个大写字符的索引

在上面的二进制表中，从概念上考虑用字符串中的索引位置替换 A B C。

所以

对于字符串 aaAbbBb，我们有索引 2 和 5(基于 0 的索引)

A B
_ _
0 0
1 0
0 1
1 1

变成了

2 5
_ _
0 0
1 0
0 1
1 1

因此，如果我们采用最多 2^numOfUppercase 的二进制数表示并删除应该起作用的关联值。请注意，下面的示例对字符串和大写索引列表进行了硬编码。至少你有一些东西可以尝试并检查你的解决方案。

请注意，不知道这种方法的上限 - 很可能会因为大写字符的长字符串作为排列的大型二进制表示而失败。

示例如下:

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;


public class StringProcessing {


public static void main(String[] args) {
    // TODO Auto-generated method stub
    StringProcessing sp = new StringProcessing();
    sp.setUpProcessing();

}

public void setUpProcessing() {
    String input = "aaABCDcs";

    //Populate with indexes of Uppercase letters (loop though each char and check if [A-Z])
    ArrayList<Integer> indexes = new ArrayList<Integer>();
    indexes.add(2);
    indexes.add(3);
    indexes.add(4);
    indexes.add(5);

    Set<String> permutationStore = new HashSet<String>();
    BigInteger permutations = BigInteger.valueOf(2).pow(indexes.size());  //2^numOfUppercaseChars


    int maxSize = getMaxLength(permutations); //Need this for padding binary with 0

    for (BigInteger index = BigInteger.ZERO; index.compareTo(permutations) < 0;  index = index.add(BigInteger.ONE)) {
        String binary = index.toString(2);
       // System.out.println(permutations + " " + index + " " + binary + ", for string: " + input); //NumOf Permutations, currentPermutation, binaryRepresentation

        int lastIndex = binary.length() -1;
        StringBuilder currentString = new StringBuilder(input);
        String permutationString = process(lastIndex, binary, currentString, indexes, maxSize);
        permutationStore.add(permutationString);
        System.out.println(permutations + " " + index + "    " + binary + ", for string: " + input + ", Stored: " + permutationString);
    }

    System.out.println("");
    for(String s : permutationStore) {
        System.out.println(s);
    }

}

public int getMaxLength(BigInteger permutations) {
   BigInteger zeroBased = permutations.subtract(BigInteger.ONE);
   return  zeroBased.toString(2).length();
}

public String process(int lastIndex, String binary, StringBuilder currentString, ArrayList<Integer> indexes, int maxSize) {
    int indexFound = binary.lastIndexOf('1', lastIndex);

    if (indexFound == -1) {
        return currentString.toString();
    }
    int padding =  maxSize - binary.length(); //Add leading "0's" to binary 

    int index = indexFound + padding;
    int charPos = indexes.get(index);

    currentString.deleteCharAt(charPos);
    process(indexFound-1, binary, currentString, indexes, maxSize);

    return currentString.toString();
}

}