生成字符串所有组合的算法

Question

生成字符串所有组合的算法

20

我在网上找到了一个链接，该链接展示了一种生成字符串所有组合的算法：http://www.mytechinterviews.com/combinations-of-a-string

以下是复制的算法。

void combine(String instr, StringBuffer outstr, int index)
{
    for (int i = index; i < instr.length(); i++)
    {
        outstr.append(instr.charAt(i));
        System.out.println(outstr);
        combine(instr, outstr, i + 1);
        outstr.deleteCharAt(outstr.length() - 1);
    }
} 

combine("abc", new StringBuffer(), 0);

我不理解的是这行代码：

outstr.deleteCharAt(outstr.length() - 1);

如果我删除这一行，程序显然就不再工作了，但是为什么一开始需要它呢？我理解递归的思想，我们改变一个初始字符并在其余字符上进行递归，但是deleteChar这一行似乎在逻辑上没有任何地方可以放置。添加outstr.deleteCharAt行的原因是什么？

- john

由于我们想要所有的组合，包括charAt(i)和不包括charAt(i)，因此我们需要将这两种情况分开处理。那些不包含charAt(i)的组合在下一次for循环迭代中会被deleteCharAt()函数神奇地处理掉，在当前迭代结束之前。 - Hackless

11个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Coder93 · Answer 1

import com.google.common.collect.Lists;

import java.util.List;

public class Combinations {
    public static String[] getCombinations(final String input) {
        final List<String> combinations = Lists.newArrayList();
        getCombinations(input.toCharArray(), combinations, 0, "");
        return combinations.toArray(new String[0]);
    }

    private static void getCombinations(final char[] input, final List<String> combinations, final int index, final String combination) {
        if (index == input.length) {
            combinations.add(combination);
            return;
        }
        getCombinations(input, combinations, index + 1, combination + String.valueOf(input[index]));
        getCombinations(input, combinations, index + 1, combination);
    }

}

相应的测试：

import org.hamcrest.Matchers;
import org.junit.Test;

import static org.hamcrest.MatcherAssert.assertThat;

public class CombinationsTest {
    @Test
    public void testCombinations() {
        verify(Combinations.getCombinations(""), "");
        verify(Combinations.getCombinations("a"), "a", "");
        verify(Combinations.getCombinations("ab"), "ab", "a", "b", "");
        verify(Combinations.getCombinations("abc"), "abc", "ab", "ac", "a", "bc", "b", "c", "");
        verify(Combinations.getCombinations("abcd"),
                "abcd", "abc", "abd", "ab", "acd", "ac", "ad", "a", "bcd", "bc", "bd", "b", "cd", "c", "d", "");
    }

    private void verify(final String[] actual, final String... expected) {
        assertThat(actual, Matchers.equalTo(expected));
    }
}