Генерация перестановок строк длиной от 2 до N с учетом N букв в Java - PullRequest
Новая
       1

Генерация перестановок строк длиной от 2 до N с учетом N букв в Java

1 голос
/ 19 сентября 2011

Учитывая следующий рекурсивный метод Java: 

protected static void makeStringsList(List<String> strings, List<Character> letters) {
  if (letters.size() == 2) {
    strings.add(letters.get(0) + "" + letters.get(1));
    strings.add(letters.get(1) + "" + letters.get(0));
  }
  else {
    Character c = letters.remove(0);
    makeStringsList(strings, letters);
    List<String> tempList = new ArrayList<String>();
    for (String s : strings) {
      StringBuffer buffer = new StringBuffer(s);
      for (int index = 0; index < s.length() + 1; index++) {
        buffer.insert(index, c);
        tempList.add(buffer.toString());
        buffer = new StringBuffer(s);
      }
    }
    strings.addAll(tempList);
  }
}

Учитывая N букв, приведенный выше код генерирует список, содержащий перестановки строк, которые используют все те же N букв. Например, учитывая (1, 2, 3), он генерирует:

  • 123
  • 132
  • 213
  • 231
  • 312
  • 321
Также в список добавляются строки, содержащие меньше N букв, но они не являются исчерпывающими. Используя тот же пример, 23 и 32 также находятся в списке, но 12, 21, 13 и 31 отсутствуют в списке.

Первоначально я создал описанный выше метод для ката, над которым я ранее работал здесь в свободное время, и я хочу изменить его сейчас, чтобы сделать его более универсальным и вернуть список содержит перестановки строк длиной от 2 до N с N буквами. Можно ли изменить метод выше, чтобы выполнить эту задачу? Какие-нибудь советы? Ваш совет будет высоко оценен!

1 Ответ

1 голос
/ 19 сентября 2011

Я бы хотел помочь с этой проблемой.

Я думаю, что лучший способ сделать это - сгенерировать набор мощности из набора заданных символов, а затем найти набор комбинаций строк, которые может генерировать каждый набор в наборе мощности. 

List <String> allPermutationsOfSubsequences( Set <Character> chars ) {

    Set < Set <Character> > powerSetOfChars = generatePowerSet ( chars );

    List <String> permutations = new ArrayList <String> ();

    for (Set <Character> subsequence : powerSetOfChars)
        permutations.addAll( generatePermutations ( subsequence ) );

    return permutations;
}

Set <Set <Character>> generatePowerSet ( Set <Character> set ) {
    Set < Set <Character> > powerSet = new HashSet < Set <Character> > ();
    if (set.size() == 0) {
        powerSet.add(new HashSet <Character> ());
        return powerSet;
    }

    Character anElement = set.iterator().next();
    set.remove(anElement);

    for (Set <Character> subset : powerSet(set)) {
        Set <Character> setWithElement = new HashSet <Character> ();
        setWithElement.add(anElement);
        setWithElement.addAll(subset);
        powerSet.add(newSet);
        powerSet.add(subset);
    }

    set.add(anElement);

    return powerSets;
}

//Generates a list of permutations of the characters provided in the set.
List <String> generatePermutations ( Set <Character> chars );

Метод generatePowerSet создает все наборы, поэтому он также включает наборы размером 0 и 1. Вы можете удалить их, если хотите, но основная идея есть.

Пример вывода: [3, 2, 1, 31, 13, 32, 23, 21, 12, 321, 312, 231, 213, 132, 123]

Все, что вам нужно сделать, это удалить те, которые размером 1.

Чтобы увидеть полный код, который был скомпилирован и показал свою работоспособность, просто зайдите сюда и попробуйте сами!

http://pastebin.com/P3YMmT2m

...