Math objects on programming (1)

Abstract:

Using mathematical objects often makes a program simpler. This time I have such experience and write it down here.

Mathematical object and programming

In a program test, we often need to generate a combination of input parameter sets. One of the most easy method to generate a combination is using nested loops.

In this article, I use pseudo code based on the Python language. I will provide the real implementation of the program in the appendix.

For example, we have following two parameter sets:

 data_size_list = [ 5, 64, 512, ]
 screen_resolution_list = [ 
   '2560x1440', '3840x2160', ].

The following program can generate the combination of them:

  for d in data_size_list:
    for s in screen_resolution_list:
      print_comb(d, s) # output

This method is simple and straightforward, however, less flexible in some cases. For example, we don't know which sets are necessary to generate a combination when the program is written. To overcome this problem, we can use an algorithm, direct product, to generate a combination [1]．Let's assume there are \(k\)-sets and we want to know all the combination of these \(k\) set's elements. We can define such combination as the following:

1. \(k = 0\), this means 0 sets. The direct product result is one empty list ([]).
2. \(k \geq 1\), \begin{eqnarray*} A_1 \times \cdots \times A_k &=&\left\{(a,t)| a \in A_1, t \in A_2 \times \cdots \times A_k \right\}\end{eqnarray*}

The second condition means that if we have an element combination list from \(k-1\) sets, then we can add one more element (\(a\)) from the \(k\)'s set to generate an element combination list from the \(k\) sets.

An implementation example is the following:

data_size_list = [ 5, 64, 512, ]
screen_resolution_list = [ 
   '2560x1440', '3840x2160', ]
all_list = [
  data_size_list,
  screen_resolution_list,
]
comb_list = []
c_tuple = [''] * len(all_list) 

def make_tuple(idx):
  if(idx >= len(all_list)):
    comb_list.append(
        copy.deepcopy(c_tuple))
  else:
    for i in range(len(all_list[idx])):
      c_tuple[idx] = all_list[idx][i]
      make_tuple(idx + 1)

def gen_combination_list():
    make_tuple(0)
    for i in comb_list:
        print i

make_tuple() function is the implementation of the direct product.

The direct product is an mathematical object. I generalized the process of generating combinations. In direct product code, the number of nesting of for-loop is depends on the input data. This means, the number of nested loops is defined by the input data. We often change the test case depends on the situation. The for-loop implementation needs to change the code every time and this direct product implementation doesn't need to change the code. This example is too simple and you might not see the necessity, however, my case needed a flexibility and this paid off.

Next time, I will explain how I mistook the mathematical object in this program.