Рекурсивная функция для генерации всех комбинаций прописных букв в слове

Question

Кто-нибудь знает логику создания рекурсивной функции для генерации всех комбинаций прописных букв в данном слове? Я пытаюсь сделать это в Java ... Например, дать ему слово "Бен", и он выводит:

Ben
bEn
beN
BEn
BeN
bEN
BEN

Но за любое слово ... любая помощь приветствуется!

Answer 1

В псевдокоде (ну, на самом деле, на Python, но он настолько близок к псевдокоду, насколько это возможно в реальном языке):

def recurse (pref,suff):
    # If no characters left, just print prefix.

    if suff == "":
            print pref
            return

    # Otherwise add lowercase of first suffix letter to prefix
    # and recur with that and the remainder of the suffix.
    # Then do the same for uppercase.
    # If you wanted smarts, this is where you'd detect if the
    # upper and lower were the same and only recurse once.

    recurse (pref + suff[0:1].lower(), suff[1:])
    recurse (pref + suff[0:1].upper(), suff[1:])

# Test the function with "Ben".

recurse ("","beN")

Это выводит:

ben
beN
bEn
bEN
Ben
BeN
BEn
BEN

Как это работает, относительно просто (большинство рекурсивных решений - это когда вы их понимаете).

Начальное условие - когда у вас нет префикса и суффикса, который вам нужно перебрать, чтобы получить все различные возможности смешанного регистра.

Условие завершения - просто, когда не осталось букв для выбора двух вариантов.

Каждое другое условие вы просто повторяете дважды, один раз с буквой в нижнем регистре и один раз с верхним.

Имейте в виду, что это не будет правильно обрабатывать не-буквенные символы, это только для того, чтобы показать вам, как работает логика. Например, для строки «a!» Вы получите четыре строки вывода, хотя «!» одинаково в верхнем и нижнем регистре.

Для правильной обработки этого вы должны использовать:

def recurse (pref,suff):
    # If no characters left, just print prefix.

    if suff == "":
            print pref
            return

    # Otherwise add lowercase of first suffix letter to prefix
    # and recur with that and the remainder of the suffix.
    # Then do the same for uppercase.
    # We also detect if the upper and lower are the same
    # and only recurse once.

    if suff[0:1].lower() == suff[0:1].upper():
        recurse (pref + suff[0:1], suff[1:])
    else:
        recurse (pref + suff[0:1].lower(), suff[1:])
        recurse (pref + suff[0:1].upper(), suff[1:])

# Test the function with "Ben!!!".

recurse ("","beN!!!")

, который дает только 8 строк вместо 64.

Эквивалент в Java, поскольку это не домашняя работа, это:

public class test {
    public static void recurse (String pref, String suff) {
        if (suff.length() == 0) {
            System.out.println (pref);
            return;
        }

        String first = suff.substring(0,1);
        String rest = suff.substring(1);

        if (first.toLowerCase().equals(first.toUpperCase())) {
            recurse (pref + first, rest);
        } else {
            recurse (pref + first.toLowerCase(), rest);
            recurse (pref + first.toUpperCase(), rest);
        }
    }

    public static void main(String[] args) {
        recurse ("","beN!!!");
    }
}

Answer 2

Вот подсказка:

000 # ben
001 # beN
010 # bEn
011 # bEN
100 # Ben
101 # BeN
110 # BEn
111 # BEN

EDIT:

Еще несколько подсказок:

• есть 2 ^ n комбинация (где n длина вашей строки);
• Вы можете использовать String toCharArray()

РЕДАКТИРОВАТЬ 2:

Так как это не домашняя работа, вот небольшая демонстрация того, как вы могли бы сделать это (итеративно) в Java:

import java.util.*;

public class Main {   
    public static void main(String[] args) {
        int n = 1;
        for(String combination : new CombinationIterator("ben")) {
            System.out.println((n++)+" = "+combination);
        }
        System.out.println("-------------");
        n = 1;
        for(String combination : new CombinationIterator("test?", "TEST!")) {
            System.out.println((n++)+" = "+combination);
        }
    }
}

class CombinationIterator implements Iterator<String>, Iterable<String> {

    protected final String zeros;
    protected final String ones;
    private int current;

    public CombinationIterator(String word) {
        this(word.toLowerCase(), word.toUpperCase());
    }

    public CombinationIterator(String zeros, String ones) {
        this.zeros = zeros;
        this.ones = ones;
        this.current = 0;
    }

    @Override
    public boolean hasNext() {
        return current < (int)Math.pow(2, zeros.length());
    }

    @Override
    public Iterator<String> iterator() {
        return this;
    }

    @Override
    public String next() {
        if(!hasNext()) {
            throw new NoSuchElementException("No such combintion: "+current+" in '"+zeros+"'");
        }
        char[] chars = zeros.toCharArray();
        for(int i = zeros.length()-1, bit = 1; i >= 0; i--, bit <<= 1) {
            if((bit & current) != 0) {
                chars[i] = ones.charAt(i);
            }
        }
        current++;
        return new String(chars);
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }
}

Выход:

1 = ben
2 = beN
3 = bEn
4 = bEN
5 = Ben
6 = BeN
7 = BEn
8 = BEN
-------------
1 = test?
2 = test!
3 = tesT?
4 = tesT!
5 = teSt?
6 = teSt!
7 = teST?
8 = teST!
9 = tEst?
10 = tEst!
11 = tEsT?
12 = tEsT!
13 = tESt?
14 = tESt!
15 = tEST?
16 = tEST!
17 = Test?
18 = Test!
19 = TesT?
20 = TesT!
21 = TeSt?
22 = TeSt!
23 = TeST?
24 = TeST!
25 = TEst?
26 = TEst!
27 = TEsT?
28 = TEsT!
29 = TESt?
30 = TESt!
31 = TEST?
32 = TEST!

Answer 3

Список выходов для "ben" может быть составлен путем объединения следующих двух списков:

• добавление «b» в начало каждого элемента списка выходов для «en»
• добавление «B» в начало каждого элемента списка выходов для «en»

Вы можете основывать свое рекурсивное определение на этом подходе.