Patterns of algorithms:
sequence -> sequence
Copy
Used to process all the elements of a sequence using a transformation function. E.g. get square of every element or convert all elements to lowercase.
Input
Postcondition
Implementation
for (int i = 0; i < X.Length; i++){
Y[i] = F(X[i]);
}Note
Copy can be used to transform multiple sequences into a single sequence. The only difference is that input is a set of sequences instead of a single sequence. E.g. sum two vectors
Multiple item selection (MIS)
Used to select multiple elements from a sequence based on a certain condition. Resulting sequence can be shorter or same length as the original sequence. Therefore MIS implements Counting PoA, because we need separate indexing for the original and resulting sequences.
Input
Postcondition
Short notation:
Implementation
int cnt = 0;
for (int i = 0; i < X.Length; i++){
// simple conditional expression can be used
// instead of a function call F(X[i])
if (F(X[i])){
Y[cnt] = X[i];
cnt++;
}
}Partitioning
Used to split a sequence into two sequences based on a certain condition. E.g. split a list of numbers into even and odd numbers.
Input
Postcondition
Short notation:
Implementation
int cnt = 0;
for (int i = 0; i < X.Length; i++){
// simple conditional expression can be used
// instead of a function call F(X[i])
if (F(X[i])){
Y[cnt] = X[i];
cnt++;
} else {
Z[i - cnt] = X[i];
}
}Note
Partitioning can be used to within a single sequence. Instead of two resulting sequences, we have two partitions within the same sequence. E.g. rearrange collection so even numbers are placed before odd numbers.
Intersection
Used to find common elements or elements with a common attribute between two sequences.
Input
Postcondition
Implementation
int cnt = 0;
for (int i = 0; i < X.Length; i++){
for (int j = 0; j < Y.Length; j++){
// simple conditional expression can be used
// instead of a function call F(X[i], Y[j])
if (F(X[i], Y[j])){
Z[cnt] = X[i];
cnt++;
}
}
}Union
Used to combine two sequences into a single sequence. Repeated elements that exist in both sequences are not duplicated in the resulting sequence.
Input
Postcondition
Implementation
int cnt = 0;
for (int i = 0; i < X.Length; i++){
// simple conditional expression can be used
// instead of a function call F(X[i], Y[j])
// e.g. X[i] != Y[j]
if (F(X[i], Y[j])){
Z[cnt] = X[i];
cnt++;
}
}
for (int j = 0; j < Y.Length; j++){
Z[cnt] = Y[j];
cnt++;
}Note
There are order-preserving implementations of union, but they are more complicated. E.g. order-preserving merge of two sorted sequences.
Implementation
int i = 0;
int j = 0;
int cnt = 0;
while (i < X.Length && j < Y.Length){
// if X[i] is smaller than Y[j] take X[i] and increment X index
if (X[i] < Y[j]){
Z[cnt] = X[i];
i++;
// if Y[j] is smaller than X[i] take Y[j] and increment Y index
} else if (X[i] > Y[j]){
Z[cnt] = Y[j];
j++;
// if X[i] and Y[j] are equal take either one and increment both indices
} else {
Z[cnt] = X[i];
i++;
j++;
}
cnt++;
}Set transformation
Used to transform a sequence into a set. E.g. remove duplicates from a sequence.
Input
Postcondition
Implementation
int cnt = 0;
for (int i = 0; i < X.Length; i++){
// F(Y[..cnt], X[i]) is a function that implements decision PoA
// it returns true if X[i] is not in Y[..cnt]
// Y[..cnt] contains elements that were already processed up to this point
if (F(Y[..cnt], X[i])){
Y[cnt] = X[i];
cnt++;
}
}Note
Set transformation is a special case of MIS, where the condition is based on whether an item has been put in the resulting set yet (determined by Decision PoA).
Multiset transformation
Used to transform a sequence into a multiset. Multiset stores several attributes of the original sequence. E.g. value and count of each value or other.
First example
Get names of students and count how many students have the same name.
Input
Postcondition
Where Y contains unique names and Z contains count of each name.
Implementation
int cnt = 0;
for (int i = 0; i < X.Length; i++){
int j = 0;
// iterate through Y (resulting collection)
// if X[i] is already in Y, then j will be the index of X[i] in Y
while (j < cnt && X[i] != Y[j]){
j++;
}
// if j reached the end of Y, then X[i] is not in Y
if (j == cnt){
// add X[i] to Y
Y[cnt] = X[i];
// set count of X[i] to 1
Z[cnt] = 1;
cnt++;
// otherwise X[i] is in Y
} else {
// then only increment count of X[i]
Z[j]++;
}
}Second example
We're given a list of payouts and we need to calculate the total amount earned for each employee.
Input
Postcondition
Where U is a set of unique employee names. After Set transformation PoA
Where R is resulting collection of structures of employees.
Implementation
int cnt = 0;
for (int i = 0; i < X.Length; i++){
int j = 0;
// iterate through R (resulting collection)
// if X[i].name is already in R, then j will be the index of X[i].name in R
while (j < cnt && X[i].name != R[j].name){
j++;
}
// if j reached the end of R, then X[i].name is not in R
if (j == cnt){
// add X[i].name to R
R[cnt].name = X[i].name;
// set amount of X[i].name to X[i].amount
R[cnt].amount = X[i].amount;
cnt++;
// otherwise X[i].name is in R
} else {
// then only increment amount of X[i].name
R[j].amount += X[i].amount;
}
}