递归函数生成一个单词中所有大写字母的组合

Question

有谁知道创建一个递归函数来生成给定单词中所有大写字母组合的逻辑吗？我试图做到这一点在Java中......对于〔实施例，给它一个字“奔”，它输出：

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 

编辑：

一些更多的提示：

• 有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 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”的输出列表中的每个项目的开始处

您可以基于此方法的递归定义。