How to calculate all permutations of a vector that satisfy a given condition

I'd like to calculate all permutations of the vector N taken k at a time. I also want to allow any element of N to permute with itself not only with other elements. I only want to get permutations that sum up to a given number n.

Here is an example in MATLAB:

N = [1 2 3 4];
k = 2;
n = 6;

For numbers above, I could reach my target by doing:

Perm = combvec(N, N)';
Perm = Perm(sum(Perm,2)==n,:);
Perm =

     4     2
     3     3
     2     4

However, N is expected to be up to 90 elements long and value of k up to 10. This makes the above way is infeasible as it involves calculation of many permutations that are not needed.

Is there any way of doing this efficiently given the expected N vector length and k?

[Walter Roberson]

This is what is referred to as a Knapsack Problem. You might want to search for algorithms for those.

[Bruno Luong]

No it is not a Knapsack Problem

[Walter Roberson]

Yes it is. The contents of N are the weights, and the selection of weights must add up to a fixed value. That is a Knapsack problem. Once all of knapsack solutions are known, then you can permute each of them.

[Bruno Luong]

NOPE There are subtility that you don't see the difference Walter

1. knapsack try to maximize an objective that here there is none
2. knsack problem try to find a single combination that maximizes the score (no more), here is ALL combinations that reach a sum.

[Jos (10584)]

There are 90^10 = 34867844009999998976 possible combinations that you need to check or exclude somehow ... I am not sure what your real problem is, but are you sure this is the right approach?

[Walter Roberson]

Bruno:

https://en.wikipedia.org/wiki/Knapsack_problem

Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

Here the weights are the contents of N, and the value of each is 0; furthermore it is a binary knapsack problem as each item is to be either present or not.

It does not not require the full power of more general knapsack problems, but it is a knapsack problem.

[Bruno Luong]

No I have already explained why it is not quite the same.

The problem here is falls into enumerative combinatorics problem, the knapsack is a discrete optimization problem.

If you convince otherwise please show us the MATLAB code using knapsack.

Here is solving knacksack using INTLINPROG

N = [1 2 3 4];
k = 2;
n = 6; % 16

% knapsack solver using INTLINPROG
f = -N(:);
intcon = 1:4;
A = N(:).';
b = 6;
Aeq = ones(1,4);
beq = k;
lb = 0+zeros(4,1);
ub = 1+zeros(4,1);
x = intlinprog(f, intcon, A, b, Aeq, beq, lb, ub);
keep = logical(x);
c = N(keep)

It returns one solution for n=6, and for n=16 it's still return one solution (where one can discard by checking the sum), but in anycase it won't solve the problem posted above.

[Walter Roberson]

The problem here is falls into enumerative combinatorics problem, the knapsack is a discrete optimization problem.

There can be multiple approaches to the same problem.

This is a classic constrained knapsack problem:

"Given a set of objects of different sizes, with a pre-set number of copies of each different size, find a combination of objects that comes closest to filling up a knapsack of fixed carrying capacity."

In this case, the number of copies of each is restricted to 1 (which is called a "binary knapsack".

Given any particular solution that exactly fills up the knapsack, you can then proceed to permute it mechanically to get the permutations needed by the user.

Answer 1

[Bruno Luong]

If your vector is consecutive number, you can directly use this allVL1 in the File Exchange.

Otherwise you can adapt the subfunction allVL1recurs as following

function c = allVL1recurs(V, n, L1, head)
% function v=allVL1eq(V, n, L1);
% INPUT
%    V: vector of allowed values
%    n: number of elements to pick from V
%    L1: desired L1 norm
% OUTPUT:
%    c: (m x n) array such as sum(c,2)==L1
%        v is n elements in V
%        c contains all (=m) possible combinations
% Algorithm:
%    Recursive
if n==1
    if any(V==L1)
        c = L1;
    else
        c = zeros(0,1,class(L1));
    end
elseif sum(V) < L1 % optional test branch
    c = zeros(0,1,class(L1));
else % recursive call
    c = cell(size(V));
    for k=1:length(V)
        j = V(k);
        c{k} = allVL1recurs(V, n-1, L1-j, j);
    end
    c = cat(1,c{:});
end
if nargin>=4 % add a head column
    c = [head+zeros(size(c,1),1,class(head)) c];
end
end % allVL1recurs

Test

>> c = allVL1recurs([1:4], 2, 6)


c =

     2     4
     3     3
     4     2

Edit: I fix the buggy code

[ANITKUMAR VANTIYA]

I am a beginer in Matlab

This code rises to some errors, when I tried to run as a new script (online). I copied following in new script

function c = allVL1recurs(V, n, L1, head)
% function v=allVL1eq(V, n, L1);
% INPUT
%    V: vector of allowed values
%    n: number of elements to pick from V
%    L1: desired L1 norm
% OUTPUT:
%    c: (m x n) array such as sum(c,2)==L1
%        v is n elements in V
%        c contains all (=m) possible combinations
% Algorithm:
%    Recursive
if n==1
    if any(V==L1)
        c = L1;
    else
        c = zeros(0,1,class(L1));
    end
elseif sum(V) < L1 % optional test branch
    c = zeros(0,1,class(L1));
else % recursive call
    c = cell(size(V));
    for k=1:length(V)
        j = V(k);
        c{k} = allVL1recurs(V, n-1, L1-j, j);
    end
    c = cat(1,c{:});
end
if nargin>=4 % add a head column
    c = [head+zeros(size(c,1),1,class(head)) c];
end
end % allVL1recurs
g = allVL1recurs([1:4], 2, 6)
disp(g)

Then it shows error:

>> Anit2
Error: File: Anit2.m Line: 33 Column: 1
This statement is not inside any function.
 (It follows the END that terminates the definition of the function "allVL1recurs".)

When I put the "last two lines" before the last "end" of function definition:

end
g = allVL1recurs([1:4], 2, 6)
disp(g)
end % allVL1recurs

Again it shows error

>> Anit2
Not enough input arguments.

Error in Anit2 (line 13)
if n==1