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.