4

Simplified problem

I have ~40 resistors (all the same value +-5%) and I need to select 12 of them so that they are as similar as possible.

Solution: I list them in order and take the 12 consecutive with the smallest RMS.

The actual problem

I have ~40 resistors (all the same value +-5%) and I have to choose 12 pairs of them so that the resistance of the pairs is as similar as possible.

Notes

The resistance of the pair (R1,R2) is R1+R2. I do not really care about the programming language, but let's say that I'm looking for a solution in C++ or Python, the two languages I'm most familiar with.

muzzle
  • 315
  • 3
  • 9
  • The only solution I could think of is to could compute the resistance of all ~1600 pairs, order them, take the 12 consecutive with the smallest RMS and pray I did not pick the same resistance twice. – muzzle Jun 17 '13 at 15:48
  • And you want to do this in ...? MATLAB? C? – Stewie Griffin Jun 17 '13 at 15:50
  • For bonus points: propose a solution to solve the same problem with 12 **triplets** of resistors. – muzzle Jun 17 '13 at 15:53
  • @RobertP. it does not really matter, let's say C++ or Python, the two languages I'm most familiar with. – muzzle Jun 17 '13 at 15:54
  • If a pair is (R1, R2), what is the resistance of the pair? And you want to minimize RMS of those 12 pairwise resistances? Or do you want to pick 24 resistors and minimize the RMS of their resistances? – svinja Jun 17 '13 at 16:07
  • The very simplified version would be to create two sorted vectors in ascending and descending order, add the rows together, and select the 12 pairs that are closest to the mean value. However, I'm quite positive someone will come up with a super clever way of doing this, so I won't even bother putting this as an answer... – Stewie Griffin Jun 17 '13 at 16:09
  • @svinja, the resistance of a pair (R1,R2) is R1+R2, and I need to minimize the RMS of the resistances (R1+R2) of the 12 pairs. – muzzle Jun 17 '13 at 16:22

4 Answers4

1

This gives reasonably good results (in MATLAB)

a = ones(40,1) + rand(40,1)*0.1-0.05; % The resistors
vec = zeros(40,2);        % Initialize matrix
indices = zeros(40,2);    % Initialize matrix
a = sort(a);              % Sort vector of resistors
for ii = 1:length(a)
  vec(ii,:) = [a(ii) a(ii)];    % Assign resistor values to row ii of vec
  indices(ii,:) = [ii,ii];      % Corresponding resistor number (index)
  for jj = 1:length(a)
    if sum(abs((a(ii)+a(jj))-2*mean(a))) < abs(sum(vec(ii,:))-2*mean(a))
      vec(ii,:) =  [a(ii) a(jj)];    % Check if the new set is better than the
      indices(ii,:) = [ii, jj];      % previous, and update vec and indices if true.
    end
  end
end

[x, idx] = sort(sum(vec')');   % Sort the sum of the pairs 
final_list = indices(idx);     % The indices of the sorted pairs

This is the result when I plot it:

enter image description here

Stewie Griffin
  • 14,889
  • 11
  • 39
  • 70
  • Thanks! I'm not too familiar with MATLAB, can you describe what you are doing so I can implement it? – muzzle Jun 17 '13 at 16:52
  • Sorry, I don't have the time... The loops and ifs are identical (except syntax) to C++. The first parts are just memory allocation, and sorting of the resistor list. You will, for all resistors, get the resistor that "fits best". That is `ii` goes best with `jj`. The `final_list` matrix is sorted, and is what you're after. – Stewie Griffin Jun 17 '13 at 17:04
  • @muzzle: Added some comments. `sum, abs, mean, sort, length` etc. are built-in functions in Matlab, that does exactly what you would guess. – Stewie Griffin Jun 17 '13 at 17:39
1

This is not optimal but should give somewhat decent results. It's very fast though so if you ever need to choose 1000 pairs out of 10000 resistors...

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>

#define GROUPS 12
#define N 40

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int main ()
{
    // generate random numbers 
    float *values = (float *)malloc(sizeof(float) * N);
    srand(time(0));
    for (int i = 0; i < N; i++)
        values[i] = 950 + rand()%101;

    qsort(values, N, sizeof(float), compare);

    // find "best" pairing
    float bestrms = -1;
    int beststart = -1;
    float bestmean = -1;
    for (int start = 0; start <= N - 2 * GROUPS; start++)
    {
        float sum = 0;
        for (int i = start; i < start + 2 * GROUPS; i++)
            sum += values[i];

        float mean = sum / GROUPS;

        float square = 0;
        for (int i = 0; i < GROUPS; i++)
        {
            int x = start + 2 * GROUPS - 1 - i;
            float first = values[start + i];
            // in a sorted sequence of 24 resistors, always pair 1st with 24th, 2nd with 23rd, etc
            float second = values[start + 2 * GROUPS - 1 - i];
            float err = mean - (first + second);
            square += err * err;
        }

        float rms = sqrt(square/GROUPS);       

        if (bestrms == -1 || rms < bestrms)
        {
            bestrms = rms;
            beststart = start;
            bestmean = mean;
        }
    }

    for (int i = 0; i < GROUPS; i++)
    {             
        float first = values[beststart + i];
        float second = values[beststart + 2 * GROUPS - 1 - i];
        float err = bestmean - (first + second);
        printf("(%f, %f) %f %f\n", first, second, first + second, err);
    }
    printf("mean %f rms %f\n", bestmean, bestrms);
    free(values);
}
svinja
  • 5,495
  • 5
  • 25
  • 43
0

Sort them and then pair 1 with 2, 3 with 4, 5 with 6 and so on. Find the difference between each pair and sort again, choosing the 12 with the least difference.

Tyler Durden
  • 11,156
  • 9
  • 64
  • 126
0
  1. sort them by resistance
  2. pair 1 with 40, 2 with 39 etc, compute R1+R2 for each pair and pick the best set of 12 pairs (needs another sorting step). compute the mean of all select (R1+R2).
  3. try to refine this initial solution successively by trying to plug in one of the remaining 16 resistors for one of the 24 chosen ones. an attempt would be successful if combined resistance of the new pair is closer to the mean than the combined resistance of the old pair. repeat this step until you can't find any further improvement.

this solution will definitely not always compute the optimal solution but it might be good enough. another idea would be simulated annealing but that would be a lot more work and still not guarantee to find the best solution.

user829755
  • 1,489
  • 13
  • 27