Permutations of integers with sum restrictions

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

Answer 1

[Suraj Mankulangara]

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.

[Christoph Heilmann]

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