# Generating permutation

Arjunkumar Shastry

Ranch Hand

Posts: 986

Stan James

(instanceof Sidekick)

Ranch Hand

Ranch Hand

Posts: 8791

posted 11 years ago

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 ]

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

Posts: 97

posted 11 years ago

If you're looking for just

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).

There are 4 ways to select 3 elements from this set, because selecting 3 to

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

(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.

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

posted 11 years ago

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.

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

It is sorta covered in the JavaRanch Style Guide. |