перестановки строки фиксированной длины

Question

Я пытаюсь взять семизначную строку и сгенерировать все возможные трех- и четырехбуквенные перестановки. Это похоже на то, что рекурсия была бы полезна (большинство генераторов перестановок, которые я видел, являются рекурсивными), но я продолжаю зацикливаться на том, как избежать повторения. То есть, если моей входной строкой является «aabcdef», я не хочу, чтобы какая-либо перестановка содержала более двух символов «a».

Любые идеи, которые вы можете предоставить, приветствуются.

Answer 1

Это можно сделать как итеративно, так и рекурсивно. Вот приличный генератор перестановок . Это можно адаптировать к вашим потребностям и сделать общим (взять List<T> элементов), чтобы он мог принимать список чисел, строку (список символов) и т. Д.

Answer 2

Попробуйте думать о персонажах как об элементах в сумке символов.

Вот какой-то псевдокод, который должен работать:

permute ( bag < character > : theBag, integer : length, string : resultSoFar )
    if length <= 0 then:
       print resultSoFar
       exit
    end-if

    for each x in theBag:
        nextResult = resultSoFar + x
        nextBag = theBag - x
        permute( nextBag, length - 1, nextResult )
    end-for
end-method

Удачи!

Answer 3

Это в Ruby, но это может помочь: http://trevoke.net/blog/2009/12/17/random-constrained-permutations-in-ruby/

Answer 4

@ Chip Uni: когда я реализовал ваш код, он генерировал все перестановки длиной от x до макс. Поэтому, когда я кормил его длиной 3 мешком, содержащим 7 символов, он генерировал все перестановки длины от 3 до 7. Однако было просто исключить все результаты, превышающие длину 4.

Большое спасибо, вы все! Я очень ценю ваши предложения и помощь.

Answer 5

Вот подсказка, которая может помочь. Если у вас введен «aabcdef» и вы не хотите перестановок с двумя «a», проще удалить одно из «a» из ввода, чем пытаться исключить перестановки с несколькими «a» Вы генерируете их.

Answer 6

сделать функцию, которая принимает набор букв, заставить ее возвращать набор из n перестановок (3 или 4), которые начинаются с указанной вами буквы. Затем запустите его один раз для каждого из уникальных персонажей в вашем наборе.

Полный набор результатов будет объединением подмножеств.