Win a copy of The Java Performance Companion this week in the Performance forum!

# Generating permutation

Arjunkumar Shastry
Ranch Hand
Posts: 986
Suppose there are four elements: p,q,r,s
we want to generate the possible permutations?
Can anybody explain with pseudocode?

Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
I was a music major so you'll have to help me ... are "p" and "pq" valid answers, or only strings of four like "pqrs" and "pqsr" ? Let's go with all answers having length of 4 for now.

Some will start with p, some with q, some with r and some with s. So lets start with a loop that makes those first characters:

Within the p's some will have q for the next char, some r, some s. So add a nested loop to get the next

See how we'd repeat to add the 3rd and 4th?

Now this scheme of avoiding the same character twice (i != j) is pretty ugly. Can you think of a better way? Maybe make a new set of characters that doesn't include the one we just used.

These nested loops that are really doing the same thing smell like code duplication and hint that there may be a shorter way to do this. Are you comfortable with recursion? If so, see if you can use that to factor out the nested loops.

Take a starting shot at this and post some code. We're much more able to help if you have working - or almost working - code. Have fun!
[ July 21, 2005: Message edited by: Stan James ]

Jimmy Die
Ranch Hand
Posts: 97
The permutations can be found with google. I found it helpful to use a chalk board and write out what is happening step by step. It gets long but definitely worth the effort.

marc weber
Sheriff
Posts: 11343
Originally posted by Arjunkumar Shastry:
Suppose there are four elements: p,q,r,s, we want to generate the possible permutations? ...

Permutations

If you're looking for just permutations (different ordering of the given elements), then consider this: There are 4 choices for the first position. Once you select this, that leaves 3 choices for the second position. Then you're left with 2 choices for the third position, and then 1 choice for the last position. So overall, there are 4*3*2*1 = 24 permutations. This is expressed as 4! = 24 (where the ! indicates "factorial").

To generate these permutations, simply apply a systematic approach. For example, if p is in the first position, you have...

pqrs
pqsr

prqs
prsq

psqr
psrq

Then, if q is the first element...

qprs
qpsr

qrps
qrsp

qspr
qsrp

And so on (with 6 more if r is first, and 6 more if s is first).

Combinations

Combinations are different selections of elements without respect to order. So if you're also interested in combinations, then consider that there is 1 way to select 4 elements from this set -- specifically, you just take all of them: pqrs.

There are 4 ways to select 3 elements from this set, because selecting 3 to include is the same as selecting 1 to exclude: qrs, prs, pqs, pqr.

There are 6 ways to select 2 elements from this set:
pq
pr
ps

qr
qs

rs

And there are 4 ways to select 1 element: p, q, r, s.

Note that there is also 1 way to select zero elements, if you want to include the null set.

In all, there are 16 possible combinations from these 4 elements. One way to look at this is to consider that for each of the 4 elements, you have two choices: Either it's in or it's out, and 2*2*2*2 = 16.

So if you want all permutations of all combinations, then you have...
(1 way to pick 4) * (24 ways to order 4) = 24
(4 ways to pick 3) * (6 ways to order 3) = 24
(6 ways to pick 2) * (2 ways to order 2) = 12
(4 ways to pick 1)* (1 way to order 1) = 4
(1 way to pick 0) * (1 way to order 0) = 1

...for a total of 24 + 24 + 12 + 4 + 1 = 65 options (including the null set).

This should provide the background logic for the code.

Stefan Wagner
Ranch Hand
Posts: 1923
I have a strange solution:

Translate the characters to numbers:
[asdf] = param
[1234] = translation
Generate every number from
[1000] = min to
[9999] = max
(or better: from
[1234] to
[4321])
Translate the generated number to a String 'toNum'.
Replace every char in toNum witch matches "[" + translation +"]" with nothing.
If the result is not of len = 0, the number contained illegal digits:
[1248] (8 is illegal).
Else replace the translation witch matches "[" + toNum +"]" with nothing.
If the result is not of len = 0, the number contained duplicate digits:
[1244] (4 is duplicated, translation has an unmatched '3').
else you found a valid number. Translate it back to your characters.

Will run about 7h to print all permutations for a 9-character String to stdout on my machine.

Mani Ram
Ranch Hand
Posts: 1140
Take a look here