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

Question

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

Я нашел в Интернете ссылку, которая показывает алгоритм для генерации всех комбинаций строки: 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?

16

java algorithm combinations

задан john 23 January 2012 в 00:07

1 ответ

Другие вопросы по тегам:

java algorithm combinations

Похожие вопросы:

score 0 · 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));
    }
}