Merge remote branch 'apache:add-combinatorics'
This closes #2
Signed-off-by: ILYA Khlopotov <iilyak@ca.ibm.com>
diff --git a/src/couch_tests_combinatorics.erl b/src/couch_tests_combinatorics.erl
new file mode 100644
index 0000000..3433362
--- /dev/null
+++ b/src/couch_tests_combinatorics.erl
@@ -0,0 +1,137 @@
+% Licensed under the Apache License, Version 2.0 (the "License"); you may not
+% use this file except in compliance with the License. You may obtain a copy of
+% the License at
+%
+% http://www.apache.org/licenses/LICENSE-2.0
+%
+% Unless required by applicable law or agreed to in writing, software
+% distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+% WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+% License for the specific language governing permissions and limitations under
+% the License.
+
+-module(couch_tests_combinatorics).
+
+-export([
+ powerset/1,
+ permutations/1,
+ product/1,
+ binary_combinations/1,
+ n_combinations/2
+]).
+
+%% @doc powerset(Items)
+%% Generate powerset for a given list of Items
+%% By Hynek - Pichi - Vychodil
+%% For example:
+%% 1> powerset([foo, bar, baz]).
+%% [
+%% [foo],
+%% [foo,baz],
+%% [foo,bar,baz],
+%% [foo,bar],
+%% [bar],
+%% [bar,baz],
+%% [baz],
+%% []
+%% ]
+-spec powerset(Elements :: list()) -> [list()].
+
+powerset([]) ->
+ [[]];
+powerset([H | T]) ->
+ PT = powerset(T),
+ powerset(H, PT, PT).
+
+powerset(_, [], Acc) ->
+ Acc;
+powerset(X, [H | T], Acc) ->
+ powerset(X, T, [[X | H] | Acc]).
+
+%% @doc permutations(Items)
+%% Return all premutations of given list of Items.
+%% from http://erlang.org/doc/programming_examples/list_comprehensions.html
+%% For example:
+%% 1> permutations([foo, bar, baz]).
+%% [
+%% [foo, bar, baz],
+%% [foo, baz, bar],
+%% [bar, foo, baz],
+%% [bar, baz, foo],
+%% [baz, foo, bar],
+%% [baz, bar, foo]
+%% ]
+-spec permutations(Elements :: list()) -> [list()].
+
+permutations([]) ->
+ [[]];
+permutations(L) ->
+ [[H | T] || H <- L, T <- permutations(L -- [H])].
+
+%% @doc product({Items1, Items2, ..., ItemsN})
+%% Return cartesian product of multiple sets represented as list of lists
+%% From: http://stackoverflow.com/a/23886680
+%% For example:
+%% 1> product([[foo, bar], [1,2,3]]).
+%% [
+%% [foo, 1],
+%% [foo, 2],
+%% [foo, 3],
+%% [bar, 1],
+%% [bar, 2],
+%% [bar, 3]
+%% ]
+-spec product(Elements :: list()) -> [list()].
+
+product([H]) ->
+ [[A] || A <- H];
+product([H | T]) ->
+ [[A | B] || A <- H, B <- product(T)].
+
+%% @doc binary_combinations(NBits).
+%% Generate all combinations of true and false for specified number of bits.
+%% For example:
+%% 1> binary_combinations(3).
+%% [
+%% [ false , false , false ],
+%% [ false , false , true ],
+%% [ false , true , false ],
+%% [ false , true , true ],
+%% [ true , false , false ],
+%% [ true , false , true ],
+%% [ true , true , false ],
+%% [ true , true , true ]
+%% ]
+%% 2> length(binary_combinations(3))
+%% 8
+-spec binary_combinations(NBits :: pos_integer()) -> [list(boolean())].
+
+binary_combinations(NBits) ->
+ product(lists:duplicate(NBits, [true, false])).
+
+
+%% @doc combinations(N, Items).
+%% Generate all combinations by choosing N values from a given list of Items
+%% in sorted order. Each combination is sorted and the entire table is sorted.
+%% For example:
+%% 1> couch_tests_combinatorics:n_combinations(2, [mon, tue, wed, thu, fri]).
+%% [
+%% [mon, tue],
+%% [mon, wed],
+%% [mon, thu],
+%% [mon, fri],
+%% [tue, wed],
+%% [tue, thu],
+%% [tue, fri],
+%% [wed, thu],
+%% [wed, fri],
+%% [thu, fri]
+%% ]
+-spec n_combinations(Size :: pos_integer(), Elements :: list()) -> [list()].
+
+n_combinations(0, _) ->
+ [[]];
+n_combinations(_, []) ->
+ [];
+n_combinations(N, [H | T]) ->
+ [[H | L] || L <- n_combinations(N - 1, T)] ++ n_combinations(N, T).
