How would I go about generating a list of all possible permutations of a string between x and y characters in length, containing a variable list of characters.

Any language would work, but it should be portable.

Translate

How would I go about generating a list of all possible permutations of a string between x and y characters in length, containing a variable list of characters.

Any language would work, but it should be portable.

All Answers

- python - Generate all permutations of a list without adjacent equal elements
- language agnostic - Algorithm to generate a crossword
- Algorithm to generate all possible permutations of a list?
- java - Generating all permutations of a given string
- algorithm - How to generate all permutations of a list in Python

There are several ways to do this. Common methods use recursion, memoization, or dynamic programming. The basic idea is that you produce a list of all strings of length 1, then in each iteration, for all strings produced in the last iteration, add that string concatenated with each character in the string individually. (the variable index in the code below keeps track of the start of the last and the next iteration)

Some pseudocode:

you'd then need to remove all strings less than x in length, they'll be the first (x-1) * len(originalString) entries in the list.

It's better to use backtracking

You are going to get a lot of strings, that's for sure...

\sum_{i=x}^y{\frac{r!}{{(r-i)}!}} http://www.codecogs.com/eq.latex?%5Csum_%7Bi=x%7D%5Ey%20%7B%20%5Cfrac%7Br!%7D%7B%7B(r-i)%7D!%7D%20%7D

Where, x and y is how you define them and r is the number of characters we are selecting from --if I am understanding you correctly. You should definitely generate these as needed and not get sloppy and say, generate a powerset and then filter the length of strings.

The following definitely isn't the best way to generate these, but it's an interesting aside, none-the-less.

Knuth (volume 4, fascicle 2, 7.2.1.3) tells us that (s,t)-combination is equivalent to s+1 things taken t at a time with repetition -- an (s,t)-combination is notation used by Knuth that is equal to {t \choose {s+t} http://www.codecogs.com/eq.latex?%7Bt%20%5Cchoose%20%7Bs+t%7D%7D. We can figure this out by first generating each (s,t)-combination in binary form (so, of length (s+t)) and counting the number of 0's to the left of each 1.

10001000011101 --> becomes the permutation: {0, 3, 4, 4, 4, 1}

Non recursive solution according to Knuth, Python example:

You might look at "Efficiently Enumerating the Subsets of a Set", which describes an algorithm to do part of what you want - quickly generate all subsets of N characters from length x to y. It contains an implementation in C.

For each subset, you'd still have to generate all the permutations. For instance if you wanted 3 characters from "abcde", this algorithm would give you "abc","abd", "abe"... but you'd have to permute each one to get "acb", "bac", "bca", etc.

Some working Java code based on Sarp's answer:

Here is a simple solution in C#.

It generates only the distinct permutations of a given string.

There are a lot of good answers here. I also suggest a very simple recursive solution in C++.

Note: strings with repeated characters will not produce unique permutations.I just whipped this up quick in Ruby:

You might look into language API for built in permutation type functions, and you might be able to write more optimized code, but if the numbers are all that high, I'm not sure there is much of a way around having a lot of results.

Anyways, the idea behind the code is start with string of length 0, then keep track of all the strings of length Z where Z is the current size in the iteration. Then, go through each string and append each character onto each string. Finally at the end, remove any that were below the x threshold and return the result.

I didn't test it with potentially meaningless input (null character list, weird values of x and y, etc).

This is a translation of Mike's Ruby version, into Common Lisp:

And another version, slightly shorter and using more loop facility features:

Here is a simple word C# recursive solution:

Method:Calling:In Perl, if you want to restrict yourself to the lowercase alphabet, you can do this:

This gives all possible strings between 1 and 4 characters using lowercase characters. For uppercase, change

`"a"`

to`"A"`

and`"zzzz"`

to`"ZZZZ"`

.For mixed-case it gets much harder, and probably not doable with one of Perl's builtin operators like that.

... and here is the C version:

Prints all permutations sans duplicates

Ruby answer that works:

Recursive solution in C++

The following Java recursion prints all permutations of a given string:

Following is the updated version of above "permut" method which makes n! (n factorial) less recursive calls compared to the above method

Here's a non-recursive version I came up with, in javascript. It's not based on Knuth's non-recursive one above, although it has some similarities in element swapping. I've verified its correctness for input arrays of up to 8 elements.

A quick optimization would be pre-flighting the

`out`

array and avoiding`push()`

.The basic idea is:

Given a single source array, generate a first new set of arrays which swap the first element with each subsequent element in turn, each time leaving the other elements unperturbed. eg: given 1234, generate 1234, 2134, 3214, 4231.

Use each array from the previous pass as the seed for a new pass, but instead of swapping the first element, swap the second element with each subsequent element. Also, this time, don't include the original array in the output.

Repeat step 2 until done.

Here is the code sample:

I'm not sure why you would want to do this in the first place. The resulting set for any moderately large values of x and y will be huge, and will grow exponentially as x and/or y get bigger.

Lets say your set of possible characters is the 26 lowercase letters of the alphabet, and you ask your application to generate all permutations where length = 5. Assuming you don't run out of memory you'll get 11,881,376 (i.e. 26 to the power of 5) strings back. Bump that length up to 6, and you'll get 308,915,776 strings back. These numbers get painfully large, very quickly.

Here's a solution I put together in Java. You'll need to provide two runtime arguments (corresponding to x and y). Have fun.

I needed this today, and although the answers already given pointed me in the right direction, they weren't quite what I wanted.

Here's an implementation using Heap's method. The length of the array must be at least 3 and for practical considerations not be bigger than 10 or so, depending on what you want to do, patience and clock speed.

Before you enter your loop, initialise

`Perm(1 To N)`

with the first permutation,`Stack(3 To N)`

with zeroes*, and`Level`

with`2`

**. At the end of the loop call`NextPerm`

, which will return false when we're done.* VB will do that for you.

** You can change NextPerm a little to make this unnecessary, but it's clearer like this.

Other methods are described by various authors. Knuth describes two, one gives lexical order, but is complex and slow, the other is known as the method of plain changes. Jie Gao and Dianjun Wang also wrote an interesting paper.

In ruby:

It is quite fast, but it is going to take some time =). Of course, you can start at "aaaaaaaa" if the short strings aren't interesting to you.

I might have misinterpreted the actual question though - in one of the posts it sounded as if you just needed a bruteforce library of strings, but in the main question it sounds like you need to permutate a particular string.

Your problem is somewhat similar to this one: http://beust.com/weblog/archives/000491.html (list all integers in which none of the digits repeat themselves, which resulted in a whole lot of languages solving it, with the ocaml guy using permutations, and some java guy using yet another solution).

This code in python, when called with

`allowed_characters`

set to`[0,1]`

and 4 character max, would generate 2^4 results:`['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111']`

Hope this is of use to you. Works with any character, not only numbers

Here is a link that describes how to print permutations of a string. http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html

Though this doesn't answer your question exactly, here's one way to generate every permutation of the letters from a number of strings of the same length: eg, if your words were "coffee", "joomla" and "moodle", you can expect output like "coodle", "joodee", "joffle", etc.

Basically, the number of combinations is the (number of words) to the power of (number of letters per word). So, choose a random number between 0 and the number of combinations - 1, convert that number to base (number of words), then use each digit of that number as the indicator for which word to take the next letter from.

eg: in the above example. 3 words, 6 letters = 729 combinations. Choose a random number: 465. Convert to base 3: 122020. Take the first letter from word 1, 2nd from word 2, 3rd from word 2, 4th from word 0... and you get... "joofle".

If you wanted all the permutations, just loop from 0 to 728. Of course, if you're just choosing one random value, a much

~~simpler~~less-confusing way would be to loop over the letters. This method lets you avoid recursion, should you want all the permutations, plus it makes you look like you know Maths^{(tm)}!If the number of combinations is excessive, you can break it up into a series of smaller words and concatenate them at the end.

c# iterative:

Here is my take on a non recursive version

The pythonic solution:

Well here is an elegant, non-recursive, O(n!) solution: