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

我正在使用番石榴，以防万一。一个普通的 Java 解决方案也可以。

如果有这种排列的名称和一些给出唯一排列总量的数学公式，我也会感兴趣，因此可以验证排列算法的结果（至少在正确的排列数量方面）。

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

感谢您对此的任何提示！

更新：

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

score 1 · Accepted Answer

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

我首先制作了一个字符串中所有大写字母的二进制表（我们可以忽略小写字母，因为它们永远不会被触及）。

从非常简单的示例开始，然后逐步进行。在二进制表中，0 表示将字符留在原处，1 表示将其删除。

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

A
0
1

对于 AB（或带有 2 个大写字母 aaaAaBbb 的字符串）4 个排列

对于 ABC 8 排列

对于 ABCD 16 排列

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

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

因此，将您的输入字符串解析以获取每个大写字符的索引

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

所以

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

变成

因此，如果我们将二进制数表示为 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();
}

}

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

1 回答 1

Related

Reference