MATLAB Answers

Getting all Permutations of a 18+ integer vector

3 views (last 30 days)
Brian Ross
Brian Ross on 8 Apr 2021
Edited: Walter Roberson on 11 Apr 2021
I am working on a project to get all permutations of a 18+ integer vector. Working with the perms function limits me to 9 integers and forces me to do cencatenate the two permuations, but I miss some of my combinations
l1 = [1:1:9]';
l2 = [10:1:18]';
l1perms = perms(l1);
l2perms = perms(l2);
lp = [l1perms,l2perms];
I would like to perform an operation on each possible permutation, but am struggling to develop a code that correctly displays each permutation without requiring a fixed number of for loops. In the code above, I perform an evaluation on each row of lp, but my matrix is limited in size due to the size of the matrix.
Ideally, the user would be able to put in a vector and the program would evaluate each permutation where the length of the original vector can vary from 18 to 30 integers.
  2 Comments
Steven Lord
Steven Lord on 8 Apr 2021
In addition to the memory considerations, what are you planning to do with all those permutations? Let's say you could process a thousand a second. How long would it take to process them all?
format longg
years(seconds(factorial(18)/1000))
ans =
202883.1461837
I don't think you want to wait over 200,000 years. All permutations of 30 elements is even worse.
years(seconds(factorial(30)/1000))
ans =
8.40552851277243e+21
If you started when the universe started you wouldn't be anywhere close to done. You need to start looking at the timeline of the far future to learn what would happen before your calculations were complete.

Sign in to comment.

Answers (2)

Walter Roberson
Walter Roberson on 8 Apr 2021
Make the last position have 18 possibilities, the second last 17, the third last 16, and so on. Increment by "one" in odometer style.
Then to read out the value, take the last digit and use it to index into the list of values. Write that down and remove that value from the list. Move to the next digit (17 possibilities) and use it to index the (shorter) list of values. Write that down and remove that value from the list. And so on, eventually getting to point there is only one left. The list of values is the permutation. Every integer from 1 to 18! maps to exactly one permutation.
  1 Comment
Walter Roberson
Walter Roberson on 8 Apr 2021
I tried pushing this up to 13 then 11 then 10, but the execution time exceeded the 55 second limit.
At this rate the calculation for 18 should only take about 5000 years.
starttime = tic;
N = 9;
permstate = zeros(1,N);
counter = 1;
matches = 0;
while ~isempty(permstate)
thisperm = decode_perm(permstate);
if thisperm(1) == 5 && thisperm(3) == 9 && thisperm(4) == 2 && thisperm(6) == 8 && thisperm(9) == 7
if matches <= 10
fprintf('pattern detected at perm #%d\n', counter);
disp(thisperm);
end
matches = matches + 1;
end
permstate = nextperm(permstate);
counter = counter + 1;
end
pattern detected at perm #243150
5 6 9 2 4 8 3 1 7
pattern detected at perm #243197
5 4 9 2 6 8 3 1 7
pattern detected at perm #243870
5 6 9 2 3 8 4 1 7
pattern detected at perm #243917
5 3 9 2 6 8 4 1 7
pattern detected at perm #245309
5 4 9 2 3 8 6 1 7
pattern detected at perm #245333
5 3 9 2 4 8 6 1 7
pattern detected at perm #252510
5 6 9 2 4 8 1 3 7
pattern detected at perm #252557
5 4 9 2 6 8 1 3 7
pattern detected at perm #253926
5 6 9 2 1 8 4 3 7
pattern detected at perm #254003
5 1 9 2 6 8 4 3 7
pattern detected at perm #255365
5 4 9 2 1 8 6 3 7
endtime = toc(starttime);
counter = counter - 1;
fprintf('Done %d permutations, %g seconds, mean %g perms per second, %d pattern matches\n', counter, endtime, counter/endtime, matches);
Done 362880 permutations, 8.48854 seconds, mean 42749.4 perms per second, 24 pattern matches
function permstate = nextperm(permstate)
got_one = false;
for K = 2:length(permstate)
permstate(K) = permstate(K) + 1;
if permstate(K) < K; got_one = true; break; end
permstate(K) = 0;
end
if ~got_one; permstate = []; end
end
function decoded = decode_perm(permstate)
N = length(permstate);
states = 1 : N;
decoded = zeros(1,N);
for K = N : -1 : 1
s = permstate(K) + 1;
decoded(K) = states(s);
states(s) = [];
end
end

Sign in to comment.


James Tursa
James Tursa on 8 Apr 2021
The number of different permutations of a vector of size n is n! (n factorial). So what you are attempting has these many possibilities:
18! is about 6.4e15
30! is about 2.7e32
So this huge number of permutations makes your approach infeasible, both from a memory standpoint and from an execution time standpoint. You need a different approach. Maybe you could describe the problem you are working on and we could suggest another approach. E.g., Monte Carlo etc.
  3 Comments
Walter Roberson
Walter Roberson on 10 Apr 2021
I already posted code for you above, in https://www.mathworks.com/matlabcentral/answers/795817-getting-all-permutations-of-a-18-integer-vector#comment_1448697 -- the nextperm() and decode_perm() functions. And I gave a demonstration of filtering the outputs.
However, the timing I show there, roughly 40000 permutations per second, would need about 5000 years for permutations of 18, and would take roughly 2E21 years for 30 elements.
Suppose you give us a target execution time of one month (30 days) for computing with 30.
perms_per_second = factorial(30)/seconds(days(30))
perms_per_second = 1.0234e+26
seconds_per_perm = 1./perms_per_second
seconds_per_perm = 9.7718e-27
That is 0.01 yactoseconds per permutation. By way of comparison, the fastest directly measured physical quantity is 247 zeptoseconds where a zeptosecond is 1e-21 seconds, so that is 247000 times slower than the seconds per permutation that you would need. The most powerful particle accelerators in the world were needed to measure the lifetime of top quarks at about 0.4 yactoseconds, so to have any chance of dealing with 1e-26 seconds per permutation, you would need particle accelators roughly 25 times as powerful as anything that has ever been created.
This is clearly not sustainable. In order to have a hope of being sustainable, you need to have a method that can produce filtered permutations faster than producing all of the permutations. You need a strategy that skips producing some of the permutations because it knows they will never be used.
If you need to evaluate a function at every permutation, then you have no realistic hope of proceeding.
If the permutations must satisfy certain properties to be considered for evaluation of the function, then there is sometimes a chance.... but we would need to know what properties need to be satisfied to have any chance of thinking up a more effective way of producing appropriate permutations.

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!