Calculating Combinations the Erlang Way

If you recall, I wrote some Ruby code to calculate combinations of values in lists. I needed to create a list of all combinations of values, where each combination had between 0 and N number of values, where N is equal to length of the source list. (I'm not sure I'm explaining that correctly, but refer to my previous post for examples).

Here's my first shot at how to do this in erlang. It look longer to find math:pow and how to convert a float to an integer in erlang than to write the actual code.



-module(s).
-export([combos/1]).

combos(L) -> combos(L, bit_masks(length(L))).

combos(L, [BH|BT]) ->
  [mask_list(L, BH)|combos(L, BT)];
combos(_, []) -> [].

mask_list([H|T], [BH|BT]) ->
  case (BH) of
    1 -> [H|mask_list(T, BT)] ;
    0 -> mask_list(T, BT)
  end;
mask_list([], []) -> [].

bit_masks(NumColumns) ->
  bit_masks(0, round(math:pow(2, NumColumns))-1, NumColumns).

bit_masks(Max, Max, NumColumns) ->
  [padl(NumColumns, bl(Max))];

bit_masks(X, Max, NumColumns) ->
  [padl(NumColumns, bl(X)) | bit_masks(X+1, Max, NumColumns)].

padl(N, L) when N =:= length(L) -> L ;
padl(N, L) when N > length(L) -> padl(N, [0|L]).

bl(N) -> bl(N, []).

bl(0, Accum) -> Accum;
bl(N, Accum) -> bl(N bsr 1, [(N band 1) | Accum]).



Brief explanation:

The bl function creates a "bit list", given a number and an accumulator. So, bl(5,[]) will return [1,0,1].

The padl function pads the list, which is useful when you want to ensure that all combinations ultimately have the same length. So, padl(4, [0]) would return [0,0,0,0].

And then bit_masks creates a list of bit masks which we'll use to create the combinations. For example, bit_masks(4) returns:



[[1,1,1,1],
 [1,1,1,0],
 [1,1,0,1],
 [1,1,0,0],
 [1,0,1,1],
 [1,0,1,0],
 [1,0,0,1],
 [1,0,0,0],
 [0,1,1,1],
 [0,1,1,0],
 [0,1,0,1],
 [0,1,0,0],
 [0,0,1,1],
 [0,0,1,0],
 [0,0,0,1],
 [0,0,0,0]]



And finally, to create the actual combinations, you will use combos. Example: combos([a,b,c,d]). This generates a result of:



[[],
 [d],
 [c],
 [c,d],
 [b],
 [b,d],
 [b,c],
 [b,c,d],
 [a],
 [a,d],
 [a,c],
 [a,c,d],
 [a,b],
 [a,b,d],
 [a,b,c],
 [a,b,c,d]]



So, is there a more erlang way to do this?

Popular posts from this blog

The 29 Healthiest Foods on the Planet

The 29 Healthiest Foods on the Planet > The following is a "healthy food hot list" consisting of the 29 food that will give you the biggest nutritional bang for you caloric buck, as well as decrease your risk for deadly illnesses like cancer, diabetes and heart disease.
Read more

Lists and arrays in Dart

(This is Part 3 in a series about Dart. Check out Part 2, Function in Dart .) Warning : We expect the Dart libraries to undergo potentially sweeping changes before Dart goes to alpha. This document is relevant as of 2011-12-22. Intro Dart is a "batteries included" effort to help app developers build modern web apps. An important "battery" is the bundled core Dart libraries, providing common and rich functionality. Dart is building a solution for large, complex web apps, and providing well tested, integrated, and common libraries is key to helping a web app developer be more productive out of the box. The Collection libraries are a crucial set of APIs that Dart developers get for free. Much more than simple arrays and maps, the Collection library includes standard ways to filter, iterate, inspect, compose, and sort your data. This post specifically looks at List<E> , Dart's ordered, indexable collection of objects. Aside: The Dart project is lucky...
Read more

Converting Array to List in Scala

Now, this has to have a built-in somewhere in Scala , because it just seems too common. So, how to convert an Array to a List in Scala? Why do I need this? I needed to drop to Java for some functionality, which in this case returns an Array. I wanted to get that Array into a List to practice my functional programming skillz. **Update**: I figured out how to convert Arrays to Lists the Scala way. Turns out it's a piece of cake. val myList = List.fromArray(Array("one", "two", "three")) or val myList = Array("one","two","three").elements.toList The call to elements returns an Iterator , and from there you can convert to a List via toList . Nice. Because my first version wasn't actually tail recursive, what follows is a true tail recursive solution, if I were to implement this by hand. The above, built in mechanism is much better, though. object ArrayUtil { def toList[a](array: Array[a]): List[a] = { d...
Read more