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.

---

Number Pools And Guaranteed Combinations Within Fixed Lists

Hey There,

It's been a while since we've taken any time to look at any formal systems or number systems (all the way back to The M I U Puzzle, so today we're going to kick off a quick beginner post that is, somewhat Linux and Unix independent(although we'll be scripting and using Linux/Unix tools to do this work for us in future posts). It's going to segue into something more complicated in a future post, but, for today, we're just going to lay the groundwork. In fact, the beginnings of this process will seem almost brain-dead simple. Which is okay, because they pretty much are ;)

Our topic for today, and for all the follow-ups, is going to be: Number Pools and Guaranteed Combinations within Fixed Strings.

We'll adhere to the following definitions (Followed by our Objective):

Number Pool: A pool of unique numbers of any given amount spanning any given start and end numeric parameters.

Fixed List: A string of numbers of no more than the total number of numbers in the Number Pool and not containing any duplicate numbers.

Fixed List Length: The number of numbers in our Fixed List.

Guaranteed Combination: A combination of unique numbers (restricted to the members of the Fixed List we've defined) with a minimum member count of 1 and a maximum member count of the total number of numbers in our Fixed String.

Guaranteed Combination Length: The number of numbers in our Guaranteed Combination.

Our Objective: 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.

Hopefully, that didn't sound too convoluted or complicated. It's not. Here's what we'll do to prove that very quickly.

1. Our Number Pool for today will be defined as: 1-5 (i.e. 1, 2, 3, 4, 5).
2. Our Fixed List will be: 1, 2, 3, 4, 5
3. This gives us a Fixed List Length of 5.
4. Our Guaranteed Combination, will be: 1, 2, 3, 4, 5
5. This gives us a Guaranteed Combination Length of 5.

So, the question before us is: Given a Number Pool of "1, 2, 3, 4, 5," what are the maximum possible variations of the 5 digit Fixed List "1, 2, 3, 4, 5" that we can create which will contain our Guaranteed Combination, without any duplication? (and, remember, this post is just to get you started thinking about the theory we'll put into practice later)

Simple deduction will lead you to this answer, since there can be only one correct answer (Which, in a sense, is true of larger systems, as well) and our variables are equal. Our result would be 1 variation:

1, 2, 3, 4, 5 <-- Note that the list 5, 4, 2, 1, 3 would be equal and would also be a correct answer, but would not count as an additional variation since it is made up of numbers duplicated from the original variation of 1, 2, 3, 4, 5.

Think about this for a while. It's a good exercise for your head :) In future posts we'll be looking at different variable expansions and the number theory behind generating these sort of lists (For example, a Number Pool of "1 through 99" with a Fixed String of "1, 3, 4, 6, 8, 9, 13, 17, 18, 20, 33, 47, 56, 68, 77, 87, 93" and a Guaranteed Combination of "1, 4, 6, 47, 68" - There will be a lot more strings to produce given these circumstances, which is where Linux or Unix scripting, as mentioned above, will help tremendously). Of course, we'll attack each individual part separately before combining them all into one equation (which will actually be somewhat simpler, but I guess that's a matter of opinion ;)

Cheers,

, Mike

---

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

---

Using Bash To Feed Command Output To A While Loop Without Using Pipes!

Hey There,

Today's post regards something I just picked up. In fact, it's something that's been driving me nuts for a long long time (Reference our earlier post on piped variable scoping in Linux or Unix). The issue I'm writing about is something I've been puzzling over for quite a while in my spare time. I haven't been mulling over how to "do it myself" creatively, but more about "why has this feature never existed when it seems so essential?" As it turns out, this feature "has" existed, although it was a little hard to find in bash 2.x. With bash 3.x, it's brought to the fore and given the attention it deserves (including it's own name ;)

HUGE HELPFUL HINT: If you don't care about the process I went through to find the answer for bash 2.x, and just want to know how to do it, skip down to the PROBLEM SOLVED section which is named appropriately and in the same SCREAMING typeface ;)

The issue is that of command line output (or, if you prefer to think about it the other way, STDIN command line input) redirection and handling. For instance, if you wanted to avoid a problem with scoping in bash and you were reading your input from a file, you could change this block of code:

cat FILE|while read line
do
 echo $line
done

to the more appropriate and efficient:

while read line
do
 echo $line
done <FILE

On the other hand, if you were dealing with command output, you "couldn't" switch this block of code:

ls -1d *|while read line
do
 echo $line
done

with this:

while read line
do
 echo $line
done < ls -1d *

...but that's just common sense, since the redirection input operator would expect ls to be a file and you'd get an error like:

./program: syntax error near unexpected token `-1d'
./program: line 4: `done < ls -1d *'

So, other than the file descriptor exec workaround (which is really just a fancy way of outputting your process's STDIN and STDOUT streams to a file and reading from it; completely contrary to the spirit of having this work naturally) the following might seem like a reasonable way to "feed" your while loop the command output (only showing the last lines of the following code blocks for brevity's sake as we roll through the error scenarios):

done < `ls -1d *`

but, this results in:

./program: `ls -1d *`: ambiguous redirect

and you'd get the same thing using the bash built-in's:

./program: $(ls -1d *): ambiguous redirect

Double redirect doesn't work either (<< ls -1d * - also << `ls -1d *` returns only an error code in errno with no output):

./program: line 4: syntax error near unexpected token `-1d'
./program: line 4: `done << ls -1d *'

And we've considered subshells, which don't work either:

./program: line 4: syntax error near unexpected token `*)'
./program: line 4: `done <(ls -1d *)'

PROBLEM SOLVED!

But here's a really neat trick for getting this to work in bash 2.x. If you change your program to be structured like so:

while read line
do
        echo $line
done < <(ls -1d *)

Your outcome will result in success!! You've got the command output and you didn't have to use a pipe to feed it to the while loop!

NOTE: The two most important things to remember about doing this are that:

1. The space between the first < and second < is mandatory! Although, it should be noted that, between the two <'s, you can have as many spaces as you want. You can even use a tab between the two <'s, they just can't be directly connected.

2. The command, from which you want to use output as fodder for the while loop, needs to be run in a subshell (generally placed between parentheses, just like the ones surrounding this sentence) and the left parenthesis must immediately follow the second <, with "no" space in between!

We've already looked at what happens if you ignore rule number 1 and use << instead of < <. If you ignore rule number 2, you'll get:

./program: line 4: syntax error near unexpected token `<'
./program: line 4: `done < < (ls -1d *)'

And here's the "even better part" - In bash 3.x, you don't have to worry about all that spacing anymore, as they've added a new feature which does the same thing (or is it really just an old feature dressed up to make it seem fabulous? ;) In bash 3.x, you can use the triple-< operator. Actually, I believe the <<< syntax is referred to as a "here string," but that's purely academic. They could call it "fudge," as long as it works ;)

So, in bash 3.x, you could write a while loop that takes input from a command without using a pipe like so:

while read line
do
 echo hi $line
done <<< "`ls -1d *`"

NOTE: The space between the <<< and your backticked (or otherwise extrapolated) command output is not necessary and you can have as much space as the shell can stand between those two parts of the "here string." Of course, the three <'s need to be all clumped together with no space in between them.

I hope this has been helpful and/or enlightening for everyone out there, like me, who've been stumped by this issue for a while and always ended up doing some half-arsed workaround. It's a problem that's been bugging me forever. It turns out I was "this close" with bash 2.x, but I'm very happy to see that bash 3.x actually includes the functionality and makes finding it as simple as RTFMP ;)

Cheers,

, Mike

---

Thanks For This Comment From Richard Bos, which points out a flaw in this post that has been corrected per his remarks:

...
So your example should actually read:

while read line
do
 echo hi $line
done <<< "`ls -1d *`"

One thing though I use: done <<< "$(ls -1d *)"
This construct is also used on this example page http://tldp.org/LDP/abs/html/x16712.html

---

Thanks, also, for this comment from Douglas Huff, which helps to clarify the underbelly of the process:

A friend of mine pointed me to this article and the
previous one in the series that you wrote [on variable scoping]...

I had two comments on these articles but you seem to have
comments disabled, so I figured I'd email them to you.

First, calling it a "scoping" issue is a bit misleading.
While technically true, understanding the underlying
reasons why this doesn't work as "expected" is key to
understanding how you can work around it in POSIX sh or in
ksh without the zsh/bash syntatical sugar for doing so.

What's going on is that a process cannot modify the
environment of it's parent.

When you do:

something | while read blah; do blah; done

What the shell is doing is first executing a subshell
(separate process) that runs the while with stdin
redirected to read from the unnamed pipe. Then in another
subshell it runs "something" with standard out redirected
to the unnamed pipe.

Knowing this it's quite easy to replicate the behaviour
from bash 2/3 and zsh in POSIX sh and ksh with a bit of
understanding of the underlying mechanics. The trick is to
keep the while inside of the original process (since it is
run by the interpretter and does not require a separate
process) and execute the other command in a subshell.
Which is exactly what the syntactical sugar does for you
behind the scenes in bash2&3/zsh.

---

Thanks, also, to Vincenzo Di Massa, for shedding even more light on the subject :

Hi,
the reason why there is the space between < and < in
done < <(ls *.txt)

is the following.

<(ls *.c) gets espanded into a filename

for example try:
$ echo <(ls *.txt)


it will print somehing like /dev/fd/63

the meaning is that <(ls *.txt) gets replaced by the filename
of a special file attached to the output of the ls command.

thus < <( ls *.txt) gets replaced by
< /dev/fd/63
and thus the standard input redirection takes place.

Best Regards Vincenzo

Looking At Formal Systems On Linux and Unix

Hey There,

For today's post, we're going to put out a brain-teaser that won't get solved (at least on this blog) until tomorrow. It's based on a formal system (which is basically a set of rules, with specific applications, used as a method to solve an equation or problem) invented by Emil Post back in the 1920's and is most commonly referred to as a "post production system."

This basic formal system was re-popularized by Douglas R. Hofstadter in his book Godel, Escher, Bach: An Eternal Golden Braid" when he introduced the concept to folks, who weren't especially crazy about such abstract notions, by way of a little puzzle.

For today's post, we're going to reproduce (paraphrased, of course) that puzzle and let you see if you can solve it (or, if you can prove that it can't be solved, which is a possibility).

For tomorrow's post, we'll be putting up a script for Linux or Unix that will make this whole process much easier and will give you the option to "attack" this problem as quickly or slowly as you prefer. While the script will relieve you of the pleasure of completing this mental exercise (if it's at all possible to complete), it will either get you to the answer very quickly or make you wonder how long it might possibly take to solve. Considering the ingredients, that may turn out to be a huge chunk of your time ;)

And here we go. I hope you enjoy this puzzle as much as I did:

We begin with an absolute. You are starting out with a single string (which is absolutely defined, within the context of this formal system and puzzle, as a set of characters in a specific order - e.g. MI is not the same as IM). That absolute (or starting point) is simply "MI." (Note that all punctuation marks are "not" parts of the strings ;)

Give the string "MI," your goal will be to convert that string into the string "MU." Please note that, although a string like MIMUIM is a valid member of the M I U formal system, given the starting string of MI, you will never be able to have an M anywhere but in the first position. Sadly, this does not make finding the answer easy ;)

There are 4, and only 4, rules in this formal system, and you can only correctly solve the puzzle by applying any and/or all of them, one at a time, for as long as it takes to get you to "MU."

Rule 1: If your string ends with an "I", you can add a "U" to the end of it.

Ex: MI can become MIU.

Rule 2: If you have a string of the form "Mx," you can change that to "Mxx." Note here that the variable x can refer to a string (not necessarily just one character) and that only the letters M, I and U will ever exist in any string you produce by application of these rules. x is simply meant to be used as a variable notation.

Ex: MI can become MII
MIU can become MIUIU

The one thing to remember about this rule is that, once you've picked your character, or string, you can only duplicate it once per invocation of the rule. For instance, this is not acceptable:

Ex: MIU cannot become MIUIUII (duplicating "IU" and then duplicating the "I" before the "U," after the "I." You could do the following, however, in a number of steps:
MIU can become MIIUIU (by duplicating the "I" first, and then duplicating the "IU" from the resultant string)

Rule 3: If the substring "III" appears in your string, you can replace "III" with "U," but you may not do the opposite:

Ex: MIII can become MU
Ex: MU cannot become MIII

Rule 4: If "UU" occurs within your string (at any point), you can remove it from the string:

Ex: MIUUI can become MII

Using these 4 "rules of production" (or "rules of inference") can you take your initial string "MI" and change it to "MU"? Also, if it's not possible, is that provable? And, if it is possible, what's the fastest way to do it?

Have fun trying to figure it out. If you already own the aforementioned book, you may know the solution already (it's hidden somewhere in the approximately 700+ pages). Sometimes, though, your individual path to the solution will teach you a lot more than you'd learn by being told the answer :)

Enjoy,

, Mike

String Variables In Bash, Perl, C and Awk on Linux or Unix - Porting

Hey There,

Once again, we're back to porting. In this series of posts that's run the gamut from a somewhat brief explanation of the shebang line (The rightful starting place) to shell, Perl and C porting examples of a fully functional useradd program, we're finally coming back around to the beginning and getting back to basics. Trust me; this will eventually all fall together. When it does, I'll be sure to put up a road map so no one has to try the hit-and-miss blog-search method of information nesting ;)

Today, we're going to look at the simple variable (also referred to as scalar, string, etc); defining, assigning value to and extracting value from it on both Unix and Linux based systems. Our approach is going to be concept-based. That is to say that, for each post on cross-language porting, we'll be hitting on a single concept (such as the simple variable) and showing how each can be applied to our chosen four languages: bash (or shell), Perl, C and Awk (Some folks think Awk isn't a programming language for some reason, but we'll demonstrate, over time, that it must be, since it contains all the constructs that generally define a language as a "programming" language; as opposed to a "markup" language like HTML). I'm going to try and keep this linear, so we're starting out with the very basics and will, eventually, work toward more complex programming constructs.

Here we go:

The simple variable is relatively accurately described in its name. This is one of the simplest forms of variables, as it can be realistically thought of as having only two parts: Part 1 is the variable itself, and part 2 is that variables definition or value. If we say x=y, then the variable x (itself) equals y (its definition/value). Simple enough.

1.Defining, Initializing or Declaring the simple variable. This part is going to be simple for every kind of variable (simple and otherwise), because (except in C), no explicit declaration of most variables is necessary. For the simple variable, Bash, Perl and Awk allow you to define the variable when you assign it value. C requires that you define your variable before you use it. In Bash, Perl and Awk, you have the option to define your variable before use if you wish. Examples below (Note that all beginning and ending double quotes are for emphasis only and not actual code):

Ex: Defining a variable called MySimpleVariable.

In Bash: Just type "declare MySimpleVariable" (you can also use "typeset," and both have options to specify what type of variable you want your simple variable to be. For instance, you could type "declare -i MySimpleVariable" if you wanted your variable to be limited to only being an integer. For now, we're not imposing any restrictions.

In Perl: Just type "$MySimpleVariable;"

In Awk: Just type "declare MySimpleVariable"

In C: You "need" to declare/initialize your variables before you can use them. For this post, we'll stick to numbers and strings for the simple variable (even though, technically, a char string is an array in C). Pretty much everything else isn't simple ;)

For a simple integer variable, just type: "int MySimpleVariable;"
For a simple string variable, just type: "char *MySimpleVariable;" (This generally needs to be followed by a declaration of the size/memory-allocation-requirement of the string, like "MySimpleVariable = (char *)malloc(8*sizeof(char));" for an 8 character string)

2. Assigning values to the simple variable. This is very straightforward in all of our four languages:

Ex: We want to assign the value "MySimpleValue" to the simple variable named MySimpleVariable (Note that any values that contain spaces should be quoted).

In Bash: Just type "MySimpleVariable=MySimpleValue" - Spaces between the variable, "=" sign and value are not permitted.

In Perl: Just type "$MySimpleVariable = MySimpleValue;" - Spaces between the variable, "=" sign and value are optional.

In Awk: Just type "MySimpleVariable = "MySimpleValue"" - Spaces between the variable, "=" sign and value are not, technically, necessary, but recommended. Also, note that "MySimpleValue" is placed within double quotes in the assignment. This is sometimes necessary for string variables, but not for numeric variables (e.g. sometimes "a = b" doesn't work, but "a = 1" does. In this case "a = "b"" ( double quoted value) is required for the string variable assignment, but not the integer).

In C: Just type: "MySimpleVariable = MySimpleValue;" for an integer assignment. For a character, or string, assignment you must surround the value with double quotes (e.g. "MySimpleVariable = "MySimpleValue";").

3. Extracting the value from your simple variable. Finally, it's all going to pay off :)

Ex: We want to print the value of the MySimpleVariable variable. This is also fairly simple in all four languages (Okay, C is always going to be a bit more of a pain ;)

In Bash: Just type "echo $MySimpleVariable" - Note that the $ character needs to precede the variable name when you want to get the value.

host # echo $MySimpleVariable
MySimpleValue

In Perl: Just type "print "$MySimpleVariable\n";" - Note that the $ character needs to precede the variable name when you want to get the value - The \n, indicating a carriage-return, line-feed or new-line isn't necessary, but is nice if you don't want your output on the same line as your next command prompt:

host # perl -e '$MySimpleVariable = MySimpleValue;print "$MySimpleVariable\n";'
MySimpleValue

In Awk: Just Type "print MySimpleVariable" - Note that the $ character "must not" precede the variable name when you want to get the value.

host # echo|awk '{MySimpleVariable="MySimpleValue";print MySimpleVariable}'
MySimpleValue

In C: Just type "printf("%d\n", MySimpleVariable);" for an integer assignment. For a character, or string assignment, you would type: "printf("%s\n", MySimpleVariable);" -- The %s in printf indicates a "string" value and the %d indicates a simple decimal (or integer) value. Note that, for this post, we're going to skip the whole compile part of getting your C program to get you output. You can just take the examples from the preceding steps as guidance. There is a bit more to making a standalone C program than there is to making a standalone program with our other three languages.

host # ./c_program
MySimpleValue

And that's all there is to the simple variable (for the most part ;)

Enjoy, and Cheers,

, Mike

linux unix internet technology

Finding the Number of Characters In A Variable Regardless Of Your Linux Or Unix Shell

Hey there,

Here's a simple enough task: Finding (or determining) the amount of characters in a string variable. In most Unix or Linux shells, this has become a trivial exercise. For instance, in bash or ksh, you can easily tell how many characters are in a particular string variable by either writing one line of code, or skipping right to the end and printing out the answer. By way of example:

host # x=thisIsMyVariable
host # echo ${#x}
16

And it's that simple. The variable x, which contains the string value "thisIsMyVariable", does, indeed, contain 16 elements (or characters). As you can see, in the more advanced shells, taking care of this is no problem.

However, in certain circumstances, you may be required to use a less-advanced, but more highly-portable, shell, like the original Bourne shell. In that case, this same sequence of commands would result in the following:

host # x=thisIsMyVariable
host # echo ${#x}
host # <--- At best, you'll get zero here. Expect nothing. You might possibly get an error.

Our script attached today, uses the old-style expr (Well, it uses the new style expr with the old format and options, again, for maximum portability between systems and shells). It does the exact same thing that echo'ing ${#VARIABLE_NAME} does, but goes about it in a grueling and confusing manner. Remember back when you had to write scripts that took the shell's needs into consideration before your own? ;) Nowadays, things are much more intuitive.

Given a string, like "thisIsMyVariable," the following script will produce the exact same results. It will spit out how many characters are in that string, but take a longer, more confusing ,route to the answer. This is another good example of security through obfuscation as well. In general, having to use the expr command can be a hurdle for folks who've never used a shell that can't do arithmetic or string comparison on its own :)

Sample output (as boring as it is ;):

host # ./string.sh thisIsMyVariable
16

And now, you can get the string length no matter how limited your shell is!

Cheers,





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

#!/bin/sh

#
# string.sh - print out how many characters are in a string variable
#
# 2008 - Mike Golvach - eggi@comcast.net
#
# Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License
#

if [ $# -ne 1 ]
then
 echo "Usage: $0 string"
 exit 1
fi

string=$1
echo $string|while read x
do
        chars=`expr "$x" : '.*'`
  echo $chars
done

, Mike