what is the function that the same as perms however can used n more than 10?

when i build a coding i used n less than 10, i used perms function.. then when get the correct coding the i test the coding in various size of n, which is n more than 10, however the length for perm is less than 10. what is the same function as perm, but can used for n more than 10?

Answer 1

[OCDER]

I think you need to make your own function of perms, but one that only returns 1 of many permutations at a time. When you past n = 10, you'll run out of memory fast.

        3.5 GB   n = 11
       46.0 GB   n = 12
      647.6 GB   n = 13
     9764.0 GB   n = 14

One suggestion is to make a classdef object that track the ith permutation and will continuously return the the next permutation. But read this link as your attempt to compute permutations for n >> 11 gets fairly impossible...

https://www.mathworks.com/matlabcentral/answers/312609-how-to-get-all-permutation-of-a-large-vector

[sharifah shuthairah syed abdullah]

its possible to solve the problem using matlab right? this is the coding..

     f=[  0  1  2  2  3  4  4  5  3  5  6  7  8  9  7  8;
     1  0  1  1  2  3  3  4  2  4  5  6  7  8  6  7;
     2  1  0  2  1  2  2  3  1  3  4  5  6  7  5  6;
     2  1  2  0  1  2  2  3  3  3  4  5  6  7  5  6;
     3  2  1  1  0  1  1  2  2  2  3  4  5  6  4  5;
     4  3  2  2  1  0  2  3  3  1  2  3  4  5  3  4;
     4  3  2  2  1  2  0  1  3  1  2  3  4  5  3  4;
     5  4  3  3  2  3  1  0  4  2  1  2  3  4  2  3;
     3  2  1  3  2  3  3  4  0  4  5  6  7  8  6  7;
     5  4  3  3  2  1  1  2  4  0  1  2  3  4  2  3;
     6  5  4  4  3  2  2  1  5  1  0  1  2  3  1  2;
     7  6  5  5  4  3  3  2  6  2  1  0  1  2  2  3;
     8  7  6  6  5  4  4  3  7  3  2  1  0  1  1  2;
     9  8  7  7  6  5  5  4  8  4  3  2  1  0  2  1;
     7  6  5  5  4  3  3  2  6  2  1  2  1  2  0  1;
     8  7  6  6  5  4  4  3  7  3  2  3  2  1  1  0 ];

     d=[
     0  3  4  6  8  5  6  6  5  1  4  6  1  5  4  5;
     3  0  6  3  7  9  9  2  2  7  4  7  9  6  3  2;
     4  6  0  2  6  4  4  4  2  6  3  6  5  6  2  6;
     6  3  2  0  5  5  3  3  9  4  3  6  3  4  7  8;
     8  7  6  5  0  4  3  4  5  7  6  7  7  3  3  3;
     5  9  4  5  4  0  8  5  5  5  7  5  1  8  5  4;
     6  9  4  3  3  8  0  6  8  4  6  7  1  8  5  6;
     6  2  4  3  4  5  6  0  1  5  5  3  7  5  9  4;
     5  2  2  9  5  5  8  1  0  4  5  2  4  5  4  5;
     1  7  6  4  7  5  4  5  4  0  7  7  5  6  5  5;
     4  4  3  3  6  7  6  5  5  7  0  9  6  5  1  8;
     6  7  6  6  7  5  7  3  2  7  9  0  6  5  4  5;
     1  9  5  3  7  1  1  7  4  5  6  6  0  5  7  4;
     5  6  6  4  3  8  8  5  5  6  5  5  5  0  5  3;
     4  3  2  7  3  5  5  9  4  5  1  4  7  5  0  8;
     5  2  6  8  3  4  6  4  5  5  8  5  4  3  8  0];

     [r,c]=size(f); 

      max_i= r;
      max_j =r;
      max_k= r;
      max_n= r;

      A=zeros(r,r);m=0;
      ID=perms([1:r]);
      x=zeros(r,r); 
      n=length(ID);
      for i=1:n
        for j=1:r
        x1=ID(i,:);
        x(j,x1(j))=1;
        B(i).mat=x;  %store permutationof binary value, 0,1
        end
       x=zeros(r,r);  
      end

     for no=1:length(B)
        m=0;z=0;xa=B(no).mat;
     for i=1:max_i
        for j=1:max_j
          for k=1:max_k

            for n=1:max_n

                 z= z+ f(i,k).*d(j,n).*xa(i,j).*xa(k,n);
%                 m=m+1;
%                F(m)=z;
            end
           % end
        end
    end
end
no;
F(no,:)=[no z];
end
zmin=min(F(:,2));
ii=find(F(:,2)==zmin); 
% xbin = facility location for minimun z 
xbin= B(ii).mat
z_minimum = zmin

[Guillaume]

To store all ~2e13 permutations of 16 numbers, you'll need 2400 terabytes of memory. Have you got that much memory? If you were to generate the permutations at a rate of 1 per microsecond, it would still take you more than half a year to generate them all.

What you want to do is simply not possible. You'll have to come up with a different algorithm that does not involve generating all the permutations.

[Stephen23]

That fact that some mathematical problems are not solvable using real computers in a practical length of time is a cause for finding other ways to solve the problem. We might be able to help you with that.

[sharifah shuthairah syed abdullah]

Matlab can solve the large data right? So I cannot used the coding above and build another one, to solve the n more than 10? Im confuse...

[Stephen23]

"Matlab can solve the large data right?"

Your problem requires far more memory than any desktop PC in the world has. Nor could any computer generate all of those permutations in a reasonable length of time. These are not restrictions caused by MATLAB, but simply by the problem that you are trying to solve.

It is easy with just one or two lines of code to define a problem that requires more memory than the known universe has particles, or that require more iterations than could be performed in a hundred years on one computer. The fact that MATLAB cannot solve such problems is not a problem of MATLAB: just because something is theoretically solvable does not means that it can be solved in a practical amount of time on real computers. You need to find other ways to solve your problem.

[OCDER]

Hi sharifah, instead of asking us how to solve the permutation problem, perhaps tell us what you're trying to do. Why do you need to get permutations for n > 15. etc. Are you building some sort of encryption/decryption algorithm, or brute force method? Some problems are so challenging that it takes super computers and a lot of time solve - example, finding the largest prime number took 39 days even with 360000 CPUs (that's a lot!).

https://www.sciencedaily.com/releases/2013/02/130213225424.htm

So the answer to " Matlab can solve the large data right? " is " yes, BUT not within a reasonable amount of time while using an average quad-core cpu with 32GB RAM ", as we all have explained.

[sharifah shuthairah syed abdullah]

hai OCTER, i know that solving this will cause me a lot of time, this is because i have been using LINGO before this and i can solve up until n = 15 in 4 days... i also know that in 1999, Nystrom produced a solution on same problem for n = 36 by using an exact method for 200 working days. but that a long time ago... however i cannot proceed with LINGO because i cannot get any help for the coding.. that why i switch to MATLAB with hope at lest it can be solve until n = 16.. i want to solve this QUADRATIC ASSIGNMENT PROBLEM USING BRANCH AND BOUND METHOD by coding in MATLAB.. why i used permutation because its solve the solution as i wanted... however i cannot solve more than n = 10.. thats why i ask about it in here.. im sorry for make everyone mad..

[Dennis]

Are your input matrices always symmetric? In that case you can discard half of your permutations, because [1 2 3] and [3 2 1] will result in same z value. You might aswell decrease computation time if you only calculate non-zero iterations of your loop. I think you are performing r^4 calculations but only r*2 of them are not zero.

[sharifah shuthairah syed abdullah]

yes, my input matrix are all symmetric..if i only used half i need to declare it right?

[OCDER]

Hi Sharifah, no one is mad here - we're just confused as to why you need to do this massive calculation. So, looks like you are indeed solving a very tough NP-hard problem.

https://en.wikipedia.org/wiki/Quadratic_assignment_problem

The issue will be making the permutations without using 100% RAM - see the file exchange links that @Stephen posted in his answer. This solves the memory issue, but not the CPU issue. It'll be slow, unless you can figure out a way to break this up into blocks of independent jobs and use Parallel Computing Toolbox to cut times roughly by the number of cores you have. You should also consider making MEX/C++ files to speed up simple and highly repetitive calculations. GPU processing could also help. This is quite an advanced problem so there isn't really a simple solution we can provide.

[Walter Roberson]

https://www.mathworks.com/matlabcentral/fileexchange/53110-quadratic-assignment-problem--qap--using-ga--pso-and-fa

https://github.com/cshen/quadratic-assignment-problem

[sharifah shuthairah syed abdullah]

i know this is an NP hard problem i have been doing this amlost 4 years now..i used randperm but it didnt satisfied my need....i also will also consider making MEX/C++ files after this...this stage is about finding optimal solution using branch n bound..i know need a lot of time for that...later i will use GA.. thank you everyone for answering my question..thank you so much

Answer 2

[Stephen23]

One option would be to use a permutation generator, which does not store all permutations in memory:

https://www.mathworks.com/matlabcentral/fileexchange/57429-nextperm-v--k-

https://www.mathworks.com/matlabcentral/fileexchange/44887-nthperm

etc.

I leave it up to the reader to decide if running through all permutations is tractable or not.

[sharifah shuthairah syed abdullah]

thank you so much