haskell - 从两个列表进行排列但不使用完整的数字

Question

我想从两个列表中创建所有可能排列的列表。但是，我不想制作全长。例如，第一个列表是["a", "e", "i", "o" "u"]，第二个是[1, 2, 3, 4, 5] 然后其中一个结果就像[["a",1,"i",2],["u",4,"e",s].....]

listsOfPossibilitiesN ::[a] -> [a]  -> [[a]]
listsOfPossibilitiesN  a b = case a of
    _ -> (listMakerN [] a b (length a) (length b) 0)


-- | list = storage, and show at the end of loop, p1h = first list, p2h = second list,
-- | count(x) = count to stop loop when the thing is fully rotated, depthCount = count to stop all loop when the depth reached 10
listMakerN :: [a] -> [a]  -> [a] -> Integer  -> Integer -> Integer -> [[a]]
listMakerN list p1h  p2h count1 count2 depthCount
    | depthCount == 10 = [list]
    | count1 == 0 = []
    | otherwise = case p1h of
                    ((x:xs)) -> (listMaker2N (list ++ [x])  xs p2h (count2 - 1) count2 (depthCount + 1)) ++ listMakerN list (xs ++ [x]) p2h (count1 - 1) count2 depthCount

listMaker2N ::  [a] -> [a]  -> [a] -> Integer -> Integer  -> Integer -> [[a]]
listMaker2N list  p1h  p2h count1 count2 depthCount
    | depthCount == 10 = [list]
    | count2 == 0 = []
    | otherwise = case p2h of
                    ((x:xs)) -> (listMakerN (list ++ [x])  p1h xs count1 (count1 ) (depthCount + 1))  ++ listMaker2N list p1h (xs ++ [x]) count1 (count2 - 1) depthCount

我在上面做了这个功能（我很抱歉图像不好。我终于可以弄清楚如何将代码置于问题中），但是获得结果需要太长时间。我如何做得更好？（提醒您，我是编程初学者）

并且，输出是：

> listsOfPossibilitiesN  [1,2,3,4,5,6,7,8,9,10] [100,200,300,400,500,600,700,800,900,1000]
[[1,100,2,200,3,300,4,400,5,500],[1,100,2,200,3,300,4,400,5,600],[1,100,2,200,3,300,4,400,5,700],[1,100,2,200,3,300,4,400,5,800],[1,100,2,200,3,300,4,400,5,900],[1,100,2,200,3,300,4,400,5,1000],[1,100,
2,200,3,300,4,400,6,500],[1,100,2,200,3,300,4,400,6,600],[1,100,2,200,3,300,4,400,6,700],[1,100,2,200,3,300,4,400,6,800],[1,100,2,200,3,300,4,400,6,900],[1,100,2,200,3,300,4,400,6,1000],[1,100,2,200,3,
300,4,400,7,500],[1,100,2,200,3,300,4,400,7,600],..]

标签： haskellpermutation

Answer 1

猜测一下你当前的代码做了什么，这里有一个算法建议：

1. 不确定地选择元音的排列
2. 为排列分配索引
3. 使用标准tails技巧从该列表中不确定地选择适当数量的元素

在代码中：

import Data.List

choose :: Int -> [a] -> [[a]]
choose 0 xs = [[]]
choose n xs = do
    x:xs' <- tails xs
    (x:) <$> choose (n-1) xs'

assignments :: Int -> [a] -> [[(Int, a)]]
assignments n xs = do
    xs' <- permutations xs
    choose n (zip [1..] xs')

在 ghci 中：

> mapM_ print (assignments 2 "abc")
[(1,'a'),(2,'b')]
[(1,'a'),(3,'c')]
[(2,'b'),(3,'c')]
[(1,'b'),(2,'a')]
[(1,'b'),(3,'c')]
[(2,'a'),(3,'c')]
[(1,'c'),(2,'b')]
[(1,'c'),(3,'a')]
[(2,'b'),(3,'a')]
[(1,'b'),(2,'c')]
[(1,'b'),(3,'a')]
[(2,'c'),(3,'a')]
[(1,'c'),(2,'a')]
[(1,'c'),(3,'b')]
[(2,'a'),(3,'b')]
[(1,'a'),(2,'c')]
[(1,'a'),(3,'b')]
[(2,'c'),(3,'b')]