Поиск комбинаций

Question

Я хочу написать функцию, которая вычисляет все комбинации чисел от 1 до 7 в 7 кортежах, но каждое число может встречаться только один раз в каждом кортеже.

До сих пор я нашел этот подход, но онтакже возвращает комбинации с несколькими вхождениями одного и того же номера в каждом кортеже.Я не совсем уверен, как удалить кортежи с несколькими вхождениями одного и того же номера.

  a = [(a,b,c,d,e,f,g) | a <- [1..7], b <- [1..7], c <- [1..7], 
        d <- [1..7], e <- [1..7], f <- [1..7], g <- [1..7]]

Пример для результата цели (все допустимые комбинации должны быть здесь):

  [(1,2,3,4,5,6,7),(2,1,3,4,5,6,7),(2,3,1,4,5,6,7),...]

Answer 1

Вы можете использовать разницу в списке (\\) от Data.List.

perms = [ (a,b,c,d,e,f,g) | a <- [1..7]
                          , b <- [1..7] \\ [a]
                          , c <- [1..7] \\ [a,b]
                          , d <- [1..7] \\ [a,b,c]
                          , e <- [1..7] \\ [a,b,c,d]
                          , f <- [1..7] \\ [a,b,c,d,e]
                          , g <- [1..7] \\ [a,b,c,d,e,f] ]

Таким образом, b будет отличаться от a, c будет отличаться от a и b и т. Д.

Answer 2

Мы можем оптимизировать код из ответа на kuoytfouy , как

perms = [(a,b,c,d,e,f,g) | a <- [1..7], let dom6 = [1..7] \\ [a]
                         , b <- dom6,   let dom5 = dom6 \\ [b]
                         , c <- dom5,   let dom4 = dom5 \\ [c]
                         , d <- dom4,   let dom3 = dom4 \\ [d] 
                         , e <- dom3,   let dom2 = dom3 \\ [e] 
                         , f <- dom2,   let dom1 = dom2 \\ [f] 
                         , g <- dom1,   let dom0 = dom1 \\ [g]  ]

и дополнительно улучшить его, исключив избыточные вычисления,

perms = [(a,b,c,d,e,f,g) | a <- [1..7], let dom6 = delete a [1..7]
                         , b <- dom6,   let dom5 = delete b dom6
                         , c <- dom5,   let dom4 = delete c dom5
                         , d <- dom4,   let dom3 = delete d dom4 
                         , e <- dom3,   let dom2 = delete e dom3 
                         , f <- dom2,   let [g]  = delete f dom2 ]

Сочетание выбора элемента с его удалением из текущего домена дает нам одну функцию, которая выполняет две работы одновременно, обычно называемую picks.Он использовался в SO-ответах в прошлом и может быть найден там.

См. Также:

• picks от одного свиновода
• choose в монаде «Уникальный выбор»
• a Общий ответ на Lisp мой с эффективным кодом, который на самом делесокращает список доменов путем хирургической мутации структуры списка, отбирая элементы один за другим, пока мы идем по рекурсивно построенным вложенным циклам;и исцеление его на обратном пути.
  То есть, код на Haskell, основанный на choose - (или, что эквивалентно, picks -), серьезно подозревается в том, что он крайне неэффективен (inits является квадратичным при полном форсировании,для начала).
  Пересчет сокращенных доменов каждый раз, как в этом ответе, мы получаем только семь (шесть, независимо от того) списков доменов в каждый момент времени, каждый из которых может быть полностью собран, когда выполняется - , но , каждый delete вызов ищет свой аргумент с самого начала заново (неэффективность picks была изобретена, чтобы исправить ...), снова подтверждая, что общий расчет был квадратичным, неэффективным.Пища для размышлений!

Answer 3

Как насчет чего-то вроде:

import Data.List
list = [(a,b,c,d,e,f,g) | a <- [1..7], b <- [1..7], c <- [1..7],
        d <- [1..7], e <- [1..7], f <- [1..7], g <- [1..7], [1,2,3,4,5,6,7]\\[a,b,c,d,e,f,g]==[]]

Answer 4

Здесь мы можем создать «вспомогательную функцию», которая для данного списка xs генерирует список кортежей, где первый элемент - это выбранный нами элемент, а второй - список оставшихся элементов, например:

import Data.List(inits, tails)

pick :: [a] -> [(a, [a])]
pick ls = [(b, as ++ bs) | (as, (b:bs)) <- zip (inits ls) (tails ls)]

Например:

Prelude Data.List> pick [1..5]
[(1,[2,3,4,5]),(2,[1,3,4,5]),(3,[1,2,4,5]),(4,[1,2,3,5]),(5,[1,2,3,4])]

каждый элемент, таким образом, выбирает элемент из списка и возвращает список, в котором этот выбранный элемент удален.Мы можем использовать это, чтобы затем передать этот список следующему генератору.

Затем мы можем использовать это, например, в do блоке, таком как:

perms :: (Num a, Enum a) => [(a, a, a, a, a, a, a)]
perms = do
    (a, as) <- pick [1..7]
    (b, bs) <- pick as
    (c, cs) <- pick bs
    (d, ds) <- pick cs
    (e, es) <- pick ds
    (f, [g]) <- pick es
    return (a, b, c, d, e, f, g)

, что приводит к:

Prelude Data.List> perms
[(1,2,3,4,5,6,7),(1,2,3,4,5,7,6),(1,2,3,4,6,5,7),(1,2,3,4,6,7,5),(1,2,3,4,7,5,6),(1,2,3,4,7,6,5),(1,2,3,5,4,6,7),(1,2,3,5,4,7,6), ...