/*

  Combinations in Picat.


  http://rosettacode.org/wiki/Combinations
  """
  Given non-negative integers m and n, generate all size m combinations of the 
  integers from 0 to n-1 in sorted order (each combination is sorted and the 
  entire table is sorted).

  For example, 3 comb 5 is
  
  0 1 2
  0 1 3
  0 1 4
  0 2 3
  0 2 4
  0 3 4
  1 2 3
  1 2 4
  1 3 4
  2 3 4
  
  If it is more "natural" in your language to start counting from 1 instead of 0 
  the combinations can be of the integers from 1 to n. 
  """


  Model created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import util.

main => go.

go =>
   N = 3,
   K = 5,
   printf("comb1(3,5): %w\n", comb1(N,K)),
   printf("comb2(3,5): %w\n", comb2(N,K)),
   printf("comb3(3,5): %w\n", comb3(N,K)),

   L = [a,b,c,d,e],
   printf("comb4(%d,%w): %w\n",3,L,comb4(3,L)),

   All = allcomb(1..4),
   printf("allcomb(1..4)  : %w\n", All),

   PowerSet = power_set(1..7),
   printf("power_set(1..7): %w\n", PowerSet.sort()),

   nl.


go2 => 
   printf("\nNumber of different combinations in comb([0..15], 15):\n"),
   foreach(K in 0..15) 
     printf("#comb1(%2d,15): %w\n", K, comb1(K,15).length)
   end,
   nl.


% comb1
comb1(K, N) = Comb =>
   Comb = sort([[J : J in I] : I in power_set(1..N), I.length == K]).


% comb2, using conditions in Head
comb2b(M, _X) = [[]], M = 0  => true.
comb2b(_M, X) =   [], X = [] => true.
comb2b(M, X)  = T =>
   X2 = [X[I] : I in 2..X.length],
   T = [ [X[1]] ++ Xs : Xs in comb2b(M-1, X2) ] ++ comb2b(M, X2).

comb2(M,N) = comb2b(M,1..N).


% comb3, more Prolog like
comb3b(0, _X)     = [[]].
comb3b(_M, [])    = [].
comb3b(M, [X|Xs]) = [ [X] ++ Xs2 : Xs2 in comb3b(M-1, Xs) ] ++ comb3b(M, Xs).

comb3(M,N) = comb3b(M, 1..N).


% comb4: combinations from a list
comb4(M, List) = T =>
   T = [ [List[P[I]] : I in 1..P.length] : P in comb1(M,List.length)].

% cf power_set above. The difference is in the ordering of the sets
allcomb(List) = L => 
   L = [],
   foreach(N in 0..List.length)
     L := L ++ comb4(N, List)
   end.


% sublist(S1, S2):
%    succeeds if S2 is a sublist of S
% (nondet.)
sublist(S1,S2) =>
    append(_, S, S1), append(S2, _, S).