msum using sliding window in kdb+

I implemented the msum verb in kdb+ using the sliding window code.

First step is to find the sliding window function in q using scan operator :

q)sw:{{1 _ x, y}\[x#0;y]}

q)y
1 6 21 56

The first argument of the internal diadic function is x 0’s and the second argument is the list y.

On the first scan, the internal function gets applied on x 0’s and y[0]. On the second scan, it gets applied on the output of the first scan and y[1] and hence, it continues.

Results :

q)sw[3;y]
0 0 1
0 1 6
1 6 21
6 21 56
q)sw[2;y]
0 1
1 6
6 21
21 56
q)sw[1;y]
1
6
21
56

Now, using this to calculate the msum function in q :

q)y
1 6 21 56
q)2 msum y
1 7 27 77
q)sum each sw[2;y]
1 7 27 77

msum is used to calculate the N-item moving sum on list y where N is the first argument. In this case, it is 2.

Point to ponder on :

mdev is a function which calculates the moving deviation. However, it cannot be implemented using this sliding window code directly. It needs some tweaks. :-)
Follow @novieq13

N Queens : all possible solutions in q/kdb+

I have written the code to generate all possible solutions for the N Queens problem. I have used backtracking approach, which allows me to generate all the solutions. Whenever, a solution is found I print it and then backtrack to search the solution space.

Code :
isconsistent:{[q;n] $[(count where q=q[n])>1;0b;{$[(abs(q[x]-y))=(abs(x-q?y));0b;1b]}[n] each q except q[n]]}

/isconsistent validates a new solution

nqueens:{[q;n;N] $[n=N;show q;{q[x]:z;$[min isconsistent[q;x];[nqueens[q;x+1;y];$[(x+1)=y;;q[x+1]:-100;];];] }[n;N]each til N];}

/backtracks and searches the solution space

Running it :
q:4#-100
nqueens[q;0;4]

Output :
1 3 0 2
2 0 3 1

The output corresponds to the following configurations,respectively, each of the values denoting the column and the index denoting the row :
* Q * *
* * * Q
Q * * *
* * Q *

* * Q *
Q * * *
* * * Q
* Q * *

Shorter Code to Generate all Permutations of a string in q/KDB+

My new Solution :

perm:{[s] $[(count s)=1;s;raze {(first x),/:perm 1_x}each (rotate[1]\)s]}

My old Solution :

perm:{[s] $[(count s)=1;s;[p:(rotate[1]\)s;raze((string first each p),/:’perm each 1_/:p)]]}

Variant of my old Solution :

perm:{[s] $[(count s)=1;s;[p:(rotate[1]\)s;raze((string first each p),/:’.z.s each 1_/:p)]]}

The .z.s function calls self and can be used here to call perm.

This solution is posted in this blog post.

The new code is much shorter and does not use multilevel lists the way I was doing initially. Besides, I also use the code execution rule from right to left in q more efficiently here. I like this one ! :)

 

 

Result :
perm “abcd”
“abcd”
“abdc”
“acdb”
“acbd”
“adbc”
“adcb”
“bcda”
“bcad”
“bdac”
“bdca”
“bacd”
“badc”
“cdab”
“cdba”
“cabd”
“cadb”
“cbda”
“cbad”
“dabc”
“dacb”
“dbca”
“dbac”
“dcab”
“dcba”

Exponential Smoothing in q/KDB+

The formula for exponential smoothing is :
S(1) = Y(0)
S(t) = Alpha * Y(t) + (1-Alpha) S(t-1)

1) The corresponding solution in Q is :
es:{{(x*z)+(1-x)*y}[x]\[y]}
where, x is the smoothing factor(Alpha) and y is the list containing the time series data.

Function call in Q : es[.8;13 16 19 23 25]

Result :

13
15.4
18.28
22.056
24.4112

2) Solution 2 in Q : es:{{y+x*z-y}[x]\[y]}

es[.8;13 16 19 23 25]

Result :

13
15.4
18.28
22.056
24.4112

Applications : Exponential smoothing is commonly applied to financial markets data.

References : The wikipedia article on exponential smoothing gives both the function definitions used here.

Generate all subsets of a string in q/KDB+

Input : “abc”

Here, the elements “a”,”b”,”c” represent the elements of the set.

Output :

“abc”, “ab”,”ca”,”bc”,”a”,”b”,”c”,””.

The output represents all subsets of the set containing the elements “abc”.

Q Code :

subsets:{[s1;s2] $[(count s2)=0;show s1;[.z.s[string `$s1,(first s2);1_s2];.z.s[s1;1_s2]]]}

Run it :

subsets[“”;”abcd”]

 

Cumulative Normal Distribution in Q/KDB+

I have implemented the numerical approximation for the normal cumulative distribution function(cdf) here.
Normal cdf is very important in financial mathematics because of its applications, one of them being in Black Scholes pricing.

Mathematically, can be expressed as :

Q code implementing

q)phi
{[x] pi:3.14;(exp -1*x*x%2)%(sqrt 2*pi)}

q)cdf:{[x] b0:0.2316419; b:0.31938153 -0.356563782 1.781477937 -1.821255978 1.33
0274429; $[x<0;1 – cdf neg x; [t:1%(1+b0*x); 1 – phi[x]*{sum b * t xexp x}[1+ ti
l count b]]]}

Regular Expressions in q/KDB+

The verb like is used for matching regular expressions in q/KDB+.

Usage : X like Y.

Reserved characters for pattern matching in q :
a) “?” matches a character
b) “*” matches a sequence of characters
c) “[]” is used to list alternatives, ex: [ab] means a or b
d) “^” at the beginning of a list in brackets indicates characters that are not to be matched

Other functions used for pattern matching are :
a) ss : The function ss finds positions of a substring within a string.

b) ssr : The function ssr does search and replace on a string.

I came across an utility which can be used for perl-compatible regular expressions(PCRE) in q.
Here’s the link.

The power of the like operator comes from the fact that the left argument can be
a) a symbol atom or vector
b) a char vector or list of char vectors
c) a dictionary whose value is a symbol vector, or list of char vectors.

Hence, as shown in the kx systems documentation searching a list of telephone book entries is so simple:
q)tb
“Smith John 101 N Broadway Elmsville 123-4567″
“Smyth Barbara 27 Maple Ave Elmstwn 321-7654″
“Smythe Ken 321-a Maple Avenue Elmstown 123-9999″
“Smothers 11 Jordan Road Oakwood 123-2357″
“Smith-Hawkins K Maple St Elmwood 321-832e”

q)tb like “Smith*”
10001b

The result shows which entry has the name “Smith” in it and that too in just a few characters.

Equality of Strings in q/KDB+

I came across an error and in the process of solving it discovered more about regular expressions in q.

I will list the problem first. I created a fictitious table named t for the same.

q)t
sym price volume
———————
“IBM” 100 100
“APPLE” 200 100
“GOOGLE” 200 200

Now I wish to select the sym named “IBM” from the table and list all its columns. The approach I tried initially is :

q)select from t where sym=”IBM”
‘type
=
(“IBM”;”APPLE”;”GOOGLE”)
“IBM”

However, = does not hold for Strings in q/KDB+. Instead it supports the ‘like’ operator. The correct method in this case would be :

q)select from t where sym like “IBM”
sym price volume
——————
“IBM” 100 100