Java生成字符排列组合时如何限制各字符使用次数不超过原有存量?
代码修改方案
核心思路是先统计原字符数组中每个字符的可用次数,递归生成组合时跟踪每个字符的已使用量,超过存量的字符不再选用,同时增加长度合法性校验,要生成的组合长度不能超过原数组总字符数。
修改后完整代码
import java.util.HashMap; import java.util.Map; public class Words { static char[] alphabet = "ab".toCharArray(); // 存储每个字符的最大可用次数 static Map<Character, Integer> charMaxCount = new HashMap<>(); // 原数组总字符数,用于校验生成长度合法性 static int totalCharCount; // 静态块初始化统计数据 static { totalCharCount = alphabet.length; for (char c : alphabet) { charMaxCount.put(c, charMaxCount.getOrDefault(c, 0) + 1); } } /** * 递归生成组合 * @param sb 存储当前生成的字符串 * @param n 当前填充到的索引位置 * @param usedCount 记录每个字符已使用的次数 */ static void generate(StringBuilder sb, int n, Map<Character, Integer> usedCount) { if (n == sb.length()) { System.out.println(sb.toString()); return; } for (char letter : charMaxCount.keySet()) { // 校验当前字符还有可用额度 if (usedCount.getOrDefault(letter, 0) < charMaxCount.get(letter)) { // 标记使用 usedCount.put(letter, usedCount.getOrDefault(letter, 0) + 1); sb.setCharAt(n, letter); // 递归下一个位置 generate(sb, n + 1, usedCount); // 回溯,撤销使用标记 usedCount.put(letter, usedCount.get(letter) - 1); } } } public static void main(String[] args) { StringBuilder sb = new StringBuilder(); // 生成的长度范围可自定义,注意不能超过原数组总字符数,否则无结果 for (int length = 2; length <= 3; length++) { if (length > totalCharCount) { continue; } sb.setLength(length); // 每次生成新长度的组合时,重置使用计数 generate(sb, 0, new HashMap<>()); } } }
改动说明
- 新增了字符频率统计逻辑,预先统计原数组中每个字符的可使用上限以及总字符数
- 递归方法新增
usedCount参数跟踪每个字符的已使用量,每次选字符前先校验剩余可用额度 - 增加了回溯逻辑,递归返回后回滚字符的使用计数,不影响其他分支的统计
- 新增长度合法性校验,要生成的组合长度超过原数组总字符数时直接跳过,避免无意义的递归
- 遍历字符时改为遍历去重后的字符集合,避免重复遍历相同字符影响效率
测试示例
如果将alphabet改为"aab"(a存量2,b存量1),生成长度为2和3的组合时,输出结果如下:
长度2结果:aa、ab、ba
长度3结果:aab、aba、baa
完全符合字符使用次数不超过存量的要求。
内容的提问来源于stack exchange,提问作者Andrés
相关产品推荐
相关产品推荐

