Getting all Permutations of a 18+ integer vector

3 visualizzazioni (ultimi 30 giorni)
Brian Ross
Brian Ross il 8 Apr 2021
Modificato: Walter Roberson il 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 Commenti
DGM
DGM il 8 Apr 2021
I'm pretty sure you're going to have to figure out a way to do what you need to do in a way that doesn't require calculating all the permutations at once. The result from perms(18) would occupy 9.2E17 bytes. I'm not sure where you'd put it.
Steven Lord
Steven Lord il 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.

Accedi per commentare.

Risposte (2)

Walter Roberson
Walter Roberson il 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 Commento
Walter Roberson
Walter Roberson il 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

Accedi per commentare.


James Tursa
James Tursa il 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 Commenti
Brian Ross
Brian Ross il 10 Apr 2021
Yes this is exactly my issue. Instead of calculating each permutation and storing in a matrix, I would like to develop a code that allows me to generate a permutation, evaluate it, then overwrite it with the next permutation. However, I am having issues coming up with a code that properly generates all potential permutations.
Walter Roberson
Walter Roberson il 10 Apr 2021
Modificato: Walter Roberson il 11 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.

Accedi per commentare.

Categorie

Scopri di più su Discrete Math in Help Center e File Exchange

Community Treasure Hunt

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

Start Hunting!

Translated by