How to generate all possible permutations of an array having numbers from 1 to 24?

I need to generate all possible permutations of an array A which is [1:x]. x is 24. If x is<=10, then it s possible with 'perms' function. But it is not possible for 'x' greater than 10. Is there any alternative way to do the same?

Thank you for your answers in advance.

[Stephen23]

You could use

https://en.wikipedia.org/wiki/Heap's_algorithm

and then be prepared to wait a long time.

Answer 1

[Walter Roberson]

You can use the "odometer" pattern.

https://www.mathworks.com/matlabcentral/answers/602395-different-number-of-for-loops#answer_502861

For the specific case of permutations, you could filter out any cases where the new vector had any duplicates. However you can be a lot more efficient if instead you swap entries in a smart way.

There is also an approach involving just counting upwards, and decoding each of the integers as a permutation index. You can map each positive integer to a permutation. Up to factorial(20) the indices fit into a 64 bit number, but for larger sets you would need something similar to Java BigInteger class.

Reminder: there are more than 2^79 permutations of 24 elements. You can potentially deal with the storage needs by processing one at a time, or a reasonable batch at a time, but counting to 2^79 is going to take you many many times the expected life of the universe.

[Walter Roberson]

https://medium.com/@benjamin.botto/sequentially-indexing-permutations-a-linear-algorithm-for-computing-lexicographic-rank-a22220ffd6e3

Answer 2

[Bruno Luong]

perms(1:4) % toy example

ans = 24×4

4 3 2 1 4 3 1 2 4 2 3 1 4 2 1 3 4 1 3 2 4 1 2 3 3 4 2 1 3 4 1 2 3 2 4 1 3 2 1 4

perms(1:24) % what you ask is

Error using perms
Requested array exceeds the maximum possible variable size.

Why? Because you need

(factorial(24)*24*8)/(1024^4) =~ 10^14

Tera bytes to store it. Do your PC have this kind of RAM.

And assuming you can process 100 of such permutations per second you need

(factorial(24))/(100*3600*24*365) =~ 2*10^14

years to process the whole thing. Do you intend to live that long?

[AMAL VASU]

Tera bytes to store it. Do your PC have this kind of RAM: No that is the problem.

[AMAL VASU]

Thank you for your humorous explanation

[Bruno Luong]

@AMAL VASU "Tera bytes to store it. Do your PC have this kind of RAM: No that is the problem."

OK so this is the code that doesn't have this problem showed with the toy example, please replace 1:4 with 1:24 and eventually fun with whatever the process you intend to do with the permutaion.

Good luck and for long life for you!

fun = @(p) fprintf('%s\n', mat2str(p));
allpermsapply(1:4, fun);

[1 2 3 4]
[1 2 4 3]
[1 3 2 4]
[1 3 4 2]
[1 4 2 3]
[1 4 3 2]
[2 1 3 4]
[2 1 4 3]
[2 3 1 4]
[2 3 4 1]
[2 4 1 3]
[2 4 3 1]
[3 1 2 4]
[3 1 4 2]
[3 2 1 4]
[3 2 4 1]
[3 4 1 2]
[3 4 2 1]
[4 1 2 3]
[4 1 3 2]
[4 2 1 3]
[4 2 3 1]
[4 3 1 2]
[4 3 2 1]

function allpermsapply(v, fun)
apa_helper([], v, fun);
end

function apa_helper(p, q, fun)
if isempty(q)
    fun(p);
else
    for k=1:length(q)
        apa_helper([p, q(k)], q([1:k-1 k+1:end]), fun);
    end
end
end

[Steven Lord]

@Bruno Luong may have written that answer humorously, but the facts cited in that answer are still correct. You don't have anywhere near enough memory to create that large an array. For context, 10^14 terabytes is 100,000 zettabytes. What's a zettabyte? A practical example is that global internet traffic in 2016 was about a zettabyte.

There's also the time consideration.

secondsToFinish = seconds(factorial(24)/100);
yearsToFinish = years(secondsToFinish)

yearsToFinish = 1.9661e+14

According to Wikipedia's timeline of the far future, processing 100 of those permutations each second would finish about the time there are only about 100 stars shining in what previously was the Milky Way.

You're going to need to rethink the approach you're going to use for whatever problem you were hoping to solve using brute force enumeration of all permutations.