Блог

Я хочу создать список списков, который содержит все возможные комбинации значений внутри меньших списков размером n

Например, допустим, у меня есть список [1,2,3], и у меня n равно 2. Результат будет: [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]

Это звучит довольно просто для фиксированного N, но как это будет работать для неопределенного значения N?

До сих пор я пытался:

 [[x,y] | x <- [1,2,3], y <- [1,2,3]] 
 

и это работает для фиксированного n, равного 2. Но я не знаю, как заставить это зависеть от N.

Для этого есть библиотечная функция: она replicateM находится в Control.Monad пакете:

 > import Control.Monad
> replicateM 2 [1,2,3]
[[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]
> replicateM 5 [1,2,3]
[[1,1,1,1,1],[1,1,1,1,2],[1,1,1,1,3],[1,1,1,2,1],....]
 

Однако, если вы заинтересованы в том, чтобы определить это самостоятельно, вы правы в том, что это невозможно сделать для undetermined N с использованием единого понимания списка. Вместо этого вам нужно написать рекурсивную версию. Идея в том, что если у нас уже был ответ на некоторые n , например n=2 :

 [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]
 

затем мы могли бы сгенерировать ответ для next n ( n=3 ), добавив ко всем этим спискам первый элемент:

 [1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],[1,3,2],[1,3,3]
 

и аналогично со вторым и третьим элементами:

 [2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3]
[3,1,1],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3]
 

для создания полного списка результатов.

В качестве понимания списка это будет выглядеть так:

 combos n lst = [x:xs | x <- lst, xs <- combos (n-1) lst]
 

Нам также нужен базовый вариант для рекурсии. Мы можем использовать:

 combos 0 lst = [[]]
 

Полное определение:

 combos :: Int -> [a] -> [[a]]
combos 0 lst = [[]]
combos n lst = [x:xs | x <- lst, xs <- combos (n-1) lst]
 

и это работает так, как задумано:

 > combos 3 [1,2,3]
[[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],[1,3,2],[1,3,3]
,[2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3]
,[3,1,1],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3]]