One of the fundamental concepts of software testing is that in most situations you cannot exhaustively test all possible inputs to your system under test because there are simply too many inputs. For example, if you are testing some poker game application and some method accepts a representation of 7 cards, if duplicate cardss are allowed, there are 52 to the 7th power inputs = 1,028,071,702,528 test case inputs. Therefore, a significant part of software testing involves various techniques designed to select a subset of useful test case inputs from the set of all possible test case inputs. Equivalence class partitioning divides all test case inputs into subsets that are equivalent in some way. The idea is that you need only test representative inputs from each equivalence class. Determining equivalence classes is much easier said than done however. A close cousin technique is boundary value analysis. Here you use input values at, above, and below the values which define equivalence classes. Research has shown that these boundary values are relatively more likely to cause errors than non-boundary values. Pairwise testing is a technique which uses all possible pairs of input values from different input parameters. Another technique to reduce the number of test case inputs is to simply send random input to the SUT. Although not particularly effective, random input testing is easy to implement and when it does reveal a bug, the bug is usually a serious crashing or hanging bug. A cousin of random input testing is a technique I call called partial antirandom testing. Here you create a set of random test case inputs which are maximally different f6rom each other. The idea is that similar inputs will reveal similar information about the SUT, so maximally different test case inputs will reveal more information than simple random input testing. The current issue of MSDN Magazine has an article I wrote about the technique: http://msdn.microsoft.com/en-us/magazine/ee309511.aspx .

 

 

I am currently working on an article for Microsoft's MSDN Magazine that describes how to write lightweight Web application UI test automation using the jQuery library. One of the technical reviewers of my article asked me about the pros and cons of using the jQuery approach compared with using the Selenium test framework and the Watir test framework. A second reviewer asked about the difference between using jQuery and using plain vanilla JavaScript. Additionally, a third reviewer pointed out that there is a new .NET based test framework named ASP.NET QA.

 

OK, let's start with jQuery vs. plain JavaScript for Web app automation. The two approaches are very similar. Using the jQuery library has the advantages of a consistent selector and manipulator syntax to get references to controls, such as submit buttons, and syntax to set and examine control values. Additionally, jQuery is mostly browser agnostic so you don't have to worry about whether code such as document.all["TextBox1"] will work with Firefox or not. One disadvantage of jQuery vs. plain JavaScript is that jQuery represents an external dependency to some extent. Now for jQuery test automation vs. using Selenium. Selenium is an excellent tool, but in my opinion a non-technical disadvantage of using Selenium is that time spent learning the Selenium framework does not help you directly with improving your developer skills. When using jQuery to write test automation you are learning skills which can be used not only for testing but also for Web development. One advantage of Selenium is that it is a big framework and has a lot of functionality at one higher level of abstraction than jQuery, so writing test automation with Selenium can be quicker than with jQuery (after you get over the initial Selenium learning curve). I am personally not a fan of Watir mostly because I just don't like coding in Ruby nearly as much as I like coding with JavaScript. So for me jQuery has the advantage of using JavaScript which directly maps to improved development skills. An advantage of Watir compared to jQuery is that the Watir framework is quite well known so there is good documentation and support. Although I'm not positive, I believe that Watir works only with Internet Explorer, which if true, is a disadvantage compared to using jQuery. Now there is also Watin, which does not have the Ruby language disadvantage, but using C# or some other .NET compliant language does not directly map to improved Web development skills either. One of the reviewers of my jQuery article pointed out that there is a new "ASP.NET QA" framework available on CodePlex, Microsoft's open source site. I haven't had a chance to examine ASP.NET QA closely but it looks pretty nice.

In some software test automation scenarios you may want the test harness to programmatically send test results via e-mail in addition to, or instead of, saving results to a file or database. In a .NET environment, this is pretty easy to do. The first step is to configure the test host machine, which is running the test automation, as an SMTP server so the host can send mail. On Windows XP, if you have configured IIS, in most cases SMTP will also be enabled, but not configured. In Computer Management, under IIS, open the SMTP Virtual Server Properties dialog. On the General tab, enter the IP address of the host machine. Port 25 will be the default. Then on the Access tab, Connection section, add the IP address of the test host machine. Now your test host can send mail. You can use the older System.Web.Mail namespace, or the newer System.Net.Mail namespace. C# code to send mail this looks like:

 

using System.Net.Mail;

try
{
  SmtpClient c = new SmtpClient("10.20.30.40", 25); // host IP, port
  MailAddress mFrom = new MailAddress("results@testHost");
  MailAddress mTo = new MailAddress("somebody@somewhere.com");
  MailMessage m = new MailMessage(mFrom, mTo);
  m.Subject = "Test Results at" + System.DateTime.Now;
  string mBody = "Number Pass = 120\nNumber Fail = 0";
  m.Body = mBody;
  c.Send(m);
}

 

If your test host machine is not running under a .NET environment, you can use the old CDONTS or the newer CDOSYS ActiveX libraries.

The new F# programming language is interesting. One possible reason for learning a new programming language is an effect that is closely related to something called the Sapir-Whorf hypothesis (SWH). In over-simplified terms, the SWH says that speakers of different languages (English, Japanese, etc.) think differently because of differences in languages. So an extension of this idea is that programmers and testers who use C# may program and test differently than those who use LISP, and so the more programming languages you know, the more programming patterns you have available. That aside, in a recent Introduction to F# Programming class I taught, most students (and I) said they were in the class out of technical curiosity and for intellectual entertainment. One of the examples I put together for the class has a nice set of thematic F# syntax and paradigms. See the image below for a sample run.

 

 1 #light
 2 open System
 3 printfn "\nBegin F# deck of cards demo"
 4 let deck =
 5   [| for suit in ["Clubs"; "Diamonds"; "Hearts"; "Spades" ] do
 6     for rank in [1..13] do
 7     yield (rank,suit) |]
 8
 9 printfn "\nThe unshuffled deck is %A \n" deck   
10 let ro = new Random(0) 
11 let shuffle (a : (int*string) array) =
12   let len = a.Length
13   for i in 0..len-1 do
14     let r = ro.Next(i, len-1)
15     let tmp = a.[r]
16     a.[r] <- a.[i]
17     a.[i] <- tmp
18 
19 deck |> shuffle
20
21 let printDeck (d : (int*string) array) =
22   let n = d.Length
23   for i in 0..n-1 do
24     if i > 10 && i < 49 then printf "."
25     elif i = 49 then printf "\n"
26     else
27       printf "card[%d] = " i
28       if i < 10 then printf " "
29       let (rank,suit) = d.[i]
30       if rank < 10 then printf " "
31       printfn "%d of %s" rank suit
32   
33 printfn "\nThe shuffled deck is: "
34 deck |> printDeck
35
36 printfn "\nEnd deck of cards demo"
37 System.Console.ReadLine() |> ignore

 

Lines 4-7 construct a mutable array of size 52, where each cell holds a tuple composed of an int (a card value from 1-13) and a string ("Clubs", etc.) Line 9 uses the %A format specifier to instruct the F# compiler to use its own judgment on how to print the array of card tuples. Lines 11-17 define a function which uses the Fisher-Yates shuffle algorithm to shuffle an array in place. Line 19 pipes the deck to the shuffle function. Lines 21-31 define a custom print function. Line 37 points out that F# is a .NET language and can access the .NET Framework. One thing I found interesting is that, more than any language I can think of, F# has many different ways to perform programming tasks. For example, Lines 29-31:

 

let (rank,suit) = d.[i]
if rank < 10 then printf " "
printfn "%d of %s" rank suit

 

can also be coded as:

 

match d.[i] with
| (rank,suit) ->
  if rank < 10 then printf " "
  printfn "%A of %A" rank suit

 

which is more F#-ish. Anyway, F# is really interesting in many ways.

 

Based on my personal experience, I have observed a large disconnect between the fields of software testing research (the kind typically done at universities) and software testing practice (as performed by companies which actually produce software). The two groups involved -- university researchers and software test engineers -- seem particularly unaware of each other's work. Well this isn't very surprising I suppose, but I'm thinking that there should be some easy way for software testing researchers and practitioners to be learn about each other's worlds. I speak at quite a few academic conferences and many of the research papers on software testing presented there are ridiculously out of touch with present or future reality, but on the other hand there are some papers that have really interesting and potentially really useful ideas. Now in theory at least, every academic conference looks for papers from practitioners -- the "call for papers" almost always says something like, "The aim of the XYZ Conference is to bring together researchers and practitioners in an effort to highlight the state-of-the-art and to present and discuss ideas and experiences to explore new directions for blah, blah, blah." However, papers from practitioners are almost never accepted at academic conferences. One reason is that writing a good academic paper is really quite difficult. Academic researchers can spend years to produce a single paper, and you have to know the "secret ingredients" of an IEEE research paper content and format. Anyway, I'm rambling today; let me cut to the chase. I am the chair of the software testing track of the ITNG 2010 Conference and I'd love to see papers from practitioners, and I do not discriminate against authors who don't have a Ph.D. degree. If you have an idea for a paper about software testing I can help you get the idea into a formal IEEE format. See http://www.vteonline.com/ITNG2010/ for a description of the conference, and see http://www.vteOnline.com/ITNG2010/Guidelines/guidelines.html for some tips about writing a research paper.

I am a Contributing Editor for MSDN Magazine and write a monthly column about software testing. As part of my background research I talk to as many software test managers as I can. One common theme in discussions with test managers is a pitfall I'll call "the test architecture error". In simple terms, it is easy for software testers to lose sight of their primary goal: analyze a software system in order to find bugs so those bugs can be fixed and improve the quality, reliability, and performance of the target system. According to many of the managers I've talked to, some software test engineers spend far too much time designing their test effort and not nearly enough time actually testing the target software system. I know I've been guilty of this in the past. Sometimes you just have to sit down and simply test the heck out of a system and not worry about architecting a test framework of some sort. A closely related scenario occurs with test automation. It is easy to get seduced into spending weeks creating some test automation only to have your automation be rendered obsolete before it can be used. One reason this can happen is related to how the job performance of software test engineers is sometimes evaluated by inexperienced managers. By creating test automation, a tester has something tangible and often impressive to demonstrate to show progress, even if the automation is not all that useful. It is much harder to demonstrate progress with a list of test cases that may in fact be far more useful than slick test automation. My point is that test automation and test architecture are useful in many situations but may not always the best way to test a system, especially an application which will ultimately be used by actual human beings. Basically, I think that if you focus on doing those test activities that best improve the quality of your target system based on all the complicated factors of your particular development environment -- maybe manual testing, designing frameworks, writing automation, or whatever -- and carefully explain to your management exactly why you are doing what you are doing, the value of your work will be appreciated.

Cryptology is the study of cryptography (schemes for encrypting data) and cryptanalysis (schemes for breaking codes). The field is very complex and testing cryptological software requires a lot of advanced knowledge. One of the things I've was looking at recently is the topic of nonlinear Boolean functions. A Boolean function accepts any number of variables, each of which can have value of only 0 or 1, and returns a single 0 or 1 value. For example f = x1 + x2x3 means "x1 or (x2 and x3). Boolean functions can be represented in a surprising number of ways, including a truth table, an equation in Algebraic normal form, and many others. Boolean functions are a cryptographic primitive -- a fundamental construct -- used for several purposes. It turns out that Boolean functions used in cryptology should have certain properties to make the systems in which they are used less vulnerable to cryptanalysis. One such property is nonlinearity, which is the Hamming distance between a function of n variables, and all possible linear functions of n variables. Whew! Like I mentioned, cryptology is very complex.

Over the past few days I have been looking at browser based test harnesses with JavaScript to test Web applications. Specifically, I have created proof-of-concept Internet Explorer harnesses to perform HTTP request-response testing, and to perform UI testing. In both situations however I used hard-coded test case input. Over the weekend I took a look at reading external test case data, and writing test case results, from a browser-based harness. Basically there are two approaches available with Internet Explorer. First, you can read or write information on the test host machine. Second, you can read or write information on the Web application server machine. To read or write test data on the test host machine, you can use code along the lines of:

 

var result = document.getElementById('TextBox4');
var fso = new ActiveXObject('Scripting.FileSystemObject');
var infile = fso.OpenTextFile("C:\\testCases.txt", 1);
// etc.

 

If this code is located and executed on the test host, it will look for file testcases.txt on the test host.

To read or write test data on the Web server machine you can create a short ASP script which contains similar code, and then invoke the script from the test host along the lines of:

 

<form method='post' action='readData.asp' name='theForm'>
 <input type='submit' />
</form>

 

combined with:

 

var f = document.getElementById('theForm');
f.submit();

 

If this code is located and executed on the Web server, it will look for file testcases.txt on the server. There are many alternatives to browser based test harnesses, and I still don't have a solid grasp of the pros and cons involved, but the approach seems like it may be useful in certain testing scenarios.

The jQuery library is an Open Source collection of JavaScript functions that Web application developers can use to easily create neat client-side effects such as fade-in and menus. But the jQuery library can be used write lightweight test automation too. I have been looking at using jQuery to perform lightweight HTTP request-response testing. See the screenshot below for a proof-of-concept. The screenshot shows that I have a test harness in the form of an HTML page. That page references the jQuery library and contains a script that fires off an HTTP request, fetches the HTTP response, and examines the response for an expected value to produce a test case pass/fail result. This technique might be useful in situations where you want to use an HTML-based test harness rather than a shell-based or Windows Form-based test harness. Additionally, investigating test automation that uses new technologies such as jQuery helps testers stay in sync with developers who are using the new technologies.

 

I am researching the use of jQuery for Web application test automation. One of the things I need to do is access HTML elements in one frame from another frame. A search of the Internet yielded several people asking how to do this but no answers. Anyway, after about two hours of work I came up with a solution to the problem. The screenshot below shows a demo in action. The main page has two frames. When a user clicks on the Set Text button in the page in left frame, control is transferred to a jQuery function which places text into the text box control in the right frame. The key lines of code are:

 

$(document).ready(function(){
 $("#Button1").click(function(){
  $(parent.rightFrame.document).contents().find('#TextBox1').val('Hello from left frame!');
 });
});

 

Anyway, jQuery is very cool and I should have a Web application test automation article written for MSDN Magazine done in a few weeks.

 

 

You have probably heard the terms eigenvalue and eigenvector before but probably aren't sure exactly what these terms mean. They are staples of discrete mathematics courses required for computer science degrees at many universities. For years I've wondered if eigenvalues and eigenvectors have any application to software testing. I don't have an answer. Let me explain what eigenvalues and eigenvectors are, and why I suspect they might be important to software testing. Suppose you are dealing with points x = (x,y) in the two-dimensional plane. Then a 2x2 square matrix A implicitly defines a transformation of any point. Bear with me here. If there exists a vector x and a value λ (Greek letter lambda) that have the relationship Ax = λx then λ  is called an eigenvalue and x is called an eigenvector. For example, if A = [ (6,3), (-2,-1) ], and λ = 0, and x = [1,-2] the λ and x form an eigenvalue-eigenvector pair. OK, so what? One of the surprising things about eigenvalue analysis is the amazing number of real-world problems they apply to in very unexpected ways. For example, using eigenvalue analysis it was shown that the optimal shape of a building support column is curvy, somewhat like the shape of a decorative stair post. Anyway, software testing is all about state changes which can be represented mathematically as vectors and matrices. There may be some interesting and useful ways that eigenvalues and eigenvectors can be applied to software testing.

The open source jQuery library is a collection of JavaScript functions that allow Web developers to create client-side effects such as fade-in and fade-out more quickly than by using plain JavaScript code. I have been looking at using jQuery to write simple, lightweight Web application UI test automation. The main advantage of using jQuery for test automation rather than using raw JavaScript is that the functions in jQuery work with multiple browsers (IE, Safari, Firefox, etc.) The screenshot below shows an example of testing a simple Web application using jQuery. The frame on the left hosts a jQuery test harness script, and the frame on the right hosts the Web application under test. I intend to write an article for MSDN Magazine which describes all the details. 

 

 

One of the core principles of software testing is that in order to determine a pass/fail result for a test case, after executing the test case you must compare the actual result or state of the system under test with an expected result/state. For example, if you are testing the + functionality of a calculator, and the test case inputs are 3.0 and 4.0 (and the expected result is 7.0) then you exercise the SUT to get an actual result and compare that actual result with the expected result. In statistics, the most common way to compare a set of observed values with a set of expected values is to use the well-known chi-square test. However, what is not so well known is that the chi-square test is actually a discrete approximation to the log likelihood test. The chi-square test was developed in the days before calculators when computing logarithms was difficult. Anyway, the point is, in software testing, if you want to compare how close a set of actual values is to a set of expected values, you should probably use the log likelihood g-test rather than the chi-square test. The g statistic is given by 2 * (sum-over-i(Oi * ln(Oi / Ei)) where Oi is an observed value and Ei is the corresponding expected value. For example, suppose you have some system which should emit the three values (4.0, 4.0, 4.0). These are the expected values. Now if the actual results are (3.0, 4.0, 6.0) then the g-statistic is 2 * [(3.0 * ln(3.0/4.0)) + (4.0 * ln(4.0/4.0)) + (6.0 * ln(6.0/4.0))] = 3.139. The closer the g-static is to 0, the closer the actual results are to the expected results; you can look up specific probabilities if necessary.

Partitioning a set of items is a problem I run across rather often. Determining the number of ways you can partition a set of n items into k groups is a surprisingly difficult problem. Suppose you have a set of n = 4 items and want to partition those items into k = 2 groups. How many ways can you do this? There are 7 possible partitions of 4 items into 2 groups:

 

(a)   (b,c,d)
(b)   (a,c,d)
(c)   (a,b,d)
(d)   (a,b,c)
(a,b)   (c,d)
(a,c)   (b,d)
(a,d)   (b,c)

 

It turns out that the number of possible partitions is given by an equation called Stirling numbers of the second kind, S(n,k). It is an interesting function which increases very rapidly. S(4,2) = 7 and S(6,4) = 65. I was working on a problem recently with n = 435 (the number of members in the U.S. House of Representatives) and k = 2. The number of ways you can partition 435 items into 2 groups is 4.4 * 10 to the 130th power. This is an unimaginably huge number. Wikipedia has a good article on Stirling numbers of the second kind if you want to know more.

One of the challenges facing the field of software testing is the perception that test engineers have weak technical skills relative to developers and that the field has too many self-proclaimed experts who are anything but. One example is the upcoming Pacific Northwest Software Quality Conference, in Portland, OR, in October. In past years I have been quite impressed with the technical quality of the speakers at the PNSQC. I'll probably go to PNSQC but find it hard to recommend the event to others this year because the list of invited speakers appears to have been significantly dumbed-down. One quote from the PNSQC invited speakers descriptions goes, "One final secret every project manager must know—there is no 'one right way' to manage a project. Everything depends on your context." Well, there's a real intellectual gem. Another quotes goes, " Some managers who’ve never studied testing, never done testing, probably have never even *seen* testing up close, nevertheless insist that it be rigorously planned in advance and fully documented." Okay, show me some data to support this ridiculous statement. Which managers? Where do they work? What survey or data supports this claim? On the other hand, I just returned from the Software Engineering and Data Engineering (SEDE) conference which had terrific speakers who actually presented useful, new information. One such topic is the relationship between software testing and entropy. In simple terms, entropy is a measure of disorder in a system. The general equation for entropy is:

 

where b is an arbitrary base (often 2 or 10) and p(x) is the probability that some random variable X takes on value x. The math looks scary but the concepts use only freshman level mathematics and are actually very, very simple. The talk at SEDE went on to describe many highly practical ways entropy can be used in software testing scenarios to improve software quality. The perception of software testing conferences will improve when conference organizers reduce the number of fluffy talks such as "Make Your Project Successful" and increase the number of talks that provide interesting and useful new testing information.

 

The use of Web-based applications such as ASP.NET applications, Web Services, AJAX-based applications, and so on, is increasing steadily. A useful technique for testing many such applications is to send a low-level request to the SUT using TCP/IP and sockets. The technique is general-purpose because is works at a very low level of abstraction. For example, suppose you want to test some Web Service which contains a Web Method named GetTitles(). First you could set up the request in SOAP format along the lines of:

 

string input = "some input";
string soapMessage = "<?xml version=\"1.0\" encoding=\"utf-8\"?>";
soapMessage += "<soap:Envelope>";
soapMessage += "<soap:Body>";
soapMessage += "<GetTitles>";
soapMessage += "<filter>" + input + "</filter>";
soapMessage += "</GetTitles>";
soapMessage += "</soap:Body>";
soapMessage += "</soap:Envelope>";

 

Next you could set up the request destination:

 

string host = "localhost";
string webService = "/TestAuto/Ch8/TheWebService/BookSearch.asmx";
string webMethod = "GetTitles";
IPHostEntry iphe = Dns.Resolve(host);
IPAddress[] addList = iphe.AddressList; // addList[0] == 127.0.0.1
EndPoint ep = new IPEndPoint(addList[0], 80); // ep = 127.0.0.1:80

 

Then you could set up a TCP/IP socket:

 

Socket socket = new Socket(AddressFamily.InterNetwork,
 SocketType.Stream, ProtocolType.Tcp);
socket.Connect(ep);

 

And then construct the HTTP wrapper somewhat like:

 

string header = "POST " + webService + " HTTP/1.1\r\n";
header += "Host: " + host + "\r\n";
header += "Content-Type: text/xml; charset=utf-8\r\n";
header += "Content-Length: " + soapMessage.Length.ToString() + "\r\n";
header += "Connection: close\r\n";
header += "SOAPAction: \"http://tempuri.org/" + webMethod + "\"\r\n\r\n";
string sendAsString = header + soapMessage;
byte[] sendAsBytes = Encoding.ASCII.GetBytes(sendAsString);

 

And next you'd fire off the request and fetch the response:

 

int numBytesSent = socket.Send(sendAsBytes, sendAsBytes.Length,
                               SocketFlags.None);
Console.WriteLine("Sending = " + numBytesSent + " bytes\n");

byte[] receiveBufferAsBytes = new byte[512];
string receiveAsString = "";
string entireReceive = "";
int numBytesReceived = 0;

while ((numBytesReceived = socket.Receive(receiveBufferAsBytes,
 512, SocketFlags.None)) > 0 )
{
  receiveAsString = Encoding.ASCII.GetString(receiveBufferAsBytes,
   0, numBytesReceived);
  entireReceive += receiveAsString;
}

 

Your test could conclude by converting the byte[] response into a string result and analyzing the result for an expected value of some sort. Using a low-level TCP/IP and socket aproach such as I've described is often useful for security-related testing. You can be sure that someone will probe your Web-based application using this technique and so you had better test using the technique.

 

I ran across a very cool metric recently. The metric is called category utility and it can be used to measure how well a database of categorical data is clustered into a set of groups. Cluster analysis of numeric data is one of the most widely studied areas in all of data mining. With numeric data it is not too hard to measure how far one row of data, such as (1.0, 2.0, 3.0), is from another row of data, such as (5.0, -1.5, 6.0). Using a difference metric you can then create clusters of data where the data within a cluster is similar, and the data in different clusters is dissimilar. However, it's not so easy to measure how far categorical data, such as (red, small, hot) is from other categorical data, such as (blue, large, cold). Category utility is a neat idea which measures such differences based on probabilities. The equation is:

 

Each possible clustering of data will have a different categorical utility value, with larger CU values indicating better clustering. I'm looking at a research paper for the International Symposium on Visual Computing and I coded up an implementation of a category utility function in C# and the following screenshot shows it in action:

 

A few blog posts ago I described generating all possible permutations. I mentioned that the terms permutations and combinations are used incorrectly on many Web sites. A mathematical permutation of order (size) n is a rearrangement of the numbers 0 through n-1. For example, if n=3, then all possible permutations are {0,1,2}, {0,2,1}, {1,0,2}, {1,2,0}, {2,0,1}, {2,1,0}. Here I've listed the permutations in lexicographical order. A mathematical combination of order (n,k) is a subset of size k of the numbers 0 through n-1 where order does not matter. For example, all combinations of order (5,3) in lexicographical order are {0,1,2}, {0,1,3}, {0,1,4}, {0,2,3}, {0,2,4}, {0,3,4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}. Here is a class, written in C# (with error-checking removed) that will generate all possible combinations. The class can be called like this:

 

static void Main(string[] args)
{
  Console.Write("\nEnter combination n-value: ");
  int n = int.Parse(Console.ReadLine());
  Console.Write("\nEnter combination k-value: ");
  int k = int.Parse(Console.ReadLine());

  Console.WriteLine("\nAll combinations: \n");
  Combination c = new Combination(n, k);
  while (c != null) {
    Console.WriteLine(c.ToString());
    c = c.Successor();
  }

  Console.WriteLine("\nDone");
}

 

 

 

Notice the approach is to define a Successor() method which returns the next combination object, or null if we are at the last combination. Here's the class:

 

public class Combination
{
  private readonly int n;
  private readonly int k;
  private readonly int[] data;

  public Combination(int n, int k)
  {
    this.n = n;
    this.k = k;
    this.data = new int[k];
    for (int i = 0; i < k; ++i) {
      data[i] = i;
    }
  } // ctor()

  public override string ToString()
  {
    string s = "{ ";
    for (int i = 0; i < k; ++i)
      s += data[i] + " ";
    s += "}";
    return s;
  }

  public Combination Successor()
  {
    if (data[0] == n - k) // last combination element
      return null;

    Combination ans = new Combination(n, k);

    int i;
    for (i = 0; i < k; ++i)
      ans.data[i] = this.data[i];

    for (i = k - 1; i > 0 && ans.data[i] == n - k + i; --i)
      ;

    ++ans.data[i];

    for (int j = i; j < k - 1; ++j)
      ans.data[j + 1] = ans.data[j] + 1;

    return ans;
  } // Successor()

} // class Combination

 

Starting last week, I have been teaching a class to prepare software test engineers for a Certificate in Software Testing with Microsoft Technologies program. The certificate program covers 42 specific topics that were listed by test managers as those topics that testers should have at least a basic understanding of. One of those 42 topics is character encoding. Yesterday morning I decided to make a tiny demo program to use to illustrate the topic. I recalled that one of my colleagues, William Rollison, is an expert at character encoding. I visited his blog and found a tool he wrote, and I decided to (approximately) reverse engineer that tool so that I could have a simple application with source code to distribute to students in the software testing certificate program. The screenshot below shows the result.

 

 

Interestingly, the character encoding logic was simple (in part because I've investigated the topic before) but I spent an hour wrestling with the ListView data control to display results. The demo is written with C#. Here's the code:

 

private void button1_Click(object sender, EventArgs e)
{
  listView1.Items.Clear();
  int charCount = 0;
  string s = textBox1.Text;
  char[] chars = s.ToCharArray();
     
  foreach (char c in chars)
  {
    char[] arrayWithOneChar = new char[] { c };

    byte[] bytes = null;
    if (radioButton1.Checked) // ASCII
      bytes = Encoding.ASCII.GetBytes(arrayWithOneChar);
    else if (radioButton2.Checked)
      bytes = Encoding.Unicode.GetBytes(arrayWithOneChar); // Little Endian
    else if (radioButton3.Checked)
      bytes = Encoding.BigEndianUnicode.GetBytes(arrayWithOneChar);
    else if (radioButton4.Checked)
      bytes = Encoding.UTF7.GetBytes(arrayWithOneChar);
    else if (radioButton5.Checked)
      bytes = Encoding.UTF8.GetBytes(arrayWithOneChar);
    else if (radioButton6.Checked)
      bytes = Encoding.UTF32.GetBytes(arrayWithOneChar);
 
    string bytesForACharInHex = "";
    string bytesForACharInDecimal = "";
    foreach (byte b in bytes)
    {
      bytesForACharInHex += b.ToString("X2") + " ";
      bytesForACharInDecimal += b.ToString() + " ";
    }
    listView1.Items.Add(new ListViewItem(new string[] { charCount.ToString(), c.ToString(), bytesForACharInHex, bytesForACharInDecimal }));
    ++charCount;
  } // next char
    
} // button1_Click()

 

Two of the most common and fundamental programming tasks are generating all possible permutations, and generating all possible combinations. Last week I spent some time looking at what I'd find on the Internet about these two problems. I was surprised by the large number of Web pages and blogs which have really, really bad information. First, the terms permutations and combinations, are used incorrectly on many Web sites. A mathematical permutation of order (size) n is a rearrangement of the numbers 0 through n-1. For example, if n=3, then all possible permutations are {0,1,2}, {0,2,1}, {1,0,2}, {1,2,0}, {2,0,1}, {2,1,0}. Here I've listed the permutations in lexicographical order. A mathematical combination of order (n,k) is a subset of size k of the numbers 0 through n-1 where order does not matter. For example, all combinations of order (5,3) in lexicographical order are {0,1,2}, {0,1,3}, {0,1,4}, {0,2,3}, {0,2,4}, {0,3,4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}. Anyway, listed below is a tiny class, written in C#, with error-checking removed, that will generate all possible permutations. The class can be called like this:

 

static void Main(string[] args)
{
  Console.Write("\nEnter permutation order (n): ");
  int n = int.Parse(Console.ReadLine());

  Console.WriteLine("\nAll permutations: \n");
  Permutation p = new Permutation(n);
  while (p != null) {
    Console.WriteLine(p.ToString());
    p = p.Successor();
  }

  Console.WriteLine("\nDone");
}

 

 

 

Notice the approach is to define a Successor() method which returns the next permutation object, or null if we are at the last permutation. Here's the class:

 

public class Permutation
{
  public readonly int n;
  public readonly int[] data;

 

  public Permutation(int n) {
    this.n = n;
    this.data = new int[n];
    for (int i = 0; i < n; ++i)
      data[i] = i;
  }

 

  public override string ToString()
  {
    string s = "( ";
    for (int i = 0; i < n; ++i)
      s += data[i] + " ";
    s += ")";
    return s;
  }

 

  public Permutation Successor()
  {
    Permutation result = new Permutation(n);
    int left, right;

    for (int i = 0; i < n; ++i)
      result.data[i] = this.data[i];
     
    left = result.n- 2;  // Step #1 - Find left value
    while ((result.data[left] > result.data[left + 1]) && (left >= 1))
      --left;
     
    if ((left == 0) && (this.data[left] > this.data[left + 1]))
      return null;

    right = result.n - 1;  // Step #2 - find right value
    while (result.data[left] > result.data[right])
      --right;
     
    int temp = result.data[left];  // Step #3 - left and right
    result.data[left] = result.data[right];
    result.data[right] = temp;
     
    int x = left + 1;              // Step #4 - order the tail
    int y = result.n - 1;

    while (x < y) {
      temp = result.data[x];
      result.data[x++] = result.data[y];
      result.data[y--] = temp;
    }

    return result;
  }

} // Permutation