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

Question

Marvin Heidkamp 2019-1-30

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/442258-what-is-the-fastest-and-most-elegant-way-to-calculate-permutations-of-a-vector-of-numbers

评论： Marvin Heidkamp 2019-1-30

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

4 个评论
显示 2更早的评论隐藏 2更早的评论

John D'Errico 2019-1-30

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 2019-1-30

编辑：Marvin Heidkamp 2019-1-30

在 MATLAB Online 中打开

"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

"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 2019-1-30

编辑：Stephen23 2019-1-30

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 2019-1-30

编辑：Marvin Heidkamp 2019-1-30

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 2019-1-30

2
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/442258-what-is-the-fastest-and-most-elegant-way-to-calculate-permutations-of-a-vector-of-numbers#answer_358685

编辑：Jan 2019-1-30

在 MATLAB Online 中打开

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.

3 个评论
显示 1更早的评论隐藏 1更早的评论

Jan 2019-1-30

在 MATLAB Online 中打开

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 2019-1-30

Great! Thanks for your helpful test!

请先登录，再进行评论。

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

4 个评论
显示 2更早的评论隐藏 2更早的评论

采纳的回答

3 个评论
显示 1更早的评论隐藏 1更早的评论

更多回答（0 个）

另请参阅

类别

标签

产品

版本

Community Treasure Hunt

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

4 个评论 显示 2更早的评论隐藏 2更早的评论

采纳的回答

3 个评论 显示 1更早的评论隐藏 1更早的评论

更多回答（0 个）

另请参阅

类别

标签

产品

版本

Community Treasure Hunt

4 个评论
显示 2更早的评论隐藏 2更早的评论

3 个评论
显示 1更早的评论隐藏 1更早的评论