代码之家 › 专栏 › 技术社区 › learner

Java中给定字符的可能组合

java

-1

learner · 技术社区 · 7 年前

我正在做一个任务,我需要找到所有可能的字符组合。

"{a | b} {c | d} e {f | } g {h | i}"

在这里输入字符 {} 指示由管道分隔的可选字符 | 那个位置的符号。因此,对于这个输入,可能的输出如下:

a c e f g h
a c e g h
b c e f g h
b c e g h
a d e f g h
a d e g h
b d e f g h
b d e g h
a c e f g i
a d e f g i
a d e g i
b c e f g i
b d e f g i
b d e g i

我试过使用for循环,但不知道如何找到所有可能的组合?

更新:

public static void main(String[] args) {
        String in = "{a|b} {c|d} e {f|} g {h|i}";
        String[] array = in.split(" ");
        for (int i = 0; i < array.length; i++) {
            String data = array[i];
            recursivecall(data);
        }
    }

    private static void recursivecall(String data) {
        if (!data.startsWith("{")) {
            System.out.println(data);
        } else {
            String set = data.replace("{", "").replaceAll("}", "");
            System.out.println("set = " + set);
            String[] elements = set.split("\\|");
            for (int i = 0; i < elements.length; i++) {
                recursivecall(elements[i]);
            }
        }
    }

我得到的输出为:

a
b
c
d
e
f
g
h
i

2 回复 | 直到 7 年前

Dawood ibn Kareem 7 年前

为此,使用递归是最简单的;因此您将编写一个可能调用自身的方法。逻辑是这样的。

如果输入不包含任何 {
否则,只选择其中一个 { } 集合。如果有嵌套对,则选择一个没有任何嵌套对的放在里面。
遍历所选元素中的元素,调用方法,其中参数是用元素替换集合的结果。

"a{b|c|d}e" ,您将遍历 {} 设置并递归到方法中三次-每次的参数都是 "abe" , "ace" "ade" .

递归将确保为每个准备好了。它处理每个集合中的任意数量的元素,以及集合的任意级别嵌套。

John McClane 7 年前

{f | } )被认为是有效的变体。不允许使用嵌套大括号。

这是非递归解。其中最重要的部分是 while 内部循环 compose() combList for 内部循环 虽然 循环以获取相同的组合集,但顺序不同。

import java.util.*;

public class CharCombinations {
    private final String input;
    private int pos;

    private CharCombinations(String input) {
        this.input = input;
    }

    private String[] checkChoice(String[] choice) {
        String[] chars = new String[choice.length];
        int i = 0;
        for (String s : choice) {
            String t = s.trim();
            switch (t.length()) {
                case 0:
                    break;
                case 1:
                    if (Character.isLetter(t.charAt(0))) // internationalized
                        break;
                default:
                    throw new IllegalArgumentException("Not a letter: " + t);
            }
            chars[i++] = t;
        }
        return chars;
    }

    private String[] nextCharChoice() {
        while (pos < input.length() && input.charAt(pos) == ' ')
            pos++;
        if (pos == input.length())
            return null;
        char c = input.charAt(pos++);
        if (c != '{')
            return checkChoice(new String[]{String.valueOf(c)});
        int closBracePos = input.indexOf('}', pos);
        if (closBracePos < 0)
            throw new IllegalArgumentException("No matching delimiter: "
                + input.substring(--pos));
        String delimChoice = " " + input.substring(pos, closBracePos) + " ";
        if (delimChoice.trim().isEmpty())
            throw new IllegalArgumentException("Empty variants list");
        pos = ++closBracePos;
        return checkChoice(delimChoice.split("\\|"));
    }

    private List<String> compose() {
        List<String> combList = new ArrayList<>(1);
        combList.add("");
        String[] choices;
        while ((choices = nextCharChoice()) != null) {
            List<String> newCombList = new ArrayList<>(combList.size() * choices.length);
            for (String c : choices)
                for (String comb : combList)
                    newCombList.add(comb + c);
            combList = newCombList;
        }
        return combList;
    }

    public static List<String> combinations(String input) {
        return new CharCombinations(input).compose();
    }

    public static void main(String[] args) {
        for (String s : combinations("{a | b} {c | d} e {f | } g {h | i}"))
            System.out.println(s);
    }
}