Permutations of integers with sum restrictions

Question

Christoph Heilmann 2018-3-1

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/385751-permutations-of-integers-with-sum-restrictions

评论： Christoph Heilmann 2018-3-15

Hi Matlab gurus,

I would like to find all possible permutations of [-1 0 1] for a varying with varying length with a restriction on the overall sum across on permutation.

npermutek([-1 0 1],n) already allows me to find all possible permutations with varying length n. Is there a way to add the additional sum restriction across all permutations (e.g., n = 3 but output should only include permutations with a sum of 2)?

Since the length goes up to n=40 I running npermutek([-1 0 1],n) would be unfeasible without additional restrictions.

Any help on this issues would be greatly appreciated.

Thanks, Christoph

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Suraj Mankulangara 2018-3-13

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/385751-permutations-of-integers-with-sum-restrictions#answer_309775

在 MATLAB Online 中打开

Hi Christoph

There are a couple of ways that you can do this:

1. Edit the source code of the "npermutek" function. Where the permutation row is calculated, find the sum of that row. Only add those rows to the matrix that meet the sum restriction

2. Alternatively, you can do:

permutedMatrix = npermutek([2 4 5], 2); % Returns permutations of length 2
permutedMatrix(sum(permutedMatrix, 2) <= maxSum, :) % Returns only those permutations whose sum is less than or equal to maxSum

The second method will allow you to continue using npermutek without making any modifications, if that is of interest to you.

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Christoph Heilmann 2018-3-15

npermutek.m

Hi Suraj,

thank you very much for your answer. Your second alternative works, however this does not yet allow longer permutations since this initial matrix is constructed without the restrictions and exceeds the maximum array size preference. For permutations longer than 16 I get the following error: "Requested 129140163x17 (16.4GB) array exceeds maximum array size preference. Creation of arrays greater than this limit may take a long time and cause MATLAB to become unresponsive. See array size limit or preference panel for more information."

I am not sure how to implement your first alternative since npermutek does not calculated each row individually as I understand. Any advice on how I could get this to work would be awesome. Attached is the code I am using.

Best regards Christoph

请先登录，再进行评论。