Combinatorics.hs

data CombinatorialProblem = ChooseOneOfNOptions Int
                          | OrderNThings Int
                          | And CombinatorialProblem CombinatorialProblem
                          | Or CombinatorialProblem CombinatorialProblem
                          | RepeatedChoice CombinatorialProblem Int

-- how many ways can eight people sit next to each other?
eightPeopleSitting = OrderNThings 8

-- how many ways can four couples sit next to each other, if each couple 
-- has to sit together?
fourCouplesSittingNextToEachOther = orderTheCouples `And` orderEachCouple
  where
    orderTheCouples = OrderNThings 4
    orderEachCouple = RepeatedChoice (OrderNThings 2) 4

-- how many ways can you sit four men and four women, if men and women 
-- can't sit next to each other?
noHomosexualTouching =
  orderTheWomen `And` orderTheMen `And` chooseWhetherTheLeftmostPersonIsMale
    where
      orderTheWomen = OrderNThings 4
      orderTheMen = OrderNThings 4
      chooseWhetherTheLeftmostPersonIsMale = ChooseOneOfNOptions 2

-- alternative definition
noHomosexualTouching2 = 
  (orderTheMen `And` orderTheWomen) -- sit the men first
  `Or` -- or
  (orderTheWomen `And` orderTheMen) -- sit the women first
    where
      orderTheWomen = OrderNThings 4
      orderTheMen = OrderNThings 4

numberOfSolutions :: CombinatorialProblem -> Int
numberOfSolutions problem = case (problem) of 
  ChooseOneOfNOptions n -> n
  OrderNThings n -> factorial n
    where
      factorial 0 = 1
      factorial n = n * factorial (n - 1)
  And problem1 problem2 -> numberOfSolutions problem1 * numberOfSolutions problem2
  Or problem1 problem2 -> numberOfSolutions problem1 + numberOfSolutions problem2
  RepeatedChoice problem n -> numberOfSolutions problem ^ n



main = do
  putStrLn "how many ways can eight people sit?"
  print (numberOfSolutions eightPeopleSitting)

  putStrLn "how many ways can four couples sit?"
  print (numberOfSolutions fourCouplesSittingNextToEachOther)

  putStrLn "how many ways can eight people sit, if no gay touching is allowed?"
  print (numberOfSolutions noHomosexualTouching)