The problem of removing the data from the matrix

I have an array including about 100 numbers.We assume the number is from 1 to 100.I want to get 7 numbers from the array, then calculate the sum of these numbers. If the sum value is in the range of two known number.We get these seven number and dispaly.oterwise we go on to find the sum value between the known number until all the arrangement method have been tried. I want to get the matlab programming code to complete it,i really don't have a good method. Look forward to you help.Thank you!

[Jan]

This sounds like a homework question. Because it is neither wanted nor useful if we solve your homework, please follow the standard procedure: Show us, what you have done so far and ask if any specific problem occurs.

[Jan]

@chengxuan yu: It is enough, if you post the messages here. Please consider my profile and do *not* send me emails. And if you send an email (to somebody who like this), then include a link to the question. It is not convenient to search for the topic you are talking about.

[Walter Roberson]

This is a technical forum for civil discussions. Personal arguments or justifications will be removed.

[Jan]

@Walter: To be exact, this is a technical forum for questions related to Matlab.

@chengxuan yu: I do not answer questions sent by email. I do answer here in this forum.

Of course you are allowed to say what you want. And the editors have the power to remove it according to these guidelines:

1. Personal attacs

2. Off-topic content not related to MATLAB or any MathWorks products

Walter keeps the forum clean. He is assiduous and careful. I like it.

Answer 1

[Andrei Bobrov]

variant

d = randperm(100).';
idx = bsxfun(@plus,1:7,(0:numel(d)-7)');
d1 = d(idx);
ou1 = sum(d1,2);
bnd = [250 300] % Interval borders
[c c] = histc(ou1,bnd);
out = d1(find(c,1,'first'),:)

simple variant

d = randperm(100).'; % your data
n = 7;
bnd = [250 300];
n1 = 0:n-1;
for j1 = 1:numel(d)-n+1
    i1 = j1 + n1;
    s1 = sum(d(i1));
    if s1 >= bnd(1) && s1 <= bnd(2)
        out = d(i1);
        break
    end
end

[Jan]

It will not be easy for yu to explain this solution of the homework.

[chengxuan yu]

The simple variant can get continous result, but it only output part of the combination method. How can i get all the combination metod?

Answer 2

[Fangjun Jiang]

The following code could solve your problem if you have enough memory. N is set at 10 first so you can try and understand the code. nchoosek(10,7) is 120 combinations. Among them, anywhere from 20 to 80 combinations might meet the criteria depending on the random data. nchoosek(100,7) will be 1.6008e+010 combinations. I don't think a personal computer at this age will have 16*8*8G memory so maybe this solution is not practical. In the meantime, take a look to see if this is a solution (for a small scale). I'll think about if there is a way to not to use the huge array, maybe use a long for-loop. Someone else might chip in too.

N=10;
K=7;
V_min=3;
V_max=4;

Data=rand(N,1);
Index=nchoosek(1:N,K);
M=size(Index,1);
Flag=false(M,1);
for j=1:M
    Select=Data(Index(j,:));
    Total=sum(Select);
    Flag(j)=and(V_min<Total,Total<V_max);
end
SelectedData=Data(Index(Flag,:))
size(SelectedData,1)

[chengxuan yu]

Just now I running your program.If N is number,it can have result,but if N is a vector, it doesn't work.I also thougth use for- loop.but I cannot write it well. The actual problem is this,I have the data below, That was all the data I have. They are 127 battery cells voltage. I want choose 7 between them to make up battery pack,which making the pack voltage is between 77.05 and 77.85.I want to get as many pack as possible. So I must know how to combine them.

10.866

11.0957

10.9235

10.9357

11.121

11.0172

11.204

10.7411

11.233

10.7411

11.304

11.43

11.3116

11.4252

11.2561

11.2136

11.2529

11.288

11.353

11.2135

11.274

11.3288

13.0326

13.0389

13.021

13.0716

13.0399

13.0177

13.0297

13.0366

13.0173

13.0006

13.0061

13.7852

13.8199

13.8602

13.8133

13.7394

13.6925

13.6472

13.7704

11.3288

12.1985

12.1771

12.2468

12.1428

12.2267

10.9119

11.018

9.8768

9.9391

10.9587

10.8442

11.002

10.8963

10.7968

10.9584

10.9174

11.0768

10.3929

10.6948

10.8723

11.0513

11.1445

11.1231

11.0267

11.0055

11.1285

11.0819

11.0273

11.0783

11.0346

11.1789

11.0578

11.0693

10.8994

11.0868

11.2318

10.9432

9.6885

8.9472

11.6253

11.6791

11.6072

11.666

11.746

11.6042

9.5838

9.6636

8.9982

11.6352

11.6809

11.6358

11.6418

11.5941

11.6731

10.3308

10.4433

9.7064

9.0447

10.6631

10.6594

10.5641

10.5523

10.543

10.6785

10.4593

10.5995

10.6576

10.7239

10.6486

11.1344

11.1412

11.0046

10.7201

11.1397

10.7368

11.0692

11.1128

10.4428

10.9322

11.0642

11.0944

11.1896

11.329

11.1137

11.0596

[Jan]

@Fangjun: You do not need 16*8*8GB memory, if you create a tree and store only the last combination. For brute-force searching the tree will be too large: it has 1.6E10 nodes in the 1st level (100over7), 9.47E9 in the 2nd level (93over7), etc. Therefore you have to cut branches, which violates the conditions. Even then an exhaustive search will use a lot of resources, such that running the program might be more expensive than buying matching battery packs. Therefore I hoped, it is a homework only...

@chengxuan yu: To minimize the total costs (programming time + run time + costs of the batteries) I suggest either a GA method or a simple gunshot technique: Choose 15 packs randomly, swap 1, 2, or 3 random elements of the packs with the worst voltage.

BTW.: It is ridiculous to determine the voltage of a batterie as 10.7201 V. The voltage depends at first on the intensity of the current due to the internal resistance, at second on the temperature (which changes during usage), at third on the life-time of the battery (it will change during your optimization program runs!). If this is really not a homework, this is an ugly design error.

[Jan]

@chengxuan yu: I've implemented the naive approach: Choose 7 batteries randomly (see RANDPERM or the faster SHUFFLE from the FEX) and accept them, if they match. Remove them from the pool and proceed with the next pack.

There are a lot of solutions for 16 packs, but I did not find one for 17.

[chengxuan yu]

Jan Simon,I have already said not one time, this is not a homework question, If you still stick to your ideas, you can choose not answer my question. At here, I thanked the help you give me.

[Fangjun Jiang]

@chengxuan, you didn't fully understand the code. N is the number of data points you have. Data=rand(N,1) is the data points in my code, which should correspond to your 127x1 voltage data.

[Fangjun Jiang]

@Simon: Jan, I found this problem interesting. I doubt it is a homework as a professor might give a nchoosek(10,7) but not a nchoosek(100,7) problem.

Answer 3

[Jan]

There are no solutions with more than 16 batteries, because the mean voltage rate is above the upper limit 7.85. One of the many solutions:

V = [ ...
 10.866, 11.0957, 10.9235, 10.9357, 11.121, 11.0172, 11.204, 10.7411, 11.233, ...
 10.7411, 11.304, 11.43, 11.3116, 11.4252, 11.2561, 11.2136, 11.2529, 11.288, ...
 11.353, 11.2135, 11.274, 11.3288, 13.0326, 13.0389, 13.021, 13.0716, 13.0399, ...
 13.0177, 13.0297, 13.0366, 13.0173, 13.0006, 13.0061, 13.7852, 13.8199, ...
 13.8602, 13.8133, 13.7394, 13.6925, 13.6472, 13.7704, 11.3288, 12.1985, ...
 12.1771, 12.2468, 12.1428, 12.2267, 10.9119, 11.018, 9.8768, 9.9391, 10.9587, ...
 10.8442, 11.002, 10.8963, 10.7968, 10.9584, 10.9174, 11.0768, 10.3929, 10.6948, ...
 10.8723, 11.0513, 11.1445, 11.1231, 11.0267, 11.0055, 11.1285, 11.0819, ...
 11.0273, 11.0783, 11.0346, 11.1789, 11.0578, 11.0693, 10.8994, 11.0868, ...
 11.2318, 10.9432, 9.6885, 8.9472, 11.6253, 11.6791, 11.6072, 11.666, 11.746, ...
 11.6042, 9.5838, 9.6636, 8.9982, 11.6352, 11.6809, 11.6358, 11.6418, 11.5941, ...
 11.6731, 10.3308, 10.4433, 9.7064, 9.0447, 10.6631, 10.6594, 10.5641, 10.5523, ...
 10.543, 10.6785, 10.4593, 10.5995, 10.6576, 10.7239, 10.6486, 11.1344, 11.1412, ...
 11.0046, 10.7201, 11.1397, 10.7368, 11.0692, 11.1128, 10.4428, 10.9322, ...
 11.0642, 11.0944, 11.1896, 11.329, 11.1137, 11.0596];

Index = [ ...
 81, 71, 42, 96, 11, 45, 41, 75, 56, 118, 76, 43, 98, 93, 101, 114; ...
 25, 90, 62, 14, 79, 107, 20, 103, 84, 33, 91, 126, 87, 12, 13, 27; ...
 70, 80, 5, 63, 95, 69, 97, 59, 17, 94, 58, 73, 74, 106, 55, 50; ...
 19, 47, 85, 120, 109, 77, 110, 2, 104, 3, 48, 57, 86, 8, 78, 102; ...
 99, 116, 7, 10, 83, 122, 52, 6, 88, 49, 113, 61, 123, 54, 64, 1; ...
 115, 31, 105, 112, 121, 66, 65, 51, 30, 72, 82, 60, 119, 127, 15, 68; ...
 32, 92, 67, 22, 111, 53, 89, 26, 4, 100, 108, 124, 117, 18, 125, 9];

disp(sum(V(Index), 1));

Using the gunshot technique finding the solutions is even faster, if the limits 77.7 < sum(V) & sumV < 77.85 are used. Then my program needs about 0.1 to 2 seconds, average 1.1 seconds. In addition increasing the lower limit let the batteries remain longer in the wanted voltage range.

The unused batteries have a too high voltage and you can even create a pack of 6 to get the required limits. Is this allowed?

Sorry for my idea that this is a homework. The values look extremly artificial and it is a very bad idea to connect batteries with 9.1V and 13.8V in series. What will happen if the weakest battery is exhausted?! So please be careful if you apply the solution and replace weak batteries as soon as possible.

As far as I understand, one solution is enough for you. But here is the program, if anybody else is interested:

% V = [... values from above]
Idx = uint8(1):uint8(length(V));
R   = zeros(7, 18, 'uint8');
iR  = 0;
for i = 1:1e5  % No infinite loops
  test = Shuffle(length(Idx), 'index', 7);  % or "randperm(length(Idx), 7)"
  sumV = sum(V(Idx(test)));
  if and(77.7 < sumV, sumV < 77.85)  % Actually "77.05 < sumV"
    iR        = iR + 1;
    R(:, iR)  = Idx(test);
    Idx(test) = [];
    % Stop early, if you have proven, that there is no 17th solution:
    % if iR == 16, break; end
  end
end

Note: For RANDPERM(N,M) Matlab 2011b is required. FEX: Shuffle.

Answer 4

[Jan]

@Fangjun: UNIQUE is slow. A tiny change let the program rum 11 times faster (70 sec -> 6 sec):

N     = 8
K     = 7;
V_min = 3.5;
V_max = 3.8;
Data  = rand(N, 1);
% fid=fopen('output.csv', 'w');
Fmt = [repmat('%d,',1,K-1),'%d\n'];
for j1=1:N
  for j2=1:N
    for j3=1:N
       for j4=1:N
          for j5=1:N
             for j6=1:N
                for j7=1:N
                   % CHANGED: UNIQUE->SORT
                   Index = sort([j1 j2 j3 j4 j5 j6 j7]);
                   if all(diff(Index)) == 0
                      continue;
                   end
                   Total = sum(Data(Index));
                   if V_min < Total && Total < V_max  % AND->&&
                     fprintf(Fmt, Index);
                   end
                end
             end
          end
       end
    end
  end
end
% fclose(fid)

But it would be fast to cut the branches early and exclude non-unique indices directly after choosing them:

for j1=1:N
   for j2=1:N
      if j1~=j2
         for j3=1:N
            if j3~=j1 && j3~=j2
               for j4=1:N
                  if j4 ~= j1 && j4 ~= j2 && j4 ~= j3
                     for j5=1:N
                        if j5 ~= j1 && j5 ~= j2 && j5 ~= j3 && j5 ~= j4
                           for j6=1:N
                              if j6 ~= j1 && j6 ~= j2 && j6 ~= j3 && ...
                                 j6 ~= j4 && j6 ~= j5
                                 for j7=1:N
                                    if j7 ~= j1 && j7 ~= j2 && j7 ~= j3 && ...
                                          j7 ~= j4 && j7 ~= j5 && j7 ~= j6
                                       Index = [j1 j2 j3 j4 j5 j6 j7];
                                       Total=sum(Data(Index));
                                       if V_min<Total && Total<V_max
                                          % fprintf(Fmt, Index);
                                       end
                                    end
                                 end
                              end
                           end
                        end
                     end
                  end
               end
            end
         end
      end
   end
end

0.24 sec. About 300 times faster - then the full program runs for 6 month only.

[EDITED: 09Nov2011 11:07 UTC] The above solutions create duplicate answers - 5040 for N=8. This can be avoided if the indices are created in a sorted order already:

for j1=1:N
  for j2=j1+1:N
    for j3=j2+1:N
      for j4=j3+1:N
        for j5=j4+1:N
          for j6=j5+1:N
            for j7=j6+1:N
              Index = [j1 j2 j3 j4 j5 j6 j7];
              Total = sum(Data(Index));
              if V_min<Total && Total<V_max
                fprintf(Fmt, Index);
              end
            end
          end
        end
      end
    end
  end
end

Runtime for N=8: 0.000865 seconds

But currently the program creates a list of all packages with the desired property. But the author does not want a single package, but as much packages as possible. Therefore the main part remains unsolved by this method: Find a maximum set of non-overlapping packages.

[Fangjun Jiang]

Great improvement, Jan! Now we are at 15 years!

Would "if ~all(diff(Index))" help?

[Fangjun Jiang]

I thought about that but was too lazy to type in those logic. You did and it paid off!

[Fangjun Jiang]

Now it's time to look at the voltage data. If the target for 7 batteries is 77.05 to 77.85, we are looking at the average from 11 to 11.12. If we can narrow down the individual voltage from 10.5 to 11.5, the number of qualified batteries will be 77. If further narrow down to 10.8 to 11.3, the number will be 53. We are really looking at a possibility here.

[Jan]

@Fangjun: Have you seen my cruel gunshot method? Its charm is the power to be applicable to 10'000 entities also. It is fast and if you obtain 1000 of its good solutions, it is very likely, that the best one is fairly good - although it is usually not optimal. Well, it is a gunshot method - it has a lot of Wummms.

[Fangjun Jiang]

Great job, Jan! I though about a similar loop but didn't get it completely right. My initial though was below but missed the j1+1 part.

%%

N=8;

count=0;

for j1=1:N

for j2=j1:N

for j3=j2:N

count=count+1;

end

end

end

count

[Fangjun Jiang]

@Jan, I don't fully understand your "gunshot method". There is no "gunshot method" entry in wikipedia. You should enter one at your convenience. My guess is it randomly picks 7 batteries and check the voltage sum. Running the random selection large enough should return a good result. I explained this in my other answer too. But I can't understand in your answer why the number 16 is involved. And I can't find the reference of Shuffle() function although I can guess.

[chengxuan yu]

@Jan, I also don't understand your "gunshot method". I think it is good but I don't know how to use it. Can you explain it to us carefully, and how to use it, and who provide this method. We will both appreciate you.

[Jan]

@Fangjun: I've posted my gunshot code above on the 8th of Nov. "Gunshot" means, that the program is simple, free of intelligence, and even processes the inputs randomly - but it hits the mark at least near to the target. The best matching Wikipedia article is http://en.wikipedia.org/wiki/Anti-pattern . Sorry, I do not post the specific anchor - this technique is called "gunshot linking". ;-)

The 16 is a "magic number" (see anti-patterns): There ist simply no 17th soltuion, therefore the search can stop after finding 16 battery packs. You can insert a smarter break condition: If the sum of the 7 batteries with the smallest capacity is higher than the lower limit, stop the process.

There is a link to the Shuffle function on the bottom of my other answer above, so I do not think, that you have to _guess_.

Answer 5

[chengxuan yu]

Thank you for your answer, you solve part of my question.But what the remaining question is that only one array number is output.What I want to get is all the possiable array numbers.Hope you can give me a further help,I will very grateful you!

[Fangjun Jiang]

What do you mean "all the possible array numbers"? All the combination picking 7 numbers out of 100, or nchoosek(100,7) combinations?

[chengxuan yu]

Yes, what you think is right.But the function nchoosek I have alreay tried. The matlab command window cannot show that too much numbers.

[chengxuan yu]

oh,sorry,I didn't see your question clearly.I mean nchoosek(100,7) combination.

Answer 6

[Fangjun Jiang]

So this is a nchoosek() combination problem.

The theoretical solution:

Use index=nchoosek(1:100,7) to generate all the possible combinations, use index to select the batteries, sum the voltage and check against the range. The problem is that there is not enough memory to hold the index, which is a very large matrix, not even mention nchoosek(1:127,7).

The practical solution:

You don't really need all the possible solution. You just need the sufficiently enough solutions. You can generate a random index such as index=1+round(99*rand(7,1)). Use this index to select the battery and then check the sum. This is similar to Jan's solution. You can achieve the same even without shuffle() or the new randperm(N,M) function. Repeat the random selection large enough in a for-loop should give you a good result. Remember to check every time whether the index has duplicated numbers.

I think seeking the theoretical solution using MATLAB programming is still possible.

Use the following code, go through 7 levels of nested for-loop to get all the possible combinations. If the voltage sum is within range, write the battery index to a text file. Duplicated index within each combination has been taken care of. But for every combination that meets the criteria, it will be duplicated 5040 times (which is 7! or prod(1:7)). That is also the number of repeats that are executed in the code inside the for-loops. So the code is inefficient but it runs without hitting memory limits. For N=8, it takes about 100 seconds on my laptop. For N=100, it will take 100*(100^7/8^7) seconds which is 151 years! Darn! I thought it would be practical. But at least, it is not light-years. Oh, wait, light-year is not about time.

One more thing, the output .csv file contains 5040 duplicated copies for every valid selection, but that could be easily handled using Excel.

N=8;
K=7;
V_min=3.5;
V_max=3.8;
Data=rand(N,1);
fid=fopen('output.csv','wt');
for j1=1:N
    for j2=1:N
        for j3=1:N
            for j4=1:N
                for j5=1:N
                    for j6=1:N
                        for j7=1:N
                            Index=unique([j1 j2 j3 j4 j5 j6 j7]);
                            if size(Index,2)<K
                                continue;
                            end
                            Total=sum(Data(Index));
                            if and(V_min<Total,Total<V_max)
                                fprintf(fid,[repmat('%d,',1,K-1),'%d\n'],Index);
                            end
                        end
                    end
                end
            end
        end
    end
end
fclose(fid);

[chengxuan yu]

Thanks for the help of the two brothers,I will study the code carefully and make the program runs successfully.First,I apologized for the mistake that I said the data is voltage, just now I confirmed that the data is battery capacity. Finally, I found it is almost cannot find a way to solve the problem effectively.Because if the workshop start product battery, there will not just be 127 batterys. Just can I change the program you provide me and roughly calculate the array that can find between them.Hope a good way can be find to solve the problem. Once again sincerely thanks for the help of the two brothers.

[Jan]

Capacity is less dangerous, because I assume (hope) that the batteries are connected in parallel.

[chengxuan yu]

Yes, you are right,they parallel first and constitute a pack. Then every pack series together provide electronic energy.