:: Int -> [a] -> [[a]] package:combinatorial

Generate all choices of n elements out of the list x with repetitions. "variation" seems to be used historically, but I like it more than "k-permutation".

>>> Comb.variateRep 2 "abc"
["aa","ab","ac","ba","bb","bc","ca","cb","cc"]

Generate all choices of n elements out of the list x without repetitions.

>>> Comb.variate 2 "abc"
["ab","ac","ba","bc","ca","cb"]

>>> Comb.variate 2 "abcd"
["ab","ac","ad","ba","bc","bd","ca","cb","cd","da","db","dc"]

>>> Comb.variate 3 "abcd"
["abc","abd","acb","acd","adb","adc","bac","bad","bca","bcd","bda","bdc","cab","cad","cba","cbd","cda","cdb","dab","dac","dba","dbc","dca","dcb"]

QC.forAll genVariate $ \xs -> Comb.variate (length xs) xs == Comb.permute xs

\xs -> equating (take 1000) (Comb.variate (length xs) xs) (Comb.permute (xs::String))

Generate all choices of n elements out of the list x respecting the order in x and without repetitions.

>>> Comb.tuples 2 "abc"
["ab","ac","bc"]

>>> Comb.tuples 2 "abcd"
["ab","ac","ad","bc","bd","cd"]

>>> Comb.tuples 3 "abcd"
["abc","abd","acd","bcd"]

Number of possibilities arising in rectification of a predicate in deductive database theory. Stefan Brass, "Logische Programmierung und deduktive Datenbanken", 2007, page 7-60 This is isomorphic to the partition of n-element sets into k non-empty subsets. http://oeis.org/A048993

>>> Comb.rectifications 4 "abc"
["aabc","abac","abbc","abca","abcb","abcc"]

>>> map (length . uncurry Comb.rectifications) $ do x<-[0..10]; y<-[0..x]; return (x,[1..y::Int])
[1,0,1,0,1,1,0,1,3,1,0,1,7,6,1,0,1,15,25,10,1,0,1,31,90,65,15,1,0,1,63,301,350,140,21,1,0,1,127,966,1701,1050,266,28,1,0,1,255,3025,7770,6951,2646,462,36,1,0,1,511,9330,34105,42525,22827,5880,750,45,1]

QC.forAll (QC.choose (0,7)) $ \k xs -> isAscending . Comb.rectifications k . nub . sort $ (xs::String)

enumerate n xs list all permutations of xs where the first n elements do not keep their position (i.e. are no fixpoints). This is a generalization of derangement. Naive but comprehensible implementation.