Haskell: как лечить большие комбинаторные списки?

Question

совсем недавно я попытался написать программу, которая в основном имитирует простую систему из онлайн-игры. Идея заключается в том, чтобы позволить программе рассчитывать наиболее эффективный набор элементов для максимально возможной эффективности эффективности из набора. Чтобы уточнить это немного больше: у вас есть 8 слотов и 74 разных предмета, вы не можете использовать какой-либо элемент дважды, и не имеет значения, какой элемент находится в этом слоте. Я даже не пытаюсь рассчитать один набор характеристик, я застрял раньше!

Таким образом, проблема заключается в количестве возможностей (74^8) перед фильтрацией и (74 выберите 8) после фильтрации. Моя программа уже начинает отставать, когда я просто пробую голову (перму '2). Поскольку я знаю, что Haskell должен работать с бесконечными списками, как он работает со списком из 899 триллионов записей? Я знаю, очевидно, что для ПК требуется много возможностей, но именно поэтому я здесь, чтобы задать вопрос:

Как обработать большой список в Haskell, чтобы я мог работать с ним?

функция упрощенных выглядит следующим образом:

quicksort :: (Ord a) => [a] -> [a] 
quicksort [] = [] 
quicksort [a] = [a] 
quicksort (x:xs) = (quicksort [y | y <- xs, y <= x]) ++ [x] ++ (quicksort [z | z <- xs , z > x]) 

eliminatedouble [] = [] 
eliminatedouble (x:xs) = if x `elem` xs then eliminatedouble xs else x:(eliminatedouble xs) 

permu' n | n>8 = error "8 is max" 
     | otherwise = eliminatedouble (filter allSatisfied (generate n)) 
    where 
     generate 0 = [[]] 
     generate x = [quicksort (a:xs) | a <- [1..74], xs <- generate (x-1)] 
     allSatisfied [] = True 
     allSatisfied (x:xs) = (checkConstraint x xs) && (allSatisfied xs) 
     checkConstraint x xs = not (doubled x xs) 
     doubled x xs = x `elem` xs 

было бы интересно узнать, как сделать все это гораздо дешевле.

Заранее благодарим.

Answer 1

Вы делаете это намного сложнее, чем должно быть.

choose 0 xs = [[]] 
choose n [] = [] 
choose n (x:xs) = map (x:) (choose (n-1) xs) ++ choose n xs 

В моем интерпретатором, choose 5 [1..74] занимает около 22 секунд, чтобы вычислить все записи и choose 6 [1..74] занимает 273 секунд. Кроме того, choose 8 [1..74] начинает сразу же перебирать комбинации; По моим оценкам, для их создания потребуется около 6 часов. Нотабене что это в интерпретаторе, при этом не происходит никакой оптимизации или другой фиктивности; возможно, это может пойти намного быстрее, если вы дадите GHC шанс выяснить, как это сделать.

Предполагая, что вы намереваетесь выполнять некоторые нетривиальные вычисления для каждого элемента choose 8 [1..74], я предлагаю вам либо запланировать довольно большой объем времени, приблизительный ответ или выяснение того, как сделать некоторую обрезку, чтобы вырезать большие, неинтересные полосы пространства поиска.