<< Previous Article
Once done with combinations, it is natural to jump to the next level – the permutations. Like combinations in the previous article, a lot of concepts will be similar. Though similar, the recursive relation would be definitely different. And so, the assumptions on our procedure to be existing for lower order, though similar, would have some variations. In general, permutations is a procedure of first selecting “k” items from “n” distinct items, and then arranging those “k” items (in different permutations or possible ways). In mathematical terms, it is denoted by nPk (read n P k), permutations of “k” items from “n” (distinct) items.
If it is to just compute the total number of such different permutations or arrangements possible, mathematics as usual readily provides the recursive relation and also the terminating condition:
nPk = n-1Pk + k * n-1Pk-1, n > k > 0 (recursive relation)
nPk = k * n-1Pk-1, n = k > 0 (recursive relation)
nPk = 1, for k = 0 (terminating condition)
Note that, the implicit condition on which nPk is defined is n >= k >= 0.
Interestingly, in the case of permutations, there are two recursive relations for two different scenarios, and one terminating condition. First, let’s work out the simpler case – the arrangements of all the “n” distinct items, i.e. for the special case k = n. And as the two parameters are same, they may be merged into one, say just “n”.
A straight away functional recursive implementation would look like this:
permutations(n)
{
if (n == 0)
return 1;
else
return n * permutations(n - 1);
}
Looks familiar? Yeah! Similar to the recursive implementation of factorial. In fact, it is the same. Recall that there are n! ways of arranging “n” (distinct) items. Anyways.
What about printing all these different possible arrangements of “n” (distinct) items? Should be similar, as the recursive logic should still hold. For n = 0, i.e. arranging 0 (distinct) items, the only way is arranging nothing, and hence print nothing. Additionally, the basket of “n” (distinct) items also need to be provided as an input to the procedure, say something like arrangements(n, basket[]). So, the procedure statement can be specified as follows: Implement a procedure arrangements(n, basket[]), which takes a number “n”, and a basket of “n” items and prints the nPn = n! possible arrangements of “n” (distinct) items in the basket, one arrangement per line.
Now, with all the background set to implement arrangements(n, basket[]), let’s apply the usual trick of assuming the procedure arrangements() to be already existing for a lower order. Based on our learnings so far, it is natural to take it for the lower order “n – 1”, as arrangements(n – 1, basket[] (with n – 1 items)), which prints the n – 1Pn – 1 = (n – 1)! possible arrangements of “n – 1” (distinct) items in the basket, one arrangement per line.
Next, to make “n” items to “n – 1” items in arrangements(n, basket[]), so as to apply the above assumed procedure to implement the logic for “n” items, we pick out one of the “n” items, and hence print n – 1Pn – 1 = (n – 1)! possible arrangements of the remaining “n – 1” (distinct) items in the basket, one arrangement per line, each prefixed by the first picked out item.
Now, same as in the case of selections in the previous article, this calls for change in the arrangements procedure & its logic. So, drawing from the past experience, the procedure statement can be redefined as follows: Implement a procedure arrangements(n, basket[], plen, prefix[]), which takes a number “n”, a basket of “n” items, a prefix of “plen” items and prints the nPn = n! possible arrangements of “n” (distinct) items in the basket, one arrangement per line, each prefixed by “plen” items in prefix.
And accordingly, the assumption of the existence of lower order procedure becomes arrangements(n – 1, basket[] (with n – 1 items), plen, prefix), which prints the n – 1Pn – 1 = (n – 1)! possible arrangements of “n – 1” (distinct) items in the basket, one arrangement per line, each prefixed by “plen” items in prefix. Again, as in the case of selections, the lower ordering has not been applied to “plen” & prefix, as they are just the supporting parameters.
This assumed procedure can now be used, as in the earlier attempt, to implement the logic for arrangements(n, basket[], plen, prefix[]), by picking out one of the “n” items and applying on the remaining “n – 1” items, along with the picked out item being passed in the prefix. However, as here, all possible arrangements are being sought, note that even this picking out of one of the “n” items can be done in “n” different ways. And for all of those “n” different ways, the assumed procedure of lower order need to be invoked for the remaining “n – 1” items. Thus, the logic would evolve into a loop iterating for “n” times, each time picking out a different item out of the “n” items and applying the assumed procedure of lower order on the remaining “n – 1” items. Note the interesting translation of the multiplication of “n”, in the recursive relation, into a loop iterating for “n” times.
Also note that, now in this new setup with prefix, the terminating condition need to print the prefix, rather than printing nothing.
Hence, the final logic may be summarized as follows:
arrangements(n, basket[], plen, prefix[])
{
if (n == 0)
{
print(plen, prefix);
print_nl(); // print new line
}
else
{
for (i = 0; i < n; i++)
{
prefix[plen] = basket[i];
remaining = basket - {basket[i]};
arrangements(n - 1, remaining, plen + 1, prefix);
}
}
}
Note that, in the above logic, “remaining = basket – {basket[i]};” is not a typical programming language statement. So, it has to be appropriately converted, when putting it into any specific language implementation. One possible implementable logic for the above else part could look like this (by separating the 0th step of the for loop):
{
prefix[plen] = basket[0];
arrangements(n - 1, basket + 1, plen + 1, prefix);
for (i = 1; i < n; i++)
{
swap(prefix[plen], basket[i]);
arrangements(n - 1, basket + 1, plen + 1, prefix);
}
// Reversing the shift due to the above swaps
// to preserve the ordering in basket
for (i = 0; i < n - 1; i++)
basket[i] = basket[i + 1];
basket[i] = prefix[plen];
}
And again, as in the case of selections in the previous article, to make the toplevel call look beautiful, a wrapper print_arrangements() can be provided as follows:
print_arrangements(n, basket[])
{
plen = 0;
prefix[] = {}; // prefix being capable of supporting max "n" items
arrangements(n, basket, plen, prefix);
}
Check out the next article for the recursive logic of the general permutations nPk.
Next Article >>