Find combinations without repetitions from a given set

Hi All,

I have a matrix b of size 119x42, I'm trying to find the combinations without repetitions, that results in a vector of the same number of columns (42). For each column only the values in the rows for that column can be used for the combinations. Some of the values in the rows are NaN, as for each column there are different number of possible values to use.

I have attached my exact file with the variable b, as the matrix is too big to post here. Any ideas of how to find these combinations without repetitions will be much appreciated.

Best, Martha

[Image Analyst]

So is a combination one element picked from the rows in each of the 42 columns to produce a row vector 42 elements long? So you'd have 119 raised to the power of 42 different possible combinations. That's 1.5 times ten to the 87th power. Why do you think you want/need these?

[Walter Roberson]

It isn't that bad. There are a lot of nan in some of the columns. There are only 4548722599534245782518243022870582858110732708610581264993179244953600000 possibilities.

Furthermore, the values are all small, all integers between 1 and 124, so they fit within uint8, so each row would only take 42 bytes, less than 2^247 bytes in total.

At 1 million values generated per second, it would take less than 1.5 x 10^59 years to generate.

[Martha]

Hi,

Is there a way then, that you think that I can select a single combination without repetition for a vector of 42 columns? I'm using this matrix in a ga integer optimisation problem, and one of my constraints is that I need a solution where all the 42 elements are not repeated. The ga solver is not finding any solution, and I realise that is because all the solutions tested are not feasible (e.g. there are repetitions), only the initial guess I made by doing this

InitialGuess=zeros(1,42); InitialGuess(1)=b(1,1);
for i=2:42
  Temp=b(:,i);
  fo=~ismember(b(:,i), InitialGuess);
  for j=1:119
      if fo (j) == 0
          Temp(j) = NaN;
      end
  end
  kj=find(~isnan(Temp(:)),1,'first');
  InitialGuess(1,i)=b(kj,i);
end

and then test it by checking that A=size(unique(InitialGuess),2) is equal to 42. So that's why I broke down my problem to just try to figure it out how to help the solver test only feasible solutions. I hope this makes sense. Thank you.

Martha

Answer 1

[Walter Roberson]

"https://www.mathworks.com/matlabcentral/answers/413504-matlab-continues-to-run-and-wont-stop-is-my-solution-to-complicated#comment_596384"

Use integer constraints and one variable for each of the 42 columns, with lower bound 1 and with upper bound the number of used items in that column. Then in your objective function, use the indicator variable to look up the value to be used for calculation purposes.

This approach will not fit well with linear constraints, and unfortunately if you do use integer constraints then you are not permitted to use nonlinear constraints. So to get this all to work you might have to not tell ga() that you have integer constraints and instead you would use a custom initialization and custom mutation and custom crossover function that "just happens" to respect the integer constraint.

ga() is not able to directly handle discrete values that do not happen to be adjacent integers; any time you have a lookup table like yours, you need to switch to indicator variables that are indices.