The Linux and Unix Menagerie: Combinations Vs. Permutations On Linux and Unix

Friday, September 19, 2008

Combinations Vs. Permutations On Linux and Unix

Hey There,

Here's a little something to finish the week off and tie up some loose ends. You may have noticed in our Perl script to maximize guaranteed matches in any give number pool that we did all of our work using permutations, which we then went through the trouble of sorting and removing duplicates. Probably a few people out there were thinking: "Why permutations if 1,2,3 and 3,1,2 are going to be considered equal? Isn't that just a bunch of extra work?" The answers to those questions are "why not" and "yes" ;)

If you feel like taking the time now, to save yourself time in the future, it would be well worth your while to replace the permutation subroutine in that script with one that generates all possible combinations instead. The difference between permutations and combinations is very relevant here because, really, we wanted all possible combinations but the author's rampant paranoia and fear of missing something caused him to generate all permutations and then weed that pool down to all possible combinations.

And what is the difference between permutations of a string and combinations of a string (assuming each alphanumeric character in the string is an element of the string)? Very simply: Permutations are all the possible ways "all" elements of the string can be translated, while combinations are all the possible unique groupings of any (and all) the elements that a string contains.

For example: The permutations of a string "abc1" would be composed of (in whatever order you want):

1 c b a
c 1 b a
1 b c a
b 1 c a
c b 1 a
b c 1 a
1 c a b
c 1 a b
1 a c b
a 1 c b
c a 1 b
a c 1 b
1 b a c
b 1 a c
1 a b c
a 1 b c
b a 1 c
a b 1 c
c b a 1
b c a 1
c a b 1
a c b 1
b a c 1
a b c 1

while the combinations of a string "abc1" would be composed of:

a
abc1
ab
1
c
bc1
abc
b
bc
c1

Here's wishing you all an enjoyable weekend. Hope this little script helps you with your combination generation (no permutations today :)

Cheers,

This work is licensed under a
Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License

#!/usr/bin/perl

#
# combos.pl
#
# 2008 - Mike Golvach - eggi@comcast.net
#
# Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License
#

print "Enter a string... any string: ";
chomp($string = (<STDIN>));

my %results;
for my $i ( 0 .. length $string ) {
        for my $j ( 0 .. length $string ) {
                $results{ substr $string, $i, $j } = 1;
        }
}

delete $results{''};

$results = keys %results;
print "\nYour string $string resulted in $results combinations!\n\n";
foreach (keys %results) {
        print "$_\n";
}