Tag Archives: arrangements

Permutations of Selections

<< Previous Article

In the previous article on permutations, the special case of arrangements of all the “n” distinct items, was dealt with. Now, with that and the logic of combinations (different ways of selecting “k” items from “n” distinct items), we are all set for the general permutations 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.

As mentioned in the previous article, the total number of such different permutations or arrangements possible can be readily computed using the following recursive relation and the terminating condition:
nPk = k * n-1Pk-1 + n-1Pk, 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.

A straight away functional recursive implementation would look like this:

permutations(n, k)
{
	if (k == 0)
		return 1;
	else if (k == n)
		return k * permutations(n - 1, k - 1);
	else
		return k * permutations(n - 1, k - 1) + permutations(n - 1, k);
}

And now with the earlier two logics of printing (different possible selections of “k” items from “n” (distinct) items, and all different possible arrangements of “n” (distinct) items), it is just a matter of few tweaks to be able to invoke the above two logics to solve the general permutations printing logic.

Note that the general permutations is a two step process of first selecting “k” items from “n” distinct items, and then arranging those “k” items (in different permutations or possible ways). Hence, it can be implemented recursively, using a recursive logic similar to that of the selection logic, and then applying the arrangement logic, once selected.

Assuming the print_arrangements(n, basket[]) available from the previous article, and invoking & renaming the selections() logic from its previous article, we have the following:

selections_arrangements(n, k, basket[], plen, prefix[])
{
	if (k == 0)
	{
		print_arrangements(plen, prefix);
	}
	else if (k == n)
	{
		for (i = 1; i < k; i++)
		{
			prefix[plen + i] = basket[i];
		}
		print_arrangements(plen + k, prefix);
	}
	else
	{
		// Following two recursive calls of selections_arrangements
		// have been swapped, compared to the original recursive calls
		// of selections, to print them from left to right
		prefix[plen] = basket[0];
		selections_arrangements(n - 1, k - 1, basket + 1, plen+1, prefix);
		selections_arrangements(n - 1, k, basket + 1, plen, prefix);
	}
}

Note the change to the invocation of print_arrangements() logic, instead of just the print() logic, in the cases of k == 0 and k == n, where the selecting of “k” items from “n” distinct items is already complete and now their arrangements need to be printed.

Moreover, as the cases k == 0 and k == n, take similar action, they can be further merged as follows:

selections_arrangements(n, k, basket[], plen, prefix[])
{
	if ((k == 0) || (k == n))
	{
		for (i = 1; i < k; i++)
		{
			prefix[plen + i] = basket[i];
		}
		print_arrangements(plen + k, prefix);
	}
	else
	{
		prefix[plen] = basket[0];
		selections_arrangements(n - 1, k - 1, basket + 1, plen+1, prefix);
		selections_arrangements(n - 1, k, basket + 1, plen, prefix);
	}
}

And again, as in the previous articles, to make the toplevel call look beautiful, a wrapper print_selections_arrangements() can be provided as follows:

print_selections_arrangements(n, k, basket[])
{
	plen = 0;
	prefix[] = {}; // prefix being capable of supporting max "k" items

	selections_arrangements(n, k, basket, plen, prefix);
}

 

   Send article as PDF   

Permutations

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

   Send article as PDF