## Saturday, January 28, 2017

### Power Set Algorithm - Iterative

The power set of a set S is the set of all subsets of S including the empty set and S itself. For example, the power set of `{1, 2, 3}` is `{{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}`.

Previously, I wrote about how you can generate the power set using a recursive algorithm. This time I'll show you how to use iteration.

Recall, that when we are generating a set for the power set, each element can either be in the set or out of the set. In other words, each set can be represented in binary form, where 1 means that the element is in the set and 0 means that it is not. For example, given a set `{a, b, c}`, the binary string `101` would represent `{a, c}`.

Generating the power set just comes down to generating all numbers from 0 to 2^n (since there are 2^n possible subsets) and converting the binary representation of the number into the set!

Here is the algorithm:

```public static <E> List<List<E>> powerSet(final List<E> list) {
final List<List<E>> result = new ArrayList<>();
final int numSubSets = 1 << list.size(); // 2^n
for (int i = 0; i < numSubSets; i++) {
final List<E> subSet = new ArrayList<>();
int index = 0;
for (int j = i; j > 0; j >>= 1) { // keep shifting right
if ((j & 1) == 1) { // check last bit
}
index++;
}
}
return result;
}
```

## Sunday, January 22, 2017

### Java 8: Top N elements from a stream

This post shows how you can sort a stream in reverse order and then select the top N elements.

This is quite common in financial systems.

For example, let's say that you have a list of currency exchange rate movements and you want to see the top 5 largest movements. You can do this using Java 8 Streams as shown below:

```import static java.util.Comparator.*;
import static java.util.stream.Collectors.*;

// list of currency exchange rate percentage moves
final List<Currency> currencies = Arrays.asList(
new Currency("EUR/USD", 0.37),
new Currency("USD/JPY", -0.21),
new Currency("GBP/USD", 0.27),
new Currency("AUD/USD", -0.08),
new Currency("USD/CHF", -0.46),
new Currency("EUR/JPY", 0.16),
new Currency("EUR/GBP", 0.13),
new Currency("USD/HKD", 0.0),
new Currency("EUR/CHF", 0.05),
new Currency("USD/KRW", -0.71)
);

currencies.stream()
.sorted(comparing(Currency::getMove, comparing(Math::abs)).reversed())
.limit(5)
.collect(toList());
```

The result is:

```Currency [ccy=USD/KRW, move=-0.71]
Currency [ccy=USD/CHF, move=-0.46]
Currency [ccy=EUR/USD, move=0.37]
Currency [ccy=GBP/USD, move=0.27]
Currency [ccy=USD/JPY, move=-0.21]
```

The two argument `Comparator.comparing` method easily allows us to compare currency moves on absolute value.

## Sunday, January 01, 2017

Happy 2017, everyone!

I'd like to wish everyone a great start to an even greater new year!

In keeping with tradition, here's one last look back at fahd.blog in 2016.

During 2016, I posted 20 new entries on fahd.blog. I am also thrilled that I have more readers from all over the world! Thanks for reading and especially for giving feedback.

Top 5 posts of 2016:

I'm going to be writing a lot more this year, so stay tuned for more great techie tips, tricks and hacks! :)

Related posts: