Permutations and combinations of a list in StrategoXT

combinations.str

/**
 * Given a length m and elements xs, generate all combinations of length m
 * from the elements in xs.
 *
 * @type (int, List(a)) -> List(List(a))
 */
combinations:
  (0, _) -> [[]]

combinations:
  (_, []) -> []

combinations:
  (m, [x | xs]) -> <conc> (tail*, recurse*)
  with
    tail* := <combinations; map(prepend(|x))> (<dec> m, xs)
  ; recurse* := <combinations> (m, xs)

prepend(|t) =
  ![t | <id>]

// Usage:
//
// <combinations> (2, [1, 2, 3]) =
//   [ [1, 2]
//   , [1, 3]
//   , [2, 3]
//   ]
//
// <combinations> (3, [1, 2, 3, 4, 5]) =
//   [ [1, 2, 3]
//   , [1, 2, 4]
//   , [1, 2, 5]
//   , [1, 3, 4]
//   , [1, 3, 5]
//   , [1, 4, 5]
//   , [2, 3, 4]
//   , [2, 3, 5]
//   , [2, 4, 5]
//   , [3, 4, 5]
//   ]

permutations.str

// The only permutation of a singleton list is a list containing that element 
permutations:
	[x] -> [[x]]

// do "permutations(|xs) x" for every x in xs
permutations:
	xs -> <map(permutations(|xs)) ; concat> xs

// Remove argument from xs, compute permutations of resulting list
permutations(|xs):
	x -> <filter(not(?x)) ; permutations ; map(prepend(|x))> xs

// Prepend x to the given list
prepend(|x) = ?t ; ![x | t]

// Usage:
//
// <permutations> [1, 2, 3] =
//   [ [1, 2, 3]
//   , [1, 3, 2]
//   , [2, 1, 3]
//   , [2, 3, 1]
//   , [3, 1, 2]
//   , [3, 2, 1]
//   ]