aspose file tools*
The moose likes Java in General and the fly likes Generating permutation Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Generating permutation" Watch "Generating permutation" New topic
Author

Generating permutation

Arjunkumar Shastry
Ranch Hand

Joined: Feb 28, 2005
Posts: 986
Suppose there are four elements: p,q,r,s
we want to generate the possible permutations?
Can anybody explain with pseudocode?



Namma Suvarna Karnataka
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
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 ]

A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
Jimmy Die
Ranch Hand

Joined: Nov 20, 2003
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.


Jimmy Die
marc weber
Sheriff

Joined: Aug 31, 2004
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.


"We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." ~Joe Strummer
sscce.org
Stefan Wagner
Ranch Hand

Joined: Jun 02, 2003
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.


http://home.arcor.de/hirnstrom/bewerbung
Mani Ram
Ranch Hand

Joined: Mar 11, 2002
Posts: 1140
Take a look here


Mani
Quaerendo Invenietis
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Generating permutation