src/couch_tests/src/couch_tests_combinatorics.erl

% 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).