Repository: couchdb-erlang-tests Updated Branches: refs/heads/add-combinatorics [created] a5d933f7b
Add basic combinatorics functions - powerset/1 - permutations/1 - product/1 - binary_combinations/1 - n_combinations/2 Project: http://git-wip-us.apache.org/repos/asf/couchdb-erlang-tests/repo Commit: http://git-wip-us.apache.org/repos/asf/couchdb-erlang-tests/commit/a5d933f7 Tree: http://git-wip-us.apache.org/repos/asf/couchdb-erlang-tests/tree/a5d933f7 Diff: http://git-wip-us.apache.org/repos/asf/couchdb-erlang-tests/diff/a5d933f7 Branch: refs/heads/add-combinatorics Commit: a5d933f7b0dbf2e2aebf2025feecf0fea9f81bf1 Parents: cba29c8 Author: ILYA Khlopotov <[email protected]> Authored: Mon May 16 13:07:39 2016 -0700 Committer: ILYA Khlopotov <[email protected]> Committed: Mon May 16 13:07:39 2016 -0700 ---------------------------------------------------------------------- src/couch_tests_combinatorics.erl | 137 +++++++++++++++++++++++++++++++++ 1 file changed, 137 insertions(+) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/couchdb-erlang-tests/blob/a5d933f7/src/couch_tests_combinatorics.erl ---------------------------------------------------------------------- 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).
