This week's book giveaway is in the Jobs Discussion forum. We're giving away four copies of Java Interview Guide and have Anthony DePalma on-line! See this thread for details.

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

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.

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

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.