Как создать перестановку haskell - PullRequest
Новая
       6

Как создать перестановку haskell

3 голосов
/ 31 мая 2011

Что я хочу сделать, это создать функцию, которая с определенной длиной создает все возможные комбинации / перестановки True / False

ех. getPerm 2 должен вернуть [True,True,True,False,False,True,False,False]

getTrue 0 = []
getTrue size = (True:(getTrue (size-1)))++(True:(getFalse (size-1)))
getFalse 0 = []
getFalse size =(False:(getTrue (size-1)))++(False:(getFalse (size-1)))
getPerm 0 = []
getPerm size= (getTrue size)++(getFalse size)

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

Ответы [ 3 ]

5 голосов
/ 31 мая 2011 
getPerm n = concat $ replicateM n [True, False]

Хотя это может считаться «странной вещью», это не так уж сложно. [True, False] представляет недетерминированный выбор в монаде списка. replicateM составляет недетерминированный список n повторений этих выборов. Поскольку вы хотели, чтобы все они были в одном списке, мы объединяем, чтобы получить окончательный результат.

3 голосов
/ 31 мая 2011

Вы получите свой результат, используя sequence: 

getPerm = concat . sequence . flip replicate [True,False]

Если вы хотите иметь разные списки для всех перестановок, просто отбросьте concat.

Я просто подумал о более простом определении. iterate :: (a -> a) -> a -> [a] применяет функцию снова и снова и возвращает промежуточные значения: 

getPerm = concat . (iterate permute [[]] !!)

permute xs = map (True:) xs ++ map (False:) xs

Таким образом, permute генерирует следующую перестановку, в то время как getPerm просто выбирает необходимую перестановку.

2 голосов
/ 31 мая 2011

Вот еще одна перспектива.

getPerm n собирается создать 2 ^ n перестановок.Другой способ генерирования этих значений - просто считать от 0 до 2 ^ n-1 и кодировать битовую комбинацию как True и False.

Я изменил тип вашей функции getPermsвернуть список списков, чтобы было легче разбить вещи на части. 

import Data.Bits

getPerms :: Int -> [[Bool]]
getPerms n = map (encode n) [0..2^n-1]

encode :: Int -> Int -> [Bool]
encode bitSize value = map (testBit value) [0..bitSize-1]

*Main> getPerms 2
[[False,False],[True,False],[False,True],[True,True]]
...