String combinations with multi-character replaceme

问题:

There's another Stack Overflow post that was created for an algorithm related to vehicle registration numbers...

According to the entered license plate (eg. ABC123) and a list of replacement values (eg 1 replaced by I). I need to get all possibles combinations.

The answer by @ArturoMenchaca is perfect for C#, but I'd like it in Java, but given that 'yield' is not available I really can't wrap my head around how to convert it.

How would you translate this code to Java?

public static IEnumerable<string> Combinations(string s, Dictionary<char, char> replacements)
{
    return Combinations(s, replacements, 0, string.Empty);
}

private static IEnumerable<string> Combinations(string original, Dictionary<char, char> replacements, int index, string current)
{
    if (index == original.Length) yield return current;
    else
    {
        foreach (var item in Combinations(original, replacements, index + 1, current + original[index]))
            yield return item;

        if (replacements.ContainsKey(original[index]))
            foreach (var item in Combinations(original, replacements, index + 1, current + replacements[original[index]]))
                yield return item;
    }
}

You would call then call the method like this..

Dictionary<char, char> dict = new Dictionary<char,char>();
dict['1'] = 'I';
dict['3'] = 'B';
dict['A'] = 'H';
dict['O'] = '0';
dict['0'] = 'O';

var combs = Combinations("ABC123", dict);

回答1:

Java doesn't have a feature for iterating values using "push" logic, like the C# yield return does.

Java only supports "pull" logic, using Enumeration, Iterator, or Spliterator (what Stream uses).

If you have the memory for it, you could of course "push" all the combinations into an ArrayList, then "pull" values from there. Converting the yield return logic into list.add() calls is easy, so I'll assume you don't want that.

The Java equivalent of IEnumerable is Iterable, so you need an Iterator implementation.

The code below will do that. It is based on my answer to another question, so please read that answer for an explanation of the overall logic, but basically, your example would be like generating combinations of characters in this jagged array:

{{'A', 'H'}, {'B'}, {'C'}, {'1', 'I'}, {'2'}, {'3', 'B'}}

In the code below, that jagged array is the textChars array, but instead of using char[] it uses a String, because a String is really just a read-only char[].

public static Iterable<String> combinations(String text, String... replacements) {
    Map<Character, String> repl = new HashMap<>();
    for (String r : replacements)
        if (repl.putIfAbsent(r.charAt(0), r) != null)
            throw new IllegalArgumentException("Duplicate replacement: [" + repl.get(r.charAt(0)) + "] vs [" + r + "]");
    String[] textChars = new String[text.length()];
    long count = 1;
    for (int i = 0; i < textChars.length; i++) {
        textChars[i] = repl.getOrDefault(text.charAt(i), text.substring(i, i+1));
        count = Math.multiplyExact(count, textChars[i].length());
    }
    long comboCount = count;
    return () -> new Iterator<>() {
        private long combo = 0;
        @Override
        public boolean hasNext() {
            return (this.combo < comboCount);
        }
        @Override
        public String next() {
            if (this.combo >= comboCount)
                throw new NoSuchElementException();
            long c = this.combo++;
            char[] buf = new char[textChars.length];
            for (int i = buf.length - 1; i >= 0; i--) {
                buf[i] = textChars[i].charAt((int) (c % textChars[i].length()));
                c /= textChars[i].length();
            }
            return new String(buf);
        }
    };
}

Test

combinations("ABC123", "1I", "3B", "AH", "O0", "0O").forEach(System.out::println);

Output

ABC123
ABC12B
ABCI23
ABCI2B
HBC123
HBC12B
HBCI23
HBCI2B