What is the fastest and most elegant way to calculate permutations of a vector of numbers?

First question Is this this the best way to calculate the permutation of a number (I don't want an array of digits)?

>> n = 123;
>> x = str2double(cellstr(perms(int2str(n))))

x =

   321
   312
   231
   213
   132
   123

I rather doubt it...

Second question If it is, what is the best way to calculate the permutation matrix of a number vector (assuming the number of digits is prescribed)?

For example (in this case the numbers from 111 to 999):

Permut = nan(6,889);
for number = 111:999
    counter = number-111+1;
    
    Permut(:,counter) = str2double(cellstr(perms(int2str(number))));
    
end

Or more generic:

numDigits = 3; 

nStart    = str2double(strrep(num2str(ones(    1,numDigits)), ' ', ''));
nFinal    = str2double(strrep(num2str(repmat(9,1,numDigits)), ' ', ''));

Permut    = nan(factorial(numDigits),nFinal-nStart+1);

for number = nStart:nFinal
    counter = number-nStart+1;
    
    Permut(:,counter) = str2double(cellstr(perms(int2str(number))));
    
end

[John D'Errico]

Fastest is rarely the most elegant, the same applies for the converse.

Anyway, you ask about permutations of a vector of numbers, but you are providing a single number. That is a very different question, because some of the time and much of the elegance is involved in converting from numeric form to a vector of digits and back again.

Anyway, worrying about elegance is NEVER a good idea. And worrying about the time required before it is seen to be a problem is also a bad idea in any programming context. Never pre-optimize your code. Get it to work, and only then if the time is a problem, should you worry about optimizing the code.

Finally, you do not even have a complete question, because you do not say what you would do if the number had replicate digits. Thus the digit permutations of 122 will not have 6 possible results, but only 3. So even the code you post will fail.

Worse, what is the result of permutations of the digits of 120? In this case, some of those permutations will be the numbers 12 and 21. So, once converted back into "numbers" the zero disappears. So you will need to decide what your goal is here, since 012 in MATLAB will effectively lose that leading zero.

[Marvin Heidkamp]

"Fastest is rarely the most elegant, the same applies for the converse."

"Anyway, worrying about elegance is NEVER a good idea"

I totally agree with you

"Get it to work, and only then if the time is a problem, should you worry about optimizing the code."

I did this, and as you can imagine from Permutations, the time for calculating 5,6 or even higher digits will increase exponentially. So yes, I do have a time problem. I just wanted to show a simple case.

"Thus the digit permutations of 122 will not have 6 possible results, but only 3. So even the code you post will fail."

How can you say that, if you didnt test it? Unlike you, I did test it and Matlab interprets the permutation of replicate digits as the following:

>> p = perms([1,1,1])

p =

     1     1     1
     1     1     1
     1     1     1
     1     1     1
     1     1     1
     1     1     1

"So, once converted back into "numbers" the zero disappears."

I am aware of this feature, but it doesn't bother me because I will exclude all numbers containing the digit 0 anyway. And even if not, it wouldnt make problems, as you can see here:

>> n = 120;
>> r = perms(int2str(n)-48) * 10.^(numel(v)-1:-1:0).'

r =

    21
    12
   201
   210
   102
   120

If needed, missing digits could be filled with zeros afterwards.

Thanks anyway for your suggestions

[Stephen23]

Note that perms is documented to return the "...all permutations of the elements of vector v...". It does not return the unique permutations of the set of values, only of the elements of the vector. Do not confuse the unique permutations of vector elements with unique permutations of their values (which perms cares absolutely nothing about).

Your example shows that MATLAB correctly returns the six permutations of the elements of the vector [1,1,1], exactly as documented. But there is only one permutation of the set of values (1,1,1):

>> factorial(3) / factorial(3)
ans =  1

https://brilliant.org/wiki/permutations-with-repetition/

[Marvin Heidkamp]

Yes, thanks Stephen for that note. In my case the permutations of vector elements with unique permutations fit for my problem.

I like the brilliant explanation, thanks for the link :)

Answer 1

[Jan]

Question 1:

perms(1:3) * [100; 10; 1]

Or the general case:

v = [2,5,4,8];
r = perms(v) * 10.^(numel(v)-1:-1:0).'

The multiple conversions by str2double, cellstr, and int2str are too indirect. If you want to work with numbers, stay at working with numbers.

If speed matters, replace perms by FEX: VChooseKO, which is about 10 times faster.

In your loop move the calculation of the power of 10 outside the loop.

[Marvin Heidkamp]

Thanks a lot for your (unbelievable fast and) perfect answer! :)

For my loop, your method is significantly faster:

For example for all 5 digits numbers, i.e. 11,111 to 99,999, your method took only 9 seconds instead of my version with 120 seconds.

To convert e.g. the number n = 2548 into a vector v = [2,5,4,8] I used the following:

>> n = 2548;
>> v = int2str(n)-48

v =

     2     5     4     8

I don't know if that's how you do it properly.

"In your loop move the calculation of the power of 10 outside the loop."

I did, so the modified code looks like this:

numDig = 5; 
pow10  = 10.^(numDig-1:-1:0).';

nStart = ones(    1,numDig)*pow10;
nFinal = repmat(9,1,numDig)*pow10;

nPerm  = factorial(numDig);
Permut = nan(nPerm,nFinal-nStart+1);
for number = nStart:nFinal
    counter = number-nStart+1;
    
    numArray = int2str(number)-48;
    Permut(:,counter) = perms(numArray)*pow10;
    
end

"If speed matters, replace perms by FEX: VChooseKO, which is about 10 times faster."

Thanks for the advice, I will look into it and post the final result here if I get it to work. I don't know MEX functions and I'm not sure if I can compile it on a Mac.

[Jan]

sprintf('%d', number) - 48 is most likely faster than int2str. I'd prefer to avoid the conversion to a char vector and back to numbers:

num = mod(floor(N ./ pow10, 10);

A small test:

numDig = 5; 
pow10  = 10.^(numDig-1:-1:0).';

tic;
for k = 11111:99999
    n = int2str(k) - 48;
end
toc

tic;
for k = 11111:99999
    n = sprintf('%i', k) - 48;
end
toc

tic;
for k = 11111:99999
    n = mod(floor(k ./ pow10), 10);
end
toc

% INT2STR: 1.66 sec
% SPRINTF: 0.96 sec
% MOD:     0.33 sec

int2str calls sprintf internally, so calling it directly saves the overhead. But sprintf is extremely powerful, and this costs time. It is cheaper to avoid a conversion, most of all because the expensive pow10 vector has been calculated already.

[Marvin Heidkamp]

Great! Thanks for your helpful test!