fixed-length permutations of a string

Question

I'm trying to take a seven-character string and generate all the possible 3- and 4-letter permutations of it. This seems like something that recursion would be handy for (most all permutation generators I've seen are recursive), but I keep getting stuck at how to avoid repetition. That is, if my input string is "aabcdef" I don't want any of the permutations to contain more than two "a" characters.

Any insights you can provide are greatly appreciated.

Answer 1

make a function that takes a set of letters make it return the set of n permutations (3 or 4) that start with the letter you specify. Then run it once for each of the unique chars in your set.

The full result set will be the union of the subsets.

Answer 2

This can be done both iteratively and recursively. Here is a decent permutation generator. That can be adapted to your needs and made generic (to take a List<T> of elements) so it can take a list of numbers, a string (list of characters) and so on.

Answer 3

Here's a clue that might help. If you have input "aabcdef" and you don't want permutations with two "a"s, it is easier to remove one of the "a"s from the input rather than trying to eliminate the permutations with multiple "a"s as you generate them.

Answer 4

Try thinking about the characters as elements in a bag of characters.

Here's some pseudocode that should work:

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

Good luck!

Answer 5

@ Chip Uni: when I implemented your code, it generated all permutations of length x to max. So when I fed it length 3 with a bag containing 7 characters it generated all permutations of length 3 through 7. It was a simple matter to eliminate all results greater than length 4, though.

Thank you very much, y'all! I greatly appreciate your suggestions and assistance.

Answer 6

This is in Ruby, but it might help: http://trevoke.net/blog/2009/12/17/random-constrained-permutations-in-ruby/