递归函数,用于生成单词中所有大写字母的组合

Question

有没有人知道创建递归函数背后的逻辑来生成给定单词中的所有大写字母组合？我正在尝试用Java做这个...例如,给它"ben"这个词并输出:

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

编辑:

一些提示:

• 有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!