3 views (last 30 days)

Show older comments

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.

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))

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))

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.

Walter Roberson
on 8 Apr 2021

I posted code at https://www.mathworks.com/matlabcentral/answers/623358-get-a-combination-of-unique-paths-for-given-pair-of-numbers#comment_1082638 that you can adapt.

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.

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

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);

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

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.

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))

seconds_per_perm = 1./perms_per_second

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.

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

Start Hunting!