如何生成特定大小的整数分区 [英] how to generate integer partitions of a specific size

问题描述

我正在尝试编写此功能

variation_models' nlocations =
  let location_list = [1..nlocations-4]
  in [[x1, x2, x3, x4, x5] |
      x1 <- location_list,
      x2 <- location_list,
      x3 <- location_list,
      x4 <- location_list,
      x5 <- location_list,
      both_conditions (adds_up_to nlocations) num_orderedq [x1, x2, x3, x4, x5]]

，但可以有任意多个x.我希望variation_models 5 15的有效答案是[1,1,1,1,11].

but have any number of x's. I want variation_models 5 15 to have a valid answer of [1,1,1,1,11].

我当前的尝试是

variation_models ncars nlocations =
  filter (both_conditions (adds_up_to nlocations) num_orderedq) $
  replicateM ncars [1..nlocations-ncars+1]

但是 replicateM似乎使函数占用了越来越多的内存.

有没有关于如何编写copyM替代品以使其不消耗太多内存的想法?

Any Ideas on how to write a replacement for replicateM so that it does not consume as much memory?

使用的其余定义:

import Control.Monad

orderedq f [] = True
orderedq f (x:[]) = True
orderedq f (x:y:zs) = f x y && orderedq f (y:zs)

num_orderedq = orderedq (<=)

adds_up_to n xs = n == sum xs

both_conditions f g xs = f xs && g xs

variation_models ncars nlocations =
  filter (both_conditions (adds_up_to nlocations) num_orderedq) $
  replicateM ncars [1..nlocations-ncars+1]

variation_models' nlocations =
  let location_list = [1..nlocations-4]
  in [[x1, x2, x3, x4, x5] |
      x1 <- location_list,
      x2 <- location_list,
      x3 <- location_list,
      x4 <- location_list,
      x5 <- location_list,
      both_conditions (adds_up_to nlocations) num_orderedq [x1, x2, x3, x4, x5]]

推荐答案

您似乎正在使用replicateM生成整数分区.

It looks like you are using replicateM to generate integer partitions.

integer_partitions :: Int -> Int -> [[Int]]
integer_partitions 0 _ = []
integer_partitions 1 n = [[n]]
integer_partitions k n =
  do x <- [1..n - k + 1]
     map (x:) (integer_partitions (k - 1) (n - x)) 

它似乎比一般的replicateM

这篇关于如何生成特定大小的整数分区的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！