Wednesday, September 3, 2008

Lists vs. Strings: Perl List Permutations For Linux Or Unix

Hey there,

I think I promised yesterday that all posts having to deal with Number Pools And Guaranteed Combinations Within Fixed Lists would have that string in their title, but, upon further reflection, it seems like it would make every title waaaay too long, and none of the parts would get indexed correctly, since Google might discard them as duplicate content based on the title tag.

In any event, this post is another small step toward yesterday's objective, along with (hopefully) an understanding of the various processes and steps involved in getting there. These are, indeed, small chunks of information when taken separately, but that is by intent. I'm not trying to insult anyone's intelligence; just keep the playing field even for all concerned ;) If you need to review the definitions of our system, please refer back to yesterday's post on Number Pools and we'll iterate (not reiterate of course, because that would be repeating it again. I'm only repeating it this time... OK, enough with the wordy nit-picking ;)

Today, we're going to look at one of the basics of building a system which can produce our desired end result. That basic building block is known as the permutation of a list, as opposed to an array (or string). Given Perl's definitions, at their basic, a list is static and cannot be modified, while the opposite is true of an array. They look deceptively the same. Most people don't know the difference. I still may not have a fingernail grip on the exact definition and details of the difference, but it hasn't caused me too much heartache ;) And, of course, strings are generally considered scalar variables (single value).

Our objective has been modified (in form, not in nature) to accommodate this change (and I've updated the original post's definitions as well): Given a Number Pool of "x through y," create the maximum possible Fixed List Length variations of our Fixed List that contain some variation of our Guaranteed Combination, without any duplication (i.e. 1, 2, 3 is equal to 2, 3, 1 and would only count as one match), and return the results.

In any event, my sincerest apologies for using string when I meant list. I didn't get a whole lot of complaints about this, which means either most everyone got what I meant or a vast majority of readers believe that Internet democracy will sort me out one way or another (which it has). This is what happens when you write at family gatherings ;)

So, given our Fixed List from yesterday (the numbers that, together, add up to a total of "Fixed List Length" members), we would first be looking for all permutations of that List. The list being composed of "1, 2, 3, 4, 5"

Using the following "public domain" code (meaning I didn't write it, don't accept credit for it, love it, but don't know who to credit it to ;) we can generate all permutations of our Fixed List. This will be the first thing we want to do, because this step needs to be completed before we check for Guaranteed Combinations within those permutations!

#!/usr/bin/perl

permute([1,2,3,4,5], []);

sub permute {
my @items = @{ $_[0] };
my @perms = @{ $_[1] };
unless (@items) {
print "@perms\n";
} else {
my(@newitems,@newperms,$i);
foreach $i (0 .. $#items) {
@newitems = @items;
@newperms = @perms;
unshift(@newperms, splice(@newitems, $i, 1));
permute([@newitems], [@newperms]);
}
}
}


This will produce all permutations of the List "1, 2, 3, 4, 5," as such (cropped for space savings):

5 4 3 2 1
4 5 3 2 1
5 3 4 2 1
3 5 4 2 1
4 3 5 2 1
3 4 5 2 1
...


As you can see, given our very simple example (where everything is equal to 5 and all lists and combinations are 5 (or 1, 2, 3, 4, 5), we have a lot of repetition in our output, and part of our stated objective is to create this list "without any duplication (i.e. 1, 2, 3 is equal to 2, 3, 1...)..."

Obviously, although this piece of Perl code will provide us with every possible permutation of the list "1, 2, 3, 4, 5," according to our Objective's definition, they're all equal. As we noted yesterday, the result can only be one list of five numbers, given our standards.

Tomorrow, we'll look at a way to resolve this issue, using a minimal amount of code (and, of course, a lot more of my concentric-circular explanation ;) so that the permutations get whittled down to the one unique list (containing all 5 numbers in our list) and removing all the "technically" different ones, which are essentially all the same list printed out in different order.

Cheers,

, Mike




Please note that this blog accepts comments via email only. See our Mission And Policy Statement for further details.