如何创建这两个列表的所有可能组合？

Question

我想从这两个列表中提取所有组合的列表，其中每个组合也是一个列表。

例如

给定两个列表：[1,2,3] 和 [True, False]

组合：

[(1, False), (2, False), (3, False)]
[(1, False), (2, False), (3, True )]
[(1, False), (2, True ), (3, False)]
[(1, True ), (2, False), (3, False)]
[(1, False), (2, True ), (3, True )]
[(1, True ), (2, False), (3, True )]
[(1, True ), (2, True ), (3, False)]
[(1, True ), (2, True ), (3, True )]

应该有 2^n 种组合，其中 n 是数字的个数。

编辑：

已尝试执行以下操作：

[(n, b) | n <- [1,2,3], b <- [True, False]]
(,) <$> [1,2,3] <*> [True, False]

Answer 1

你想要的输出可以通过定义

产生

foo :: [a] -> [b] -> [[(a, b)]]
foo nums bools =
    map (zip nums) . sequence $ replicate (length nums) bools
  =
    let n = length nums 
    in 
        [ zip nums bs | bs <- sequence $ replicate n bools]

并打电话

foo [1,2,3] [False, True]

那个调用等同于

    let nums = [1,2,3]
        bools = [False, True]
        n = 3
    in 
        [ zip nums bs | bs <- sequence $ replicate n bools]
      =
        [ zip [1,2,3] bs | bs <- sequence $ replicate 3 [False, True]]
      =
        [ zip [1,2,3] (b:bs) | b  <- [False, True]
                             , bs <- sequence $ replicate 2 [False, True]]
      =
        [ zip [1,2,3] (b:c:bs) | b  <- [False, True]
                               , c  <- [False, True]
                               , bs <- sequence $ replicate 1 [False, True]]
      =
        [ zip [1,2,3] (b:c:d:bs) | b  <- [False, True]
                                 , c  <- [False, True]
                                 , d  <- [False, True]
                                 , bs <- sequence $ replicate 0 [False, True] ]
      =
        [ zip [1,2,3] (b:c:d:bs) | b  <- [False, True]
                                 , c  <- [False, True]
                                 , d  <- [False, True]
                                 , bs <- sequence [] ]
      =
        [ zip [1,2,3] (b:c:d:bs) | b  <- [False, True]
                                 , c  <- [False, True]
                                 , d  <- [False, True]
                                 , bs <- [[]] ]
      =
        [ zip [1,2,3] (b:c:d:[]) | b  <- [False, True]
                                 , c  <- [False, True]
                                 , d  <- [False, True] ]

即

        [ zip [1,2,3] [b,c,d]    | b  <- [False, True]
                                 , c  <- [False, True]
                                 , d  <- [False, True] ]

如果对最后一个表达式求值，我们也会得到相同的结果。

用两个可用值的每个可能组合填充三个空间就像拥有从 3 个空间到 2 个值的所有可能函数，无论这些空间和值是什么。

数学家把这个函数写成2³，事实上，我们得到了2^3 = 8个输出。

edit: sequence ... replicate 组合实际上只是重新实现了另一个内置的 replicateM:

foo ns bs = map (zip ns) (replicateM (length ns) bs)

因为 replicateM n a 就像 sequence (replicate n a)，但实际上没有构建中间列表。

对于pointfree爱好者来说，我们可以

foo ns    =  map (zip ns) . replicateM (length ns)
          =  (.) ((map . zip) ns) ((replicateM . length) ns)
          =  ((.) . map . zip <*> replicateM . length)   ns

即

foo       =  (.) . map . zip <*> replicateM . length

Answer 2

这不是最直接或最有效的答案。

但是使用 How to generate a list of all possible strings from shortest to longest 中的技术，我们可以生成所有可能的布尔序列的列表。我们采用与第二个列表长度相同的那些，然后将它们与该列表一起压缩。

allBoolPermutations :: Int -> [[Bool]]
allBoolPermutations n = takeWhile (\l -> length l == n) 
                      $ dropWhile (\l -> length l < n) 
                      $ allBools
  where
    allBools = [ c : s | s <- []:allBools, c <- [True, False]] 


zipWithBoolPermutations :: [a] -> [[(a, Bool)]]
zipWithBoolPermutations someList = map (zip someList) 
                                       (allBoolPermutations (length someList))

那么zipWithBoolPermutations [1,2,3]应该给你你想要的。

Answer 3

我们可以避免使用 length，这可能是不安全的，因为列表可以无限长。通过使用递归或 foldr 模式，我们可以避免：

{-# LANGUAGE TupleSections #-}

allComb :: [b] -> [a] -> [[(a,b)]]
allComb vs = go
    where go [] = [[]]
          go (x:xs) = (:) <$> map (x,) vs <*> go xs

或在单行中使用折叠模式：

allComb :: [b] -> [a] -> [[(a,b)]]
allComb vs = foldr (\x -> ((:) <$> map (x,) vs <*>)) [[]]

例如：

Prelude> allComb [False, True] [1,2,3]
[[(1,False),(2,False),(3,False)],[(1,False),(2,False),(3,True)],[(1,False),(2,True),(3,False)],[(1,False),(2,True),(3,True)],[(1,True),(2,False),(3,False)],[(1,True),(2,False),(3,True)],[(1,True),(2,True),(3,False)],[(1,True),(2,True),(3,True)]]

上述方法不适用于无限列表，但我们可以在给定第一个列表至少包含一个元素的情况下稍微更改代码，以生成结果的第一个元素：一个压缩所有元素的列表在带有该项目的第二个列表中。我把它留作练习。

Answer 4

又好又短：

traverse ((<$> [True, False]) . (,)) [1,2,3]

或更少点自由，但也许更容易理解：

{-# LANGUAGE TupleSections #-}

traverse (\x -> (x,) <$> [True, False]) [1,2,3]

内部函数（(<$> [True, False]) . (,)或\x -> (x,) <$> [True, False]）获取每个元素，例如1，并将其变成[(1,True),(1,False)]。如果你认为 traverse f 是 sequence . fmap f，那么 fmap f 部分意味着对列表中的每个事物执行该功能（产生 [[(1,True),(1,False)],[(2,True),(2,False)],[(3,True),(3,False)]]），而 sequence 部分意味着将它们与 List 应用程序（模拟非确定性）结合起来以创建所有可能的组合（产生 [[(1,True),(2,True),(3,True)],[(1,True),(2,True),(3,False)],[(1,True),(2,False),(3,True)],[(1,True),(2,False),(3,False)],[(1,False),(2,True),(3,True)],[(1,False),(2,True),(3,False)],[(1,False),(2,False),(3,True)],[(1,False),(2,False),(3,False)]]）。

如何创建这两个列表的所有可能组合？

How to create all possible combinations of these two lists?

combinations

haskell

list

combinatorics