CODEWITHSUNDEEP
algorithmmatlabconstraintspermutation
Alvin Nunez
Alvin Nunez

Reputation: 247

Finding all possible permutations with a sum constraint and a redundancy option? (MATLAB)

I had the following problem in mind:

There is a hypothetical revered musician who is retired. The musician receives royalty checks for their past recordings from time to time. The musician's royalty checks always come in as:

$1, $5, $8, $12, $17, $20, $42, $100, or $200

This means that the musician ONLY receives royalty checks in the amounts specified above. I was wondering, how would I go about computing the total number of possible ways the musician can get paid to amass $1,000? There are some constraints/allowed assumptions in this problem. These are:

(1) There is no cap on the total amount of "checks" the musician can receive to get $1,000. For example, the musician can receive 1,000 $1 checks, 5 $200 checks, or 10 $20 checks and 4 $200 checks, etc. etc.

(2) As (1) implies, you can receive multiples of any checks (in fact, the sum of all singular check options totals $405, making this condition imperative to amass $1,000).

(3) Order matters. Getting paid $200, $200, $100, $100, $100, $100, $100, and $100 is a different "solution" than $100, $100, $100, $100, $100, $100, $200, and $200, which is also a different "solution" than $200, $100, $100, $200, $100, $100, $100, and $100, even though both solutions contain 6 $100 checks and 2 $200 checks. Remember, the musician gets paid checks "from time to time", so the order of check reception makes for the possibility of different solutions (permutations).

I am interested in finding only the total amount of solutions to solve this problem with the given check possibilities, not printing them out.

This is my approach so far:

However, I don't know how to incorporate x1, x2, x3 and their permutations in a given equation, and I don't know how to solve such equation.

Upvotes: 1

Views: 733

Answers (1)

Daniel
Daniel

Reputation: 36710

This is my idea to solve it, following the pattern of dynamic programming:

checks=[1,5,8,12,17,20,42,100,200];
target=300;
M=[checks;ones(size(checks))];
while M(1,1)<target
    %we know that there are #possibilities to get a sum of value
    value=M(1,1);
    possibilities=M(2,1);
    M(:,1)=[];
    disp(value)
    %combine value with each check:
    for idx=1:numel(checks)
        if value+checks(idx)<=target
            ii=find(M(1,:)==value+checks(idx),1,'first');
            if isempty(ii)
                M(:,end+1)=[value+checks(idx),possibilities];
            else
                M(2,ii)=M(2,ii)+possibilities;
            end
        end
    end
    %Sort M by value
    [a,idx]=sort(M(1,:));
    M=M(:,idx);
end

You can do it manually, create a table (variable M) with the value (summed up) and the number of possibilities to get this value. Initialize it with 1 possibility for each value you can get directly with a check.

Now repeat until you get your intended value:

  • Pop your first entry from the table (smallest value). Recombine it with each check (used once) and reinsert it to the table.
  • When the combined value is already in the table, sum up the numbers.
  • When the combined value is not in the table, insert a new entry.

While on a theoretical level this approac is precises, it quickly exceeds floating point precision. For the target value of 300, the result is ~10^42 which exceeds floating point precision. Is the symbolic toolbox available, then you could switch to vpa?

Upvotes: 2

Related Questions