Jane’s Homework

December 12, 2017

Today’s exercise is from user Jane, who needs homework help:

Consider all partitionings of a list of positive integers into two partitions. For each partitioning, compute the sums of the two partitions, then compute the least common multiple of the two sums. Report the maximum of all possible least common multiples. For example, given the list (2 3 4 6), the possible partitionings, the associated sums, and the least common multiples, are:

    () (2 3 4 6) -  0 15 -  0
    (2)  (3 4 6) -  2 13 - 26
    (3)  (2 4 6) -  3 12 - 12
    (2 3)  (4 6) -  5 10 - 10
    (4)  (2 3 6) -  4 11 - 44
    (2 4)  (3 6) -  6  9 - 18
    (3 4)  (2 6) -  7  8 - 56
    (2 3 4)  (6) -  9  6 - 18
    (6)  (2 3 4) -  6  9 - 18
    (2 6)  (3 4) -  8  7 - 56
    (3 6)  (2 4) -  9  6 - 18
    (2 3 6)  (4) - 11  4 - 44
    (4 6)  (2 3) - 10  5 - 10
    (2 4 6)  (3) - 12  3 - 12
    (3 4 6)  (2) - 13  2 - 26
    (2 3 4 6) () - 15  0 -  0

Thus, the maximum least common multiple is 56.

Jane writes that she wants to be able to recursively find all partitions given a list, and she thinks she will have to use lambda in her program.

Your task is to write a program that finds the maximum least common multiple of the part-sums of all possible 2-partitionings of a list of positive integers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2