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

Question

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

Ben 
bEn 
beN 
BEn 
BeN 
bEN 
BEN 

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

Answer 1

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

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

EDIT:

еще несколько советов:

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

EDIT 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 2

В псевдокод (ну, 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 3

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

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

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