Permutations with Replacement & Constraint

2 views (last 30 days)
Karl
Karl on 10 Oct 2011
Given n options or 'off' for each of of two classes (say, -n:step:n) taken m at a time, how many permutations are possible subject to the additional constraint that the sum of elements > 0 is <k and sum of elements < 0 is > -k?
Perhaps a valid example would be a red/blue LED lightshow bar. The LEDs can handle up to 10 A in 0.1V steps. There are five red/blue led pairs on a bar; either the red or blue LED in each pair is lit, or both are off. How many different lightshows are possible if the two PSUs (one for red, one for blue) can only supply 20A total (let's set aside any circuit considerations of the example :p)?
Attempting to count the number of possible lightshows using loops & logic tests is extremely slow (unmexed) with even low m, due in great part to the logic test. e.g.:
limit = 20;
n = 10;
dn = 0.1;
count = 0;
for a = -n:dn:n
for b = -n:dn:n
temp = [a,b];
if a==0 || b==0 || (sum(temp(temp > 0)) < limit) || (sum(temp(temp < 0)) > -limit)
for c = -n:dn:n
temp = [a,b,c];
if c==0 || (sum(temp(temp > 0)) < limit) || (sum(temp(temp < 0)) > -limit)
count = count + 1;
end%if
end%for
end%if
end%for
end%for
count
I have wondered if it's possible to solve smaller portions of the problem using closed-form equations and then sum and product to the full number of lightshows. (e.g., nchoosek to select combinations of 'lit' LED pairs of each 1:m [10,1 ; 10,2 ; ... 10,5], then permutations of positive & negative values of n given each combination [100,1; 100,2;...100,5], then combine). I still have trouble reasoning how to implement the constraint, though, as not all permutations w/ replacement are valid.
Thanks for looking! Please share any insight. I will clarify or share more of my attempts at the problem to the best of my ability if it will be helpful.
-Karl

Answers (0)

Categories

Find more on Construct and Work with Object Arrays in Help Center and File Exchange

Community Treasure Hunt

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

Start Hunting!