Cartesian Product with Groovy

In what follow a groovy script to perform cartesian product of variables A,B,C,.. each one with differnt values is presented. The script should be compared with the analog Python or C++ programs.

Following the code with all the comments inside.

#!/usr/bin/groovy
/**
 * This is a simple groovy script calculating combinations of variables A,B,C,... written 
 * in a file test.txt in the
 * following format:
 *
 *  ##########################
 *  # Example file test.txt
 *  ##########################
 *
 *  # Variable A
 *  A:1,2,3
 *
 *  # Variable B
 *  B:a,b,c
 *
 *  # Variable C
 *  C:11,12,13,14,15
 *
 *  # Variable D
 *  D:aa,bb,cc
 *
 *  # Variable E
 *  E:a1,b1,c1,d1,d3,d4
 *
 * The variable must be separated from the list of value with a colon ":", while 
 * the list elements must be separated with a coma ","
 *
 * For example
 *   A:1,2,3,4
 * define the variable A that should get the values 1,2,3,4
 *
 * The # char is used to insert comments in the file, where is also possible to 
 * add how many blank lines as you want to improve readability.
 *
 * Programs must be called with:
 *
 *                              groovy ProdCart.groovy -f test.txt
 *
 * The output is printed on standard output and is possible to re-pipe it in file using 
 * standard *ix (or windows) > and >> operators.
 *
 */

// Print out error if input parameters are not correct
// Look at: http://www.javaworld.com/article/2074004/core-java/customizing-groovy-s-clibuilder-usage-statements.html
def cli = new CliBuilder(
        usage: 'ProdCart -f fileName',
        header: '\nAvailable options (use -h for help):\n',
        footer: '\nInformation provided via above options is used to generate printed string.\n')
//import org.apache.commons.cli.Option
cli.with
        {
            h(longOpt: 'help', 'Usage Information', required: false)
            f(longOpt: 'file', 'File Name', args: 1, required: true)
        }
def opt = cli.parse(args)

if (!opt) return
if (opt.h) cli.usage()

// Variable declaration
def inputFile = opt.f
def cont = 0
def arrHeader = []
def arrItems = [ [] , [] ]
def permutazioni = [ [] ]

// Read the string in the input file
File inFile = new File(inputFile)

String[] arrLines = inFile.readLines()
arrLines.each {line ->
    if(!line.startsWith("#") && !line.empty) {
        def arrHeaderItems = line.tokenize(":")
        arrHeader << arrHeaderItems[0]
        arrItems[cont] = arrHeaderItems[1].tokenize(",")
        cont += 1
    }
}

// Load permutation array with arrItems
arrItems.each {item ->
    permutazioni << item
}

// Print combinations with header
println arrHeader.join(",\t")

permutazioni.combinations().each { comb ->
            println comb.toString().replace(" ","").replace("[","").replace("]","").replace(",",",\t")
}

Following the downloadable code and example imput file
Attachments:
FileDescriptionFile sizeDownloadsCreated
Download this file (ProdCart_Groovy.zip)ProdCart with GroovyA simple Groovy script to calculate cartesian product of N variables defined in a file1 kB7092016-06-20 15:12

Minimum Pair Wise test set calculation and (possible) connections with Graph Theory

The problem we will engage here is the following: having N variables with different values each one, what is – if exist – a minimal test set allowing a full pair wise coverage? In other words, consider the following table:

A_1 A_2 A_3 A_K
1 1 1   1
2 2 2   2
N1 N2 N3 NK

 K variables with different values each ones

Consider now the ordered sequence (N1, N2, N3, …, NK) where N1 ≥ N2 ≥ N3 ≥ … > NK. We may expect that the minimal pair wise test set has no more and no less than N1●N2 test cases. In the following for “Minimal Pair Wise Test Set” we consider not a generic test set that should be extracted with some kind of algorithm, but the test set for which each variables pairs appears one and only one times. In other words, the frequency map of all variables pair is exactly equal to one. This should be a little importance for practical test problems, but it should be interesting from a theoretical point of view. For example, for the variables and values below:

A_1 A_2 A_3 A_4
1 1 1 1
2 2 2 2
3 3 3  
4 4 4  
5      

4 variables with different values each ones as Example

We forecast a minimum test set is composed by 5●4 = 20 test cases.

Such minimal test cases exist in some particular cases, for example when we have 4 variables with 3 values each one (as we will see in the following paragraph), so the answer to the question should not be always “YES” or always “NO”. Investigating on the problem, using the IPOG algorithm used by NIST ACTS tool, we will find a correlation among: combinatorial pair wise problems, k-partite graph (Graph Theory) and prime number.

As an empirical conjecture (so, not a well-proofed theorem) we will find that there is a solution of the problem (which we will call in the following “Minimal Pair Wise Problem), when:

  • We have N variables with N values or (N+1) variables with N values each.
  • N is prime
  • Finding solution for the Minimal Pair Wise Problem for N variables with N values means find the Hamiltonian Circuits for KN,N,…N (with N indexes) Kuratowski’s graph.
  • The solution for the Minimal Pair Wise Problem for (N+1) variables with N values do not imply the existence of Hamiltonian Circuits for KN,N,…N (with N+1 indexes) Kuratowski’s graph.

Connections between Graph Theory and pair wise testing was already discussed in the article “Pairwise Test Set Calculation using k-partite Graphs” written by Elke Salecker, Sabine Glesner (TU Berlin), 2010 IEEE International Conference on Software Maintenance (ICSM)” but with a different purpose.

For Graph Theory definitions and theorems we referred the book: “Graph Theory, with applications to engineering and computer science “ – Narsingh Deo – PHI Editions.

Attached the complete article, freely downloadable. Welcome to any comments and/or corrections and/or advices.

Attachments:
FileDescriptionFile sizeDownloadsCreated
Download this file (Pairwise_Thought.zip)M.P.T.Minimum Pair Wise test set calculation and (possible) connections with Graph Theory756 kB3452015-12-28 09:30

C++ and Binary Files

In what follows it's reported a simple C++ programs that write and read a long int and an int into a binary file. In the program list we do not manage error conditions, like file that does not exist, error on writing file, ... because out of scope for this short article, focused on reading and writing binary data on file using C++


#include <iostream>
#include <fstream>
#include <climits>
#include <string>
#include <bitset>

using namespace std;

int main()
{

    // CONSTANT
    const std::string FILE_NAME = "file.bin";

    // Variable declaration
    unsigned long lngNum   = 0;
    unsigned int  intNum   = 0;


    // Notes on consolle
    cout <<  "Total sizeof: " << sizeof(lngNum) << " + " << sizeof(intNum) << endl;


    // ******************
    // ** WRITING FILE **
    // ******************
    cout << "Writing binary file..." << endl;
    ofstream file_o (FILE_NAME, ios::binary);
    for (int i=0;  i<16; ++i){

        // Insert numbers starting from MAX ot the corresponding type
        lngNum = (ULONG_MAX-15) + i;  //ULONG_MAX
        intNum = (UINT_MAX -15) + i;  //UINT_MAX

        // Write binary file
        file_o.write (reinterpret_cast<const char *>(&lngNum), sizeof(lngNum));
        file_o.write (reinterpret_cast<const char *>(&intNum), sizeof(intNum));

        // Print out data
        cout << "lngNum decimal     = "             << lngNum             << " - intNum decimal     = " << intNum << endl;

    }
    // Closing file
    file_o.close ();


    // ******************
    // ** READING FILE **
    // ******************
    lngNum = 0;     // ... just to clear variable
    intNum = 0;

    cout << "Reading binary file..." << endl;
    ifstream file_i (FILE_NAME, ios::binary);
    if(file_i.is_open()){

        // Cycle on file
        while(true){

            // Read data into a long and int
            file_i.read(reinterpret_cast<char *>(&lngNum),sizeof(lngNum));
            file_i.read(reinterpret_cast<char *>(&intNum),sizeof(intNum));

            // Exit if EOF
            if(file_i.eof()) {
                break;
            }

            // Print out data
            cout << "lngNum = " << endl;
            cout << std::dec << "\t decimal     = " << lngNum  << endl;
            cout << std::hex << "\t hexadecimal = " << lngNum  << endl;
            cout << std::oct << "\t octal       = " << lngNum  << endl;
            cout <<             "\t binary      = " << std::bitset< sizeof(lngNum)*8 >( lngNum )       << endl;

            cout << "intNum = " << endl;
            cout << std::dec << "\t decimal     = " << intNum                                          << endl;
            cout << std::hex << "\t hexadecimal = " << intNum                                          << endl;
            cout << std::oct << "\t octal       = " << intNum                                          << endl;
            cout <<             "\t binary      = " << std::bitset< sizeof(intNum)*8 >( intNum )       << endl;

            cout << "******************************************************************************"   << endl;
        }
    }
    // Closing file
    file_i.close ();

    return 0;
}


In more details, in the first part (writing file) the two variables are written 16 times and we can think at the file as composed by sixteen “rows” each with two “columns” with the first having the “long int” value and the second having the “int” value.
In the second part (reading file) the two  variables are read “line by line” and printed out.

Take care that a binary file cannot be subdivided by “lines” or “rows”. All bits 1/0 are in sequence, so thinking at it “by row” is just a virtual way to interpret it. With some little arrangement, the script should be useful to dump binary file in different format (if the standard tools xxd, hexdump, od, … and others that for sure exist and that I do not know are not “good enough” for you :-))) ).

The output is the following:

Total sizeof: 8 + 4

Writing binary file...

lngNum decimal     = 18446744073709551600 - intNum decimal     = 4294967280
lngNum decimal     = 18446744073709551601 - intNum decimal     = 4294967281
lngNum decimal     = 18446744073709551602 - intNum decimal     = 4294967282
lngNum decimal     = 18446744073709551603 - intNum decimal     = 4294967283
lngNum decimal     = 18446744073709551604 - intNum decimal     = 4294967284
lngNum decimal     = 18446744073709551605 - intNum decimal     = 4294967285
lngNum decimal     = 18446744073709551606 - intNum decimal     = 4294967286
lngNum decimal     = 18446744073709551607 - intNum decimal     = 4294967287
lngNum decimal     = 18446744073709551608 - intNum decimal     = 4294967288
lngNum decimal     = 18446744073709551609 - intNum decimal     = 4294967289
lngNum decimal     = 18446744073709551610 - intNum decimal     = 4294967290
lngNum decimal     = 18446744073709551611 - intNum decimal     = 4294967291
lngNum decimal     = 18446744073709551612 - intNum decimal     = 4294967292
lngNum decimal     = 18446744073709551613 - intNum decimal     = 4294967293
lngNum decimal     = 18446744073709551614 - intNum decimal     = 4294967294
lngNum decimal     = 18446744073709551615 - intNum decimal     = 4294967295

Reading binary file...

lngNum = 
	 decimal     = 18446744073709551600
	 hexadecimal = fffffffffffffff0
	 octal       = 1777777777777777777760
	 binary      = 1111111111111111111111111111111111111111111111111111111111110000
intNum = 
	 decimal     = 4294967280
	 hexadecimal = fffffff0
	 octal       = 37777777760
	 binary      = 11111111111111111111111111110000
******************************************************************************
lngNum = 
	 decimal     = 18446744073709551601
	 hexadecimal = fffffffffffffff1
	 octal       = 1777777777777777777761
	 binary      = 1111111111111111111111111111111111111111111111111111111111110001
intNum = 
	 decimal     = 4294967281
	 hexadecimal = fffffff1
	 octal       = 37777777761
	 binary      = 11111111111111111111111111110001
******************************************************************************
lngNum = 
	 decimal     = 18446744073709551602
	 hexadecimal = fffffffffffffff2
	 octal       = 1777777777777777777762
	 binary      = 1111111111111111111111111111111111111111111111111111111111110010
intNum = 
	 decimal     = 4294967282
	 hexadecimal = fffffff2
	 octal       = 37777777762
	 binary      = 11111111111111111111111111110010
******************************************************************************
lngNum = 
	 decimal     = 18446744073709551603
	 hexadecimal = fffffffffffffff3
	 octal       = 1777777777777777777763
	 binary      = 1111111111111111111111111111111111111111111111111111111111110011
intNum = 
	 decimal     = 4294967283
	 hexadecimal = fffffff3
	 octal       = 37777777763
	 binary      = 11111111111111111111111111110011
******************************************************************************
lngNum = 
	 decimal     = 18446744073709551604
	 hexadecimal = fffffffffffffff4
	 octal       = 1777777777777777777764
	 binary      = 1111111111111111111111111111111111111111111111111111111111110100
intNum = 
	 decimal     = 4294967284
	 hexadecimal = fffffff4
	 octal       = 37777777764
	 binary      = 11111111111111111111111111110100
******************************************************************************
lngNum = 
	 decimal     = 18446744073709551605
	 hexadecimal = fffffffffffffff5
	 octal       = 1777777777777777777765
	 binary      = 1111111111111111111111111111111111111111111111111111111111110101
intNum = 
	 decimal     = 4294967285
	 hexadecimal = fffffff5
	 octal       = 37777777765
	 binary      = 11111111111111111111111111110101
******************************************************************************
lngNum = 
	 decimal     = 18446744073709551606
	 hexadecimal = fffffffffffffff6
	 octal       = 1777777777777777777766
	 binary      = 1111111111111111111111111111111111111111111111111111111111110110
intNum = 
	 decimal     = 4294967286
	 hexadecimal = fffffff6
	 octal       = 37777777766
	 binary      = 11111111111111111111111111110110
******************************************************************************
lngNum = 
	 decimal     = 18446744073709551607
	 hexadecimal = fffffffffffffff7
	 octal       = 1777777777777777777767
	 binary      = 1111111111111111111111111111111111111111111111111111111111110111
intNum = 
	 decimal     = 4294967287
	 hexadecimal = fffffff7
	 octal       = 37777777767
	 binary      = 11111111111111111111111111110111
******************************************************************************
lngNum = 
	 decimal     = 18446744073709551608
	 hexadecimal = fffffffffffffff8
	 octal       = 1777777777777777777770
	 binary      = 1111111111111111111111111111111111111111111111111111111111111000
intNum = 
	 decimal     = 4294967288
	 hexadecimal = fffffff8
	 octal       = 37777777770
	 binary      = 11111111111111111111111111111000
******************************************************************************
lngNum = 
	 decimal     = 18446744073709551609
	 hexadecimal = fffffffffffffff9
	 octal       = 1777777777777777777771
	 binary      = 1111111111111111111111111111111111111111111111111111111111111001
intNum = 
	 decimal     = 4294967289
	 hexadecimal = fffffff9
	 octal       = 37777777771
	 binary      = 11111111111111111111111111111001
******************************************************************************
lngNum = 
	 decimal     = 18446744073709551610
	 hexadecimal = fffffffffffffffa
	 octal       = 1777777777777777777772
	 binary      = 1111111111111111111111111111111111111111111111111111111111111010
intNum = 
	 decimal     = 4294967290
	 hexadecimal = fffffffa
	 octal       = 37777777772
	 binary      = 11111111111111111111111111111010
******************************************************************************
lngNum = 
	 decimal     = 18446744073709551611
	 hexadecimal = fffffffffffffffb
	 octal       = 1777777777777777777773
	 binary      = 1111111111111111111111111111111111111111111111111111111111111011
intNum = 
	 decimal     = 4294967291
	 hexadecimal = fffffffb
	 octal       = 37777777773
	 binary      = 11111111111111111111111111111011
******************************************************************************
lngNum = 
	 decimal     = 18446744073709551612
	 hexadecimal = fffffffffffffffc
	 octal       = 1777777777777777777774
	 binary      = 1111111111111111111111111111111111111111111111111111111111111100
intNum = 
	 decimal     = 4294967292
	 hexadecimal = fffffffc
	 octal       = 37777777774
	 binary      = 11111111111111111111111111111100
******************************************************************************
lngNum = 
	 decimal     = 18446744073709551613
	 hexadecimal = fffffffffffffffd
	 octal       = 1777777777777777777775
	 binary      = 1111111111111111111111111111111111111111111111111111111111111101
intNum = 
	 decimal     = 4294967293
	 hexadecimal = fffffffd
	 octal       = 37777777775
	 binary      = 11111111111111111111111111111101
******************************************************************************
lngNum = 
	 decimal     = 18446744073709551614
	 hexadecimal = fffffffffffffffe
	 octal       = 1777777777777777777776
	 binary      = 1111111111111111111111111111111111111111111111111111111111111110
intNum = 
	 decimal     = 4294967294
	 hexadecimal = fffffffe
	 octal       = 37777777776
	 binary      = 11111111111111111111111111111110
******************************************************************************
lngNum = 
	 decimal     = 18446744073709551615
	 hexadecimal = ffffffffffffffff
	 octal       = 1777777777777777777777
	 binary      = 1111111111111111111111111111111111111111111111111111111111111111
intNum = 
	 decimal     = 4294967295
	 hexadecimal = ffffffff
	 octal       = 37777777777
	 binary      = 11111111111111111111111111111111
******************************************************************************

Regarding xxd this is a short script to convert binary data interpreted as exadecimal (the first 12 byte, but you can change as you want) in decimal.

xxd -c 12 -p -u file.bin > out.sh ; sed -i -e 's/^/echo "ibase=16;/' out.sh ; sed -i -e 's/$/" | bc/' out.sh ; chmod +x out.sh; ./out.sh ; rm out.sh

Big Number C++ library

This article - or better the downloadable attachments - describe the behavior of a BigNumber C++ library – called bn.h that is an acronym for Big Number - developed by myself, performing the standard four operations: sum, subtraction, multiplication and division between two BIG NUMBERS (in the following B.N.) using the standard well-know-lower-school-teached-algorithms. The definition of B.N. is: number with a quantity of digits that it's impossible and/or difficult to deal with them as usual C++ - signed or unsigned -  long double number, bigger than LDBL_MAX and/or lesser than LDBL_MIN.

Now,  considering  that  LDBL_MAX/MIN  are  platform  dependent  –  the  values  are  different  for different machines architecture – as a rule of thumbs those values are about: LDBL_MIN=3.3621e-4932 and LDBL_MAX=1.18973e+4932; in practical problems this is not an issue. Some problems start to come up when you consider the precision; for a  C++ long double type the precision – that is always platform dependent – has usually the value of 18. This value is the “number  of  digits  (in  decimal  base)  that  can  be  represented  without  change”   (from http://www.cplusplus.com/reference/limits/numeric_limits/).  In  more  technical  words,  the  C++ code:

#include <climits>
std::cout << "long double minimum   = " << std::numeric_limits<long double>::min() << std::endl;
std::cout << "long double maximum   = " << std::numeric_limits<long double>::max() << std::endl;
std::cout << "long double precision = " << std::numeric_limits<long double>::digits10 << std::endl;

Produces:

long double minimum   = 3.3621e-4932
long double maximum   = 1.18973e+4932
long double precision = 18

So, rephrasing, the following B.N. definition should be used: is a B.N. any number that has to be used in calculations requiring a precision greater than the precision of a C++ long double type.

Functions  in  bn.h library  are  NOT  THREAD  SAFE,  because  they  use  variables  passed  by reference. It will not be difficult to “transform” those functions in “thread-safe”, replacing the return value of each function with a C++ structs; should be this behavior will be adjusted –time allowing– in a next release.

All the  primary functions  - that are: SumB(), SubB(), MulB(), InvB(), DivB() -  are located in the core module “bn.h”; in the module “functions.h” are located secondary functions- in this release just one function  PowB() -  that are considered secondary because functions that call primary functions to operate.

Just to give you a taste of the library usage, the following is a call to MulB() function performing product between two B.N.

strNum1       = "1234567890";
strNum2       = "1234567890.1010";
bolSignNum1   = true;
bolSignNum2   = false;
bolSignResult = false;
isError       = false;
strSeparator  = ".";

strResult = MulB(strNum1,strNum2,bolSignNum1,bolSignNum2,bolSignResult,isError,strSeparator);
cout << strNum1 << " * (-" << strNum2 << ") = " << strResult << endl;
cout << "bolSignResult = " << bolSignResult << endl;
cout << "isError       = " << isError       << endl;

Results is:

1234567890 * (-1234567890.1010) = 1524157875143743456.89
bolSignResult = 0
isError       = 0

Library (source code) and User/Reference Manual should be downloaded at the bottom of current article. The project was developed using Code::Block and the source code include the CodeBlock complete project.

This code is released under GPL version 3 - Copyright (C) 2015 Berta Danilo

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

See the GNU General Public License for more details.

Attachments:
FileDescriptionFile sizeDownloadsCreated
Download this file (BN_Manual.pdf)U-RMC++ Big Number Library User & Reference Manual238 kB8822015-09-11 12:24
Download this file (CppBigNumbersLibrary.zip)BNC++ Big Number Library source code (basic four operations)908 kB2852015-09-11 12:22