Permutations of integers with sum restrictions

1 次查看（过去 30 天）
Christoph Heilmann
评论： 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

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

采纳的回答

Suraj Mankulangara
Suraj Mankulangara 2018-3-13
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 个评论
Christoph Heilmann
Christoph Heilmann 2018-3-15
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

请先登录，再进行评论。

更多回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Special Functions 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by