Combinations

Today I solved a rather interesting problem: To find (and display) all the combinations that can be formed from a word. Suppose the word entered is “abc,” the output would be “abc acb bac bca cab cba.” A little Combination theory in Mathematics would tell you that if the length of the word is n, the number of combinations that can be formed from that word is n! (i.e, factorial of n.) In the above case, it is 3! or 3x2x1 = 6.

I went about solving the problem in Pascal, and it certainly isn’t the language you want to program in for these kind of tasks. However, today it wasn’t my choice in the matter, so: Pascal it was. An explanation of the solution is given below (not the actual source code):

I used three functions for the task: combinationOf(word, stub), shuffle(word), and strip(position, word). combinationOf displays all the combinations of the word using recursion. shuffle (which shifts the word one position to the right, i.e, changes “abc” to “bca” and “bca” to “cab”) and strip (which strips the alphabet corresponding to the digit i.e, strip(1, “abc”) => “bc”) are helper functions called from combinationOf.

The crux of the code (which may not be valid Pascal) is given below:


function combinationOf(word: string, stub: string) : string;
var i: integer;
var prestub: string;
begin
for i := 1 to length(word) do
prestub := word[i];
begin
if(length(strip(i, word)) = 2) then
begin
write(stub, preStub);
write(shuffle(word));
write(stub, preStub);
write(word);
end;
else
begin
stub := stub + prestub;
combinationOf(shuffle(strip(i, word)), stub);
end;
end;

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s