Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
does Matlab have any such function

Subject: does Matlab have any such function

From: Will

Date: 3 Feb, 2009 02:38:09

Message: 1 of 29

I need to take a vector of the numbers
v={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15} and go through all 15 factorial permutations of these numbers. With each of these permutations I need to do a calculation on a vector that contains 25,000 numerical entries.
Does anyone know if Matlab has a convenient function for generating, one step at a time, all of the permutations of v?
Also, does anyone know if this going to take a really long time to complete?
Thanks.

Subject: does Matlab have any such function

From: Matt Fig

Date: 3 Feb, 2009 02:54:02

Message: 2 of 29

Matlab does not have such a function. I wrote one, found at the link below, but it doesn't generate the permutations one at a time. There is no way you can use it to get them all either, unless you have astronomical storage. Maybe you could modify it somehow to give the results a few at a time.

http://www.mathworks.com/matlabcentral/fileexchange/11462

Good luck.





MBEv\Lc"L\QM\|KD>>IKj\H>R6?EFLEJB*?>>\Q>L\BVIFcL\@BJ@RL>SQ\

Subject: does Matlab have any such function

From: Will

Date: 3 Feb, 2009 03:32:11

Message: 3 of 29

Hi. Thanks very much. Actually I am new to Matlab. I looked at your code and in the example it seems to return all the permutations in matrix form. Does that mean that if I ran MAT = npermutek([1:15],15) I would get 15! rows?

% Example:
% MAT = npermutek([2 4 5],2)
%
% MAT =
%
% 2 2
% 2 4
% 2 5
% 4 2
% 4 4
% 4 5
% 5 2
% 5 4
% 5 5

Subject: does Matlab have any such function

From: Roger Stafford

Date: 3 Feb, 2009 03:50:03

Message: 4 of 29

Will <william108@gmail.com> wrote in message <2115737.1233628719570.JavaMail.jakarta@nitrogen.mathforum.org>...
> I need to take a vector of the numbers
> v={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15} and go through all 15 factorial permutations of these numbers. With each of these permutations I need to do a calculation on a vector that contains 25,000 numerical entries.
> Does anyone know if Matlab has a convenient function for generating, one step at a time, all of the permutations of v?
> Also, does anyone know if this going to take a really long time to complete?
> Thanks.

  There is also Mathworks' own 'perms' which generates all permutations, but like Matt's function, they are produced all in one array which would be a massive 1.3e12 x 15 in size. If you have a computation to do involving a vector with 25000 entries for each row, I think one can predict a very, very long computation process!

  I think your best bet would be to try to do this computation, whatever it is, on a different basis, one that doesn't require tediously working with each separate permutation. You might be surprised at the shortcuts that could be found in such problems. Why don't you try explaining what it is you propose to do with each row to see if such a simplification is possible?

Roger Stafford

Subject: does Matlab have any such function

From: Matt Fig

Date: 3 Feb, 2009 03:56:02

Message: 5 of 29

Will <william108@gmail.com> wrote in message

No, I misread your message. What you want is a subset of what npermutek([1:15],15) would produce. For example, if you looked at the output of

c = npermutek([1:3],3);
c([6,16,7],:)



You want something more like

ranperm(15)

done over and over with no repeats, correct?






hXNJNVXY.]QJ6QJb#J)KWX]RQJNhUKUYW]JBhL^hh^hXVThoR_XLNohXPvJ

Subject: does Matlab have any such function

From: Matt Fig

Date: 3 Feb, 2009 04:01:01

Message: 6 of 29

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message
> Roger Stafford

perms of course! Thanks Roger, I was leading the poor guy astray. Sorry to the OP.




c?yf\i_4fa]ypygh!b[]yy(bj[[_y_onijniGs[[nSo\cbiih!_[y[g:eyi

Subject: does Matlab have any such function

From: Will

Date: 3 Feb, 2009 05:00:48

Message: 7 of 29

I have a fixed row of data which I call CL and another row of data which I call Var. Each row has 25,000 entries.
And each row has only the values 1 through 15 as entries.

I want to see how many times these two rows are the same. So I compare them and count up each time they are not the same.

But, the CL row has an arbitrayness to it. What I mean is, that I don't care what the particular entries are in the CL row but only the "pattern". What I mean by that is if
the first entry
the eighth entry
the twentythird entry
and so on
are all 1

and if
the second entry
the tenth entry
the thirtieth entry
(and so on)
are all 5

then I don't care if they are renamed so that
the first entry,
the eighth entry
the twentythird entry
and so on
are all 11


and if
the second entry
the tenth entry
the thirtieth entry
(and so on)
are all 7

What I am interested in is what I call the "best match" for these two rows CL and Var.
So I can take
v={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}
and for the first permutation
every time there is a 1 in CL assign it 1 from v and
every time there is a 2 in CL assign it 2 from v and so on.
This is just the identity mapping.
But the next time, I would permute v -suppose the permuted v is v={2,1,3,4,5,6,7,8,9,10,11,12,13,14,15}.
Now,
every time there is a 1 in CL assign it 2 from v and
every time there is a 2 in CL assign it 1 from v and so on.

Then I would do the checking of the difference as described when I said above "So I compare them and count up each time they are not the same."

So I think I need some way of creating permutations of v one at a time.
Thanks.

Subject: does Matlab have any such function

From: Matt Fig

Date: 3 Feb, 2009 07:31:04

Message: 8 of 29

I haven't looked over your code, but if you *really* do need to get these permutations one at a time you could do something like this. I have shown a way to get the permutations for [1 2 3 4]. The corresponding code to get them for 1:15 will be ugly, but it will mostly involve a lot of copy/paste activity, it won't be too hard. Good luck.



for ii = 1:4
    for jj = 1:4
        if ii~=jj
            for kk = 1:4
                if ii~=kk && jj~=kk
                    for mm = 1:4
                        if ii~=mm && jj~=mm && kk~=mm
                            perm = [ii,jj,kk,mm];
                            % Here is where you put the code where you need the
                            % perm vector one at a time.
                        end
                    end
                end
            end
        end
    end
end






<<8L.FL&<5<:.L.Z.L=f0.CAA29.4L9;0S<l.AyqL/6:2=<52BB;S/L6L25

Subject: does Matlab have any such function

From: Roger Stafford

Date: 3 Feb, 2009 08:44:02

Message: 9 of 29

Will <william108@gmail.com> wrote in message <24898439.1233637284374.JavaMail.jakarta@nitrogen.mathforum.org>...
> I have a fixed row of data which I call CL and another row of data which I call Var. Each row has 25,000 entries.
> And each row has only the values 1 through 15 as entries.
>
> I want to see how many times these two rows are the same. So I compare them and count up each time they are not the same.
> .......
> But, the CL row has an arbitrayness to it.>
> What I am interested in is what I call the "best match" for these two rows CL and Var.
> So I can take
> v={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}
> and for the first permutation
> every time there is a 1 in CL assign it 1 from v and
> every time there is a 2 in CL assign it 2 from v and so on.
> This is just the identity mapping.
> But the next time, I would permute v -suppose the permuted v is v={2,1,3,4,5,6,7,8,9,10,11,12,13,14,15}.
> Now,
> every time there is a 1 in CL assign it 2 from v and
> every time there is a 2 in CL assign it 1 from v and so on.
>
> Then I would do the checking of the difference as described when I said above "So I compare them and count up each time they are not the same."
> .......

  One idea occurs to me that would avoid having to go through 25000 comparisons between all 'CL' and 'Var' elements for each permutation to be tested. If you haven't already thought of it yourself, Will, you might be interested in the idea.

  You are trying to find the best match in what you call "patterns" in the two vectors. With a given assignment of values in 'CL' and 'Var', there are 15*15 = 225 possible pairings of values between the two vectors throughout their 25000 elements and each particular pairing occurs a certain number of times. The sum of these counts for all pairings must equal 25000. Suppose we initially construct a 15 x 15 matrix called X which contains all these counts, with each X(i,j) being the number of cases in which corresponding CL, Var pairs are i and j respectively. Assuming 'CL' and 'Var' are column vectors, you can compute such an X this way:

 X = accumarray([CL,Var],1,[15,15]);

Compared with the computing task involved in generating 15 factorial permutations, this task will seem almost instantaneous.

  Now, provided you have found some means of generating all the permutations one-at-a-time (something I might ponder later,) then for each permutation row vector, p, of 1:15, you can simply do the following one-liner within the appropriate for-loop

 c = sum(X(p+(0:15:210)));

to find the number of matches you would get using p as a permutation of the values in CL. That should certainly beat anything that has to scan through 25000 elements of 'CL' and 'Var'. It has only fifteen X values to sum.

  I can think of variations on this theme of a heuristic sort which would not require going through all possible permutations. What you want to do is find a 15-element path through the X matrix that doesn't visit any row or column more than once and which has the maximum possible sum. A good start on this might be to first select the maximum count anywhere in X. Next find the maximum value in X in which the row and column of that first count have been eliminated. Keep this up until a path is fully selected. This might not be the best match but, conceivably, repeated subsequent switchings between pairs of columns whenever that increases the count would eventually get you to the true maximum path - or perhaps it wouldn't - I am not sure.

  However, at this point my brain is getting increasingly torpid and I would prefer to put off any further thought until later. I hope the above idea might be of some assistance to you. It seems to me that the matrix X above is fundamental to the solution of your problem because it contains all the necessary information needed to find the best match, and does so using only 225 numbers rather than 50000 numbers.

Roger Stafford

Subject: does Matlab have any such function

From: Eric

Date: 3 Feb, 2009 09:28:02

Message: 10 of 29

Will <william108@gmail.com> wrote in message <2115737.1233628719570.JavaMail.jakarta@nitrogen.mathforum.org>...
> I need to take a vector of the numbers
> v={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15} and go through all 15 factorial permutations of these numbers. With each of these permutations I need to do a calculation on a vector that contains 25,000 numerical entries.
> Does anyone know if Matlab has a convenient function for generating, one step at a time, all of the permutations of v?
> Also, does anyone know if this going to take a really long time to complete?
> Thanks.

Hi!

Perhaps the function getNextPermutation showed below might be usefull for you.

vNElements is a vector of arbitrary length. Every element of this vector gives the number of elements to permute for this "position".

The first permutation is created by calling the function with vidCur=[]:
   cur = getNextPermutation([], [15 15]')
   -> cur = [1 1]'
To obtain the next permutation, just call the function with the current permutation:
   cur = getNextPermutation(cur, [15 15]')
   -> cur = [1 2]'
   ...
If the vidCur is the last possible permutation, then getNextPermutation returns an empty matrix:
   cur = getNextPermutation([15 15], [15 15]')
   -> cur = []

You can use the permutations created by getNextPermutation as indices of some data vectors, cell-arrays, etc.

##########################################
function vidNext = getNextPermutation(vidCur, vNElements)

N = length(vNElements);

if isempty(vidCur)
vidNext = ones(N, 1);
else
bFinished = false;
i = N+1;
while ~bFinished
i = i - 1;
if (vidCur(i) < vNElements(i))
vidCur(i) = vidCur(i) + 1;
vidNext = vidCur;
bFinished = true;
elseif (i == 1)
vidNext = [];
bFinished = true;
else
vidCur(i) = 1;
end
end % while ~ bFinshed
end

end % function getNextPermutation
#######################################

Subject: does Matlab have any such function

From: Roger Stafford

Date: 3 Feb, 2009 09:37:01

Message: 11 of 29

"Matt Fig" <spamanon@yahoo.com> wrote in message <gm8rro$o94$1@fred.mathworks.com>...
> I haven't looked over your code, but if you *really* do need to get these permutations one at a time you could do something like this. I have shown a way to get the permutations for [1 2 3 4]. The corresponding code to get them for 1:15 will be ugly, but it will mostly involve a lot of copy/paste activity, it won't be too hard. Good luck.
>
> for ii = 1:4
> for jj = 1:4
> if ii~=jj
> for kk = 1:4
> if ii~=kk && jj~=kk
> for mm = 1:4
> if ii~=mm && jj~=mm && kk~=mm
> perm = [ii,jj,kk,mm];
> % Here is where you put the code where you need the
> % perm vector one at a time.
> end
> end
> end
> end
> end
> end
> end

  Matt, you might modify that for-loop method by just having eight nested for-loops like the above which generate an eight element vector [i1,i2,..,i8] with values chosen out of 1:15. At that point you could take time to determine a single vector of the seven values in 1:15 which were not used in [i1,i2,..,i8], call it q = [i9,i10,...,i15]. Then, referring to a precomputed 5040 x 7 array from perms(1:7), you could successively apply q to each row of this array one-at-a-time to generate the 5040 different seven-element permutations from q each of which would then be concatenated with the [i1,i2,...,i8] above to get your 'perm' value.

  This way you could avoid some of the overhead involved in fifteen nested for-loops and their associated increasingly lengthy inequality testing at the cost of only a 35280 element array kept in memory.

  However, the total number of permutations here is enormous, over a trillion, and I think the computation time will eventually rule out such a method using all 15! permutations no matter how this is done. I think Will needs to try something else.

Roger Stafford

Subject: does Matlab have any such function

From: John D'Errico

Date: 3 Feb, 2009 10:00:05

Message: 12 of 29

"Eric" <noemail@noemail.com> wrote in message <gm92n2$r2h$1@fred.mathworks.com>...
> Will <william108@gmail.com> wrote in message <2115737.1233628719570.JavaMail.jakarta@nitrogen.mathforum.org>...
> > I need to take a vector of the numbers
> > v={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15} and go through all 15 factorial permutations of these numbers. With each of these permutations I need to do a calculation on a vector that contains 25,000 numerical entries.
> > Does anyone know if Matlab has a convenient function for generating, one step at a time, all of the permutations of v?
> > Also, does anyone know if this going to take a really long time to complete?
> > Thanks.
>
> Hi!
>
> Perhaps the function getNextPermutation showed below might be usefull for you.

It won't be terribly helpful here, since the total
number of permutations is simply too large.

factorial(15)
ans =
   1.3077e+12

Nobody seems to believe this.

Lets assume that this "operation" with 25000
numbers on each such permutation takes one
second for each permutation.

60*60*24*365.25
ans =
    31557600

Since there are roughly 31000000 seconds in
a year, this will still require

factorial(15)/31000000
ans =
        42183

a total of roughly 42183 years to finish this
computation. Even if you can do it much more
quickly, this will still take a long time. Suppose
the computation is nothing more difficult than
taking the sum of 25000 numbers. On my CPU,
even that takes some time.

p = 1:25000;
>> timeit(@() sum(p))
ans =
   0.00044416

It will still take

42183*.00044416
ans =
       18.736

a total of 18.7 years to finish these operations.
Doing them one at a time or not does not matter.

I'd strongly suggest reformulating the problem.

For example, suppose I just wanted to sum the
numbers 1:1e12. I could set up a for loop,
foolishly applying the power of a fast computer
to the problem. Worse, next month, some other
damn fool will decide to sum the numbers up to
1e15, just because they can, and because they
have an even faster computer of their own.

Far better would be to use the appropriate formula
for these sums.

John

Subject: does Matlab have any such function

From: Will

Date: 3 Feb, 2009 10:09:02

Message: 13 of 29

Hello. Thank you for your help and your deep thought! I am trying to understand what you mean. You suggest forming the matrix X which will be a 15x15 square matrix. Lets say that the entries of X are denoted by x(i,j).
For example x(7,4) would be equal to the number of times a 7 in the CL vector corresponded to a 4 in the Var vector (or visa versa) if we were to line them up one on top of the other. Thus summing up all 225 entries would give 25000. You have also said that there is a convenient function in Matlab that will form this array: accumarray[].
This seems very convenient for one part of my calculation. The diagonal of this array is the number of times the two vectors agree. That is the part of my calculation where I need to calculate Er. So
Er=25000-trace(X).
But I don't think this solves the permutation part of the problem. The permutation part has to do with the fact that the naming of the values in CL are arbitrary.
For example, if the first few entries of CL were
CL={3,5,9,3,3,8,3,5,..}
they could just as well be
CL={11,2,6,11,11,4,11,2,...}
(for example the entries in the first, fourth, fifth, and seventh are the same in both of these).
But I want to know the matches between CL and Var. If I use the first CL above, I will get a certain number of matches. But since the names in CL are arbitrary, I have to check how the second CL above matches Var. If it is closer (smaller Er), then that is important. And what I want to do is find the smallest Er among all possible "codings" of CL.
I am sorry if I cannot explain this well. I don't know how to say it better than this.

Subject: does Matlab have any such function

From: Will

Date: 3 Feb, 2009 10:29:57

Message: 14 of 29

18 years is a bit too long. Thank you for that very simple calculation.
I am not sure what you mean by using an appropriate formula for the sums though. It seems like there is not a way to do this the way I want. And I can't think of any approach, like an optimization approach, that would point to where among all the permutation the Er would be least.

Subject: does Matlab have any such function

From: Roger Stafford

Date: 3 Feb, 2009 17:53:02

Message: 15 of 29

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <gm94j4$c7$1@fred.mathworks.com>...
> .......
> It won't be terribly helpful here, since the total
> number of permutations is simply too large.
>
> factorial(15)
> ans =
> 1.3077e+12
>
> Nobody seems to believe this.
>
> Lets assume that this "operation" with 25000
> numbers on each such permutation takes one
> second for each permutation.
> ..........
> It will still take
>
> 42183*.00044416
> ans =
> 18.736
>
> a total of 18.7 years to finish these operations.
> ......
> John

  Hello John. It isn't true that for each permutation it would require an operation on all 25000 pairs of elements. Just read the stuff I wrote above where this can be reduced to working with a 15 x 15 matrix, X. Each permutation would lead to a sum with only 15 terms rather than 25000, so I think you need to reduce that 18 year estimate substantially.

  On the other hand, when you say, "the total number of permutations is simply too large" combined with "Nobody seems to believe this", that isn't entirely accurate either. I quote myself from earlier in this thread, "However, the total number of permutations here is enormous, over a trillion, and I think the computation time will eventually rule out such a method using all 15! permutations no matter how this is done. I think Will needs to try something else."

  Nevertheless, Matt, Eric, and I have cooperated with Will in showing him how one could generate permutations one-at-a-time, in the hopes that he might find a use for the technique but using a smaller number of permutations.

  I do hardily agree with you that this problem as it stands requires a different approach if it is to be reasonably solved. No matter how quickly each permutation is dealt with, one trillion permutations is too many to handle one-at-a-time. That is why I suggested the possibility of a heuristic approach using the X matrix in a different manner than the brute force one of using all permutations. I stated "What you want to do is find a 15-element path through the X matrix that doesn't visit any row or column more than once and which has the maximum possible sum." This cries out for some clever approach, heuristic or otherwise, and probably better than the one I mentioned.

Roger Stafford

Subject: does Matlab have any such function

From: John D'Errico

Date: 3 Feb, 2009 18:05:19

Message: 16 of 29

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gma09u$6l9$1@fred.mathworks.com>...
> "John D'Errico" <woodchips@rochester.rr.com> wrote in message <gm94j4$c7$1@fred.mathworks.com>...
> > .......
> > It won't be terribly helpful here, since the total
> > number of permutations is simply too large.
> >
> > factorial(15)
> > ans =
> > 1.3077e+12
> >
> > Nobody seems to believe this.
> >
> > Lets assume that this "operation" with 25000
> > numbers on each such permutation takes one
> > second for each permutation.
> > ..........
> > It will still take
> >
> > 42183*.00044416
> > ans =
> > 18.736
> >
> > a total of 18.7 years to finish these operations.
> > ......
> > John
>
> Hello John. It isn't true that for each permutation it would require an operation on all 25000 pairs of elements. Just read the stuff I wrote above where this can be reduced to working with a 15 x 15 matrix, X. Each permutation would lead to a sum with only 15 terms rather than 25000, so I think you need to reduce that 18 year estimate substantially.
>
> On the other hand, when you say, "the total number of permutations is simply too large" combined with "Nobody seems to believe this", that isn't entirely accurate either. I quote myself from earlier in this thread, "However, the total number of permutations here is enormous, over a trillion, and I think the computation time will eventually rule out such a method using all 15! permutations no matter how this is done. I think Will needs to try something else."
>
> Nevertheless, Matt, Eric, and I have cooperated with Will in showing him how one could generate permutations one-at-a-time, in the hopes that he might find a use for the technique but using a smaller number of permutations.
>
> I do hardily agree with you that this problem as it stands requires a different approach if it is to be reasonably solved. No matter how quickly each permutation is dealt with, one trillion permutations is too many to handle one-at-a-time. That is why I suggested the possibility of a heuristic approach using the X matrix in a different manner than the brute force one of using all permutations. I stated "What you want to do is find a 15-element path through the X matrix that doesn't visit any row or column more than once and which has the maximum possible sum." This cries out for some clever approach, heuristic or otherwise, and probably better than the one I mentioned.
>
> Roger Stafford

Hi Roger,

My point in my response was to convince the OP
to look for a seriously different way to approach the
problem. I do know that you do understand the
issues, so "nobody" was an incorrect statement.

Too often people rely too much on the computational
horsepower available to them. They just create large
problems and throw a computer at the problem with
no thought at all about what they are doing. Yes,
it is easy, but it is laziness to the utmost. Why
bother thinking about your problem? I'll admit that
all of us probably do this at times.

John

Subject: does Matlab have any such function

From: Roger Stafford

Date: 3 Feb, 2009 18:14:02

Message: 17 of 29

Will <william108@gmail.com> wrote in message <17296950.1233655772681.JavaMail.jakarta@nitrogen.mathforum.org>...
> Hello. Thank you for your help and your deep thought! I am trying to understand what you mean. You suggest forming the matrix X which will be a 15x15 square matrix. Lets say that the entries of X are denoted by x(i,j).
> For example x(7,4) would be equal to the number of times a 7 in the CL vector corresponded to a 4 in the Var vector (or visa versa) if we were to line them up one on top of the other. Thus summing up all 225 entries would give 25000. You have also said that there is a convenient function in Matlab that will form this array: accumarray[].
> This seems very convenient for one part of my calculation. The diagonal of this array is the number of times the two vectors agree. That is the part of my calculation where I need to calculate Er. So
> Er=25000-trace(X).
> But I don't think this solves the permutation part of the problem. The permutation part has to do with the fact that the naming of the values in CL are arbitrary.
> For example, if the first few entries of CL were
> CL={3,5,9,3,3,8,3,5,..}
> they could just as well be
> CL={11,2,6,11,11,4,11,2,...}
> (for example the entries in the first, fourth, fifth, and seventh are the same in both of these).
> But I want to know the matches between CL and Var. If I use the first CL above, I will get a certain number of matches. But since the names in CL are arbitrary, I have to check how the second CL above matches Var. If it is closer (smaller Er), then that is important. And what I want to do is find the smallest Er among all possible "codings" of CL.
> I am sorry if I cannot explain this well. I don't know how to say it better than this.

  Will, I don't think you have entirely understood what I had in mind with this X matrix. To start with, when you said, "For example x(7,4) would be equal to the number of times a 7 in the CL vector corresponded to a 4 in the Var vector (or visa versa)", the "visa versa" isn't correct. X(4,7) need not be equal to X(7,4). They are different counts.

  When you said, "The diagonal of this array is the number of times the two vectors agree", that would be agreement before any permutation is performed on the elements of CL. Since you have asserted that the values in CL are subject to an arbitrary permutation, the values along the diagonal of X have no particular significance. Only if you happened to use the identity permutation in CL would the diagonal mean anything.

  Where you say "But I don't think this solves the permutation part of the problem. The permutation part has to do with the fact that the naming of the values in CL are arbitrary" this totally overlooks the fact that the permutation p in defining a path through the X matrix is investigating each possible reassignment of the values in CL. That is what the whole problem is about! You should note that the 'Er' you describe is exactly 25000-c where c = sum(X(p+(0:15:210))), and this is what is to be maximized. The 'p' you see here refers to one of the huge number of possible permutations of values in CL.

Roger Stafford

Subject: does Matlab have any such function

From: Roger Stafford

Date: 3 Feb, 2009 19:07:02

Message: 18 of 29

"Matt Fig" <spamanon@yahoo.com> wrote in message <gm8rro$o94$1@fred.mathworks.com>...
> I haven't looked over your code, but if you *really* do need to get these permutations one at a time you could do something like this. I have shown a way to get the permutations for [1 2 3 4]. The corresponding code to get them for 1:15 will be ugly, but it will mostly involve a lot of copy/paste activity, it won't be too hard. Good luck.
>
> for ii = 1:4
> for jj = 1:4
> if ii~=jj
> for kk = 1:4
> if ii~=kk && jj~=kk
> for mm = 1:4
> if ii~=mm && jj~=mm && kk~=mm
> perm = [ii,jj,kk,mm];
> % Here is where you put the code where you need the
> % perm vector one at a time.
> end
> end
> end
> end
> end
> end
> end
------------
  Matt, here is another way of generating permutations one-at-a-time in nested for-loops that doesn't require any rejections - no conditional if's. It also doesn't have to deal with inequalities. The example below is for permutations of 1:n with n = 6 but it is easily generalized to greater values of n. Pardon the somewhat user-unfriendly lack of insets in the code lines but this makes it easier to see how it is to be generalized. Note that for reasonably large n, the time spent building the fixed arrays r1, r2, ..., r_n-1 will be minute compared with the time spent in the nested for-loops.

r1 = flipud(reshape(repmat(1:6,5,1),6,5));
r2 = flipud(reshape(repmat(1:5,4,1),5,4));
r3 = flipud(reshape(repmat(1:4,3,1),4,3));
r4 = flipud(reshape(repmat(1:3,2,1),3,2));
r5 = flipud(reshape(repmat(1:2,1,1),2,1));
q1 = 1:6;
for j1 = 1:6, i1 = q1(j1); q2 = q1(r1(j1,:));
for j2 = 1:5, i2 = q2(j2); q3 = q2(r2(j2,:));
for j3 = 1:4, i3 = q3(j3); q4 = q3(r3(j3,:));
for j4 = 1:3, i4 = q4(j4); q5 = q4(r4(j4,:));
for j5 = 1:2, i5 = q5(j5); i6 = q5(r5(j5,:));
  p = [i1,i2,i3,i4,i5,i6];
  % <-- Use permutation p here for whatever is needed
end
end
end
end
end

Roger Stafford

Subject: does Matlab have any such function

From: Will

Date: 4 Feb, 2009 00:54:35

Message: 19 of 29

Hello Roger,
Let me think about your reply for a few hours. One thing though is that when I said visa versa I should have been more clear. I did not mean the x(4,7) = x(7,4). I meant that we could form the matrix by putting CL across the top or by putting Var across the top and the other down the side. Sorry for the ambiguity.

Subject: does Matlab have any such function

From: Roger Stafford

Date: 4 Feb, 2009 01:47:02

Message: 20 of 29

Will <william108@gmail.com> wrote in message <29474463.1233708906150.JavaMail.jakarta@nitrogen.mathforum.org>...
> Hello Roger,
> Let me think about your reply for a few hours. One thing though is that when I said visa versa I should have been more clear. I did not mean the x(4,7) = x(7,4). I meant that we could form the matrix by putting CL across the top or by putting Var across the top and the other down the side. Sorry for the ambiguity.
-------------
  Perhaps I can speed up things for you with a simple example. Cut down from 15 to 3 and from 25000 to 30 and let

 CL = [2 3 2 1 2 2 1 2 3 3 3 2 1 1 2 3 3 2 2 2 2 2 3 2 3 2 2 2 1 2];
 Var = [2 3 1 3 2 1 2 2 2 3 3 1 3 1 2 2 3 1 3 3 1 3 2 2 3 1 2 3 2 1];

You can count these cases by hand, as well as try out the 'accumarray' function, and either way you should get:

 X = 1 2 2
      7 6 4
      0 3 5

There are six different possible permutation vectors:

 p = [1 2 3]
 p = [1 3 2]
 p = [2 1 3]
 p = [2 3 1]
 p = [3 1 2]
 p = [3 2 1]

When you do the c = sum(X(p+(0:15:210))); line you should get this:

 c = 1 + 6 + 5 = 12
 c = 1 + 3 + 4 = 8
 c = 7 + 2 + 5 = 14
 c = 7 + 3 + 2 = 12
 c = 0 + 2 + 4 = 6
 c = 0 + 6 + 2 = 8

for the six successive p permutations. The third one is the maximum, where the match is greatest. So applying this "best" p to the original CL to permute its values gives:

C2 = p(CL) =
       1 3 1 2 1 1 2 1 3 3 3 1 2 2 1 3 3 1 1 1 1 1 3 1 3 1 1 1 2 1
Var = [2 3 1 3 2 1 2 2 2 3 3 1 3 1 2 2 3 1 3 3 1 3 2 2 3 1 2 3 2 1];

You can count the matches here and verify that the count is indeed 14.

  As you can perhaps see from this, it would be a waste of time to have to run through all 25000 vector entries in the actual CL and Var when you can accomplish the same thing using the much smaller X properly.

  Of course you still face the problem of there being over a trillion possible permutations for your problem, and even with the single line

 c = sum(X(p+(0:15:210)));

to do each time, it will take a very, very long time to compute. As John indicates, you should try for some other method, presumably using X, to find the "best" or at least a good match.

Roger Stafford

Subject: does Matlab have any such function

From: Will

Date: 4 Feb, 2009 02:18:45

Message: 21 of 29

First let me reply on what you wrote in an earlier post.
You said "When you said, "The diagonal of this array is the number of times the two vectors agree", that would be agreement before any permutation is performed on the elements of CL. Since you have asserted that the values in CL are subject to an arbitrary permutation, the values along the diagonal of X have no particular significance. Only if you happened to use the identity permutation in CL would the diagonal mean anything."

But the diagonal here is relevant to the first permutation of CL. Then I thought what you meant was do the next permutation of CL and form X again and then the diagonal would be relevant to that permutation. Isn't this correct?

Subject: does Matlab have any such function

From: Will

Date: 4 Feb, 2009 02:23:40

Message: 22 of 29

I am now trying to understand what you meant by:
"Now, provided you have found some means of generating all the permutations one-at-a-time (something I might ponder later,) then for each permutation row vector, p, of 1:15, you can simply do the following one-liner within the appropriate for-loop

c = sum(X(p+(0:15:210)));

to find the number of matches you would get using p as a permutation of the values in CL. That should certainly beat anything that has to scan through 25000 elements of 'CL' and 'Var'. It has only fifteen X values to sum."

In particular I am trying to figure out
c = sum(X(p+(0:15:210)));
Is this matlab notation. I am not very familiar with matlab. Sorry

Subject: does Matlab have any such function

From: Matt Fig

Date: 4 Feb, 2009 02:50:03

Message: 23 of 29

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message

> Matt, here is another way of generating permutations one-at-a-time in nested for-loops that doesn't require any rejections - no conditional if's.


Very nice Roger! That is the way I started to go last night, but I was too tired and wanted to give Will something to work with: at least the idea that it could be done.
I modified the version I wrote last night to calculate perm(1:6), and surprise surprise, your version is nearly twice as fast, proving that wise indexing is faster than conditional elimination.

Thanks.

Subject: does Matlab have any such function

From: Will

Date: 4 Feb, 2009 03:13:33

Message: 24 of 29

As I understand it x(i,j) is the number of times the i in CL occurs in the same place as j in Var (if CL and Var were lined up on top of each other).
So x(i,i) is the number of times i in CL is in the same place as i in Var and so it is the number of matches and that is what I was interested in (for a particular permutation of CL).
Now I don't really understand the importance of the other values in X. You seem to be suggesting that you have some way of looking at the other values of X and knowing about the other permutations but I don't understand that.

Subject: does Matlab have any such function

From: Roger Stafford

Date: 4 Feb, 2009 06:19:01

Message: 25 of 29

Will <william108@gmail.com> wrote in message <5124452.1233717244446.JavaMail.jakarta@nitrogen.mathforum.org>...
> As I understand it x(i,j) is the number of times the i in CL occurs in the .....

  Will, I'll try to answer each of your questions. The first one is: "But the diagonal here is relevant to the first permutation of CL. Then I thought what you meant was do the next permutation of CL and form X again and then the diagonal would be relevant to that permutation. Isn't this correct?" No, that is not correct. X is formed only once, before ever entering the part where permutations are examined one-by-one. Otherwise there would be no point in computing X. The same X matrix serves for all different permutations. The picture you should have in mind is that each permutation defines some 15-element path through X in such a way that each column and each row is visited only once. There are 15 factorial such paths, an enormous number. Look at the line

 c = sum(X(p+(0:15:210)));

and notice the p there. That is defining the path I am talking about. For example if p = [9 2 5 1 7 ....] then X(p+(0:15:210)) would be the elements

 X(9,1),X(2,2),X(5,3),X(1,4),X(7,5), etc.

and this is some "path" winding through array X. The sum of all these terms along the path would give that particular value of the "match" count c. This is a particular "path" through matrix X which visits each row and each column just once. It represents the matching score you would get if you transformed the values in CL by that permutation: a 1 in place of 9, a 2 which remains as is, a 3 which replaces a 5, a 4 which replaces a 1, a 5 in place of the 7, etc. This is in accordance with your instruction that the actual numbering within CL is arbitrary with only the "patterns" being preserved.

  Perhaps you are wondering about the notation in

 c = sum(X(p+(0:15:210)));

and in particular how the row and column numbers emerge from all of this. You should examine the matlab 'sub2ind' function which converts from a pair of subscripts into a single index. For example, in p+(0:15:210), the first value in the above example is just 9+0=9 which means row 9 and column 1. The next one is 2+15=17 which is the single index for row 2, column 2. The third one is 5+30+35 which translates to row 5, column 3. Single indices start in the upper left corner, move down the column to the bottom, and then go the top of the next column and move down again, etc. That is why in a 15 x 15 array the single index of 5+30=35 carries you over to the 5th row of the 3rd column.

  You also asked "Now I don't really understand the importance of the other values in X [besides the diagonals.} You seem to be suggesting that you have some way of looking at the other values of X and knowing about the other permutations but I don't understand that." The diagonals give the counts of those cases where the values in the original CL and Var match. It is only pertinent if you are considering the identity permutation - that is, no permutation at all. Remember you have stated that the values in CL were arbitrary and could be changed by a permutation among its values. The off-diagonal elements of the (unchanging) X are relevant to these other permutations. For example row 5, column 3 in X above contains the count of all the 5's in CL which are paired with 3's in Var, and this is done to handle any case where 5's have been transformed to 3's in CL, because this would then
be a match such as you have defined.

  My advice would be to examine very carefully the simple example I gave earlier with 25000 reduced to 30 and 15 reduced to 3. It is fully representative of the larger case. Try to analyze it carefully until you can understand completely what is happening there. If you do, you will be in good shape for the larger case.

Roger Stafford

Subject: does Matlab have any such function

From: Will

Date: 4 Feb, 2009 11:59:19

Message: 26 of 29

Hi. I am getting some of this but not all by any means.
You said,
p = [9 2 5 1 7 ....]
"For example, in p+(0:15:210), the first value in the above example is just 9+0=9 which means row 9 and column 1. The next one is 2+15=17 which is the single index for row 2, column 2. The third one is 5+30+35 which translates to row 5, column 3. Single indices start in the upper left corner, move down the column to the bottom, and then go the top of the next column and move down again, etc. That is why in a 15 x 15 array the single index of 5+30=35 carries you over to the 5th row of the 3rd column."
Where are you getting the 0 in 9+0=9
and the 15 in 2+15=17
and the 30 in 5+30+35

and also, what does (0:15:210) mean?
I see that you are jumping by 15 in what you are adding to the permutation but why?
And how does insure that you only go to any row or any column only once?

And also, how in the world did you come up with the fact that this matrix X would have the property that if you follow one one "path" as you defined it (one row and one column only once) that it would give you all permutations of 15 elements (or however many elements n is in the nxn dimensions of X). And how did you come up with the fact that the entries of such a path when summed up give the number of matches (if that is true)?

?????

Subject: does Matlab have any such function

From: Roger Stafford

Date: 4 Feb, 2009 23:05:05

Message: 27 of 29

Will <william108@gmail.com> wrote in message <10598829.1233748789416.JavaMail.jakarta@nitrogen.mathforum.org>...
> Hi. I am getting some of this but not all by any means.
> ........

  Will, I need to make an adjustment to the code that generates X which I gave you earlier. It should be changed to this:

 X = accumarray([Var,CL],1,[15,15]);

rather than the other way around. The 'Var' values should be the row indices and the CL values the column indices in the 'accumarray' counting process. This will have the effect of generating the transpose of the former X. As it was, with the p used in

 c = sum(X(p+(0:15:210)));

you would have needed to find the inverse, q, of p in order to create a vector

 C2 = q(CL)

which would have the corresponding match count, c, to Var, and this would have been a needless added complexity.

  In the simple example I gave you earlier, it happened that the "best" p was p = [2 1 3] which is its own inverse, so the error didn't show up, but if you had tried p = [2 3 1] or p = [3 1 2], you would have noticed that the match counts in the c formula above wouldn't agree with the actual counts with C2 = p(CL).

  Also in that example there is a typo. I copied the original code instead of the needed modification in computing c. For this example, which has only three possible values in CL and Var, it should read:

 c = sum(X(p+(0:3:6)));

For a general m replacing 15, it would be c=sum(X(p+(0:m:m*(m-1)))). For these errors I apologize.

  As for your questions about p+(0:15:210)) with the p I mentioned, just do the math:

  p = [9 2 5 1 7 ....]
 (0:15:210) = [0 15 30 45 60 ... 210]

 p+(0:15:210) =
 [9+0,2+15,5+30,1+45,7+60,....] = [9,17,35,46,67,.....]

Since we are handing X single indices instead of pairs, it uses the single index method of locating the proper entries, which as I told you is done by counting down the first column, then down the second column, then the third column, and so forth in sequence. So single index 9 would be 9 down the first column and that is row 9, column 1. Index 17 is all the way down the first column and into the second column and two down that column to give row 2, column 2. The 35 index is into the third column and five down giving row 5, column 3. Remember, I suggested that you read up on the 'sub2ind' function, which should explain this conversion from a pair of subscripts to a single index. In fact I could have used 'sub2ind' in this formula for c but chose not to.

  You asked "how in the world did you come up with the fact that this matrix X would have the property that if you follow one one "path" as you defined it (one row and one column only once) that it would give you all permutations of 15 elements." I never made such an absurd claim. One path corresponds to just one permutation, p. The totality of all such paths is the totality of all permutations on 1:15, which are 15-factorial in number. You have to calculate

 c = sum(X(p+(0:15:210)));

repeatedly in a loop that must be executed once for each possible permutation p - that is, each possible "path". The X is calculated just once, but the c is done 1,307,674,368,000 times and that is why it is important for it to be done as quickly as possible.

  Even so, it would require some three and a half years to complete (on my admittedly ancient machine) and that is not counting the generation of the permutations. One point three trillion is a very, very large number indeed, as John has pointed out.

  Finally you asked "And how did you come up with the fact that the entries of such a path when summed up give the number of matches (if that is true)?" Again I refer you to the simplified example I gave you, but of course corrected in the two ways I mentioned above. Look at the terms being added together in sum(X(p+(0:3:12))). For the "best" permutation, p = [2 1 3], it is adding 7 + 2 + 5 = 14. The 7 is the number of cases with Var = 1 and CL = 2, and when the 2 in CL is transformed to a 1, these would be matches with both being 1's. Similarly the 2 is the count of cases where CL = 1 and Var = 2 and with the 1 transformed to a 2, these would also match. The 5 is the count when both CL and Var are equal to 3. Hence if in CL we transform 1 to 2, 2 to 1, and leave 3 as is, the transformed CL and Var would have 7+2+5=14 matches altogether, seven with 1's, two with 2's and five with
3's, which is the best match possible. This transformation is what the vector p does in C2 = p(CL) (once the above correction on X is made.)

  It is extremely wasteful to have to compute all of these individual matches in the 25000 pairs for each permutation. Computing X ahead of time does the bulk of that summation just once and leaves only 15 quantities to be added with each new permutation, one for each of the 15 possible pair values.

Roger Stafford

Subject: does Matlab have any such function

From: Gwendolyn Fischer

Date: 10 Feb, 2009 08:05:06

Message: 28 of 29

Hi Will,

are you still interested in this functionality?
If so, I can show you a function which calculates the p in Rogers algorithm for your 15x15 X in about 50 seconds. This is accomblished by calculating all combinations of X(:,1:7) and X(:,8:15) and than combine the matching combinations and find theire maximum.
If someone is interessted in the details please tell me.

Regards

Gwen

Subject: does Matlab have any such function

From: Gwendolyn Fischer

Date: 11 Feb, 2009 15:07:02

Message: 29 of 29

Hi again,

the munkres algorithm proposed by Steve Lord in this thread
http://www.mathworks.com/matlabcentral/newsreader/view_thread/243884

really does the trick, the 15x15 matrix is solved in 0.002 sec and the only thing you have to do is to call

[pMax cMax] = munkres(max(X)-X);
[pMax,pMax]=max(pMax);
cMax = max(X)*15-cMax;

as the algorithm looks for the lowest values instead of the highest.

Wow

Cheers

Gwen

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us