David Tran’s blog

Finished:
Yet Another Haskell Tutorial
Haskell for C Programmers

Start reading:
Haskell Wikibook

To find the combination of (n,r), we can use this formula:
C(n,r) = C(n-1,r-1) + C(n-1,r)

This means, combination of (n,r) equals to combine of
take the first ( C(n-1,r-1) ) and without take the first ( C(n-1,r) ).

For example, for C(2,1), it can be:
C(2,1)
= add#1 in C(1,0) + C(1,1)
= add#1 in C(1,0) + add#2 in C(0,0) + C(0,1)
where
add#1 = add first element of list ( C(2,1) )
add#2 = add first element of list ( C(1,1) )

So, the base case could define as:
C(_,0) = [[]]
C(0,_) = []

Here is the Haskell definition for combination:

combination :: [a] -> Int -> [[a]]
combination _   0    = [[]]
combination []  _    = []
combination (x:xs) n = map (x:) (combination xs (n-1)) ++ combination xs n

The power set of S is the set of all subsets of S.
There will be total 2ⁿ sets where n is the number element of S.
For example, the set S={a,b,c}, we could use all 3 bits value to find the power set.

By using this hint (the color red represents power set of {b,c}), the power set function can be defined as:

powerset :: [a] -> [[a]]
powerset []     = [[]]
powerset (x:xs) = powerset xs ++ map (x:) (powerset xs)
-- powerset (x:xs) = powerset xs ++ [x:xs' | xs' <- powerset xs]

My solution for the Ruby Quiz (#160) Chess960.
This is ported form my Haskell version solution.
Also posted on Ruby-talk mailing list here.

def permutations(pieces)
  return [pieces] if pieces.size <= 1
  result = []
  pieces.uniq.each do |p|
    _pieces = pieces.dup
    _pieces.delete_at(pieces.index(p))
    permutations(_pieces).each do |perm|
      result << (perm << p)
    end
  end
  result
end

results = permutations("RNBKQBNR".split(//)).select do |position|
  r1 = position.index('R')
  r2 = position.rindex('R')
  b1 = position.index('B')
  b2 = position.rindex('B')
  k  = position.index('K')
  r1 < k && k < r2 && ((b1+b2) % 2 != 0)
end

puts "Total positions = #{results.size}"
puts results[rand(results.size)].join(' ')

Compute permutation using list comprehension and recursion can be like:

permutations :: Eq a => [a] -> [[a]]
permutations [] = [[]]
permutations xs = [x:ps | x <- xs, ps <- permutations (delete x xs)]

There are many other variants, like:

permutations xs = [x:ps | x <- xs, ps <- permutations (xs\\[x])] 

and also on here and LicensedPreludeExts

permutations :: [a] -> [[a]]
permutations [] = [[]]
permutations xs = [y:zs | (y,ys) <- selections xs, zs <- permutations ys ]

selections :: [a] -> [(a,[a])]
selections [] = []
selections (x:xs) = (x,xs) : [(y,x:ys) | (y,ys) <- selections xs]

even faster version:

permutations :: [a] -> [[a]]
permutations []     = [[]]
permutations (x:xs) = [zs | ys <- permutations xs, zs <- everywhere x ys]

everywhere :: a -> [a] -> [[a]]
everywhere x []     = [[x]]
everywhere x (y:ys) = (x:y:ys) : [y:zs | zs <- everywhere x ys]

and so on.

Sometime the list to permute may contain repeat elements (likes two quizzes below), one way to get the unique permutations is like:

result = nub (permutations list_has_repeat_elements)

This is sometime really inefficient, especially there are many repeats elements like in Chess960 quiz; simply modify the permutations definition can improve a lot in this case:

permutations :: Eq a => [a] -> [[a]]
permutations [] = [[]]
permutations xs = [ x:ps | x <- nub xs, ps <- permutations (delete x xs) ]

Now, I can apply this permutations to quick solve below two quizzes.

(1) Check960 (see detail information on: Ruby Quiz #106 Chess960 or wikipedia)

module Main where
import Data.List

pieces = "RNBKQBNR"

permutations [] = [[]]
permutations xs = [x:ps | x <- nub xs, ps <- permutations (delete x xs)]

restriction position =
  r1 < k && k < r2 &&
  sum (elemIndices 'B' position) `mod` 2 /= 0
  where
    r1:r2:_  = elemIndices 'R' position
    Just k   = elemIndex   'K' position

result = filter restriction (permutation pieces)

main = do
--  print result
    print (length result)

(2) Quiz: give you 1,2,2,3,4,5 six digits(attention: two 2s), print out all of different possible numbers by using the digits under two conditions: 3 and 5 can’t be consecutive, 4 can’t be at the thousand position. This is really similar to the Check960 quiz.

module Main where
import Data.List

permutations [] = [[]]
permutations xs = [x:ps | x <- nub xs, ps <- permutations (delete x xs)]

digits = [1,2,2,3,4,5]

check xs =            -- precondition: xs is one of "digits"’s permutations  
  xs !! 2 /= 4  &&    -- 4 can’t be at the thousand position
  abs (p3 - p5) /= 1  -- 3 and 5 can’t be consecutive
  where
    Just p3 = elemIndex 3 xs
    Just p5 = elemIndex 5 xs

result = filter check (permutations digits)

main = do
--  print result
    print (length result)

I have more fun with Haskell than Ruby.