select a group of pairs in order to minimize rms of group

Question

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.

Answer 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:

Answer 2

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);
}

Answer 3

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.

Answer 4

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.