Retrieve a specific permutation without storing all possible permutations in Matlab

Question

I am working on 2D rectangular packing. In order to minimize the length of the infinite sheet (Width is constant) by changing the order in which parts are placed. For example, we could place 11 parts in 11! ways.

I could label those parts and save all possible permutations using perms function and run it one by one, but I need a large amount of memory even for 11 parts. I'd like to be able to do it for around 1000 parts.

Luckily, I don't need every possible sequence. I would like to index each permutation to a number. Test a random sequence and then use GA to converge the results to find the optimal sequence.

Therefore, I need a function which gives a specific permutation value when run for any number of times unlike randperm function.

For example, function(5,6) should always return say [1 4 3 2 5 6] for 6 parts. I don't need the sequences in a specific order, but the function should give the same sequence for same index. and also for some other index, the sequence should not be same as this one.

So far, I have used randperm function to generate random sequence for around 2000 iterations and finding a best sequence out of it by comparing length, but this works only for few number of parts. Also using randperm may result in repeated sequence instead of unique sequence.

Here's a picture of what I have done. Packing example

I can't save the outputs of randperm because I won't have a searchable function space. I don't want to find the length of the sheet for all sequences. I only need do it for certain sequence identified by certain index determined by genetic algorithm. If I use randperm, I won't have the sequence for all indexes (even though I only need some of them).

For example, take some function, 'y = f(x)', in the range [0,10] say. For each value of x, I get a y. Here y is my sheet length. x is the index of permutation. For any x, I find its sequence (the specific permutation) and then its corresponding sheet length. Based on the results of some random values of x, GA will generate me a new list of x to find a more optimal y.

I need a function that duplicates perms, (I guess perms are following the same order of permutations each time it is run because perms(1:4) will yield same results when run any number of times) without actually storing the values.

Is there a way to write the function? If not, then how do i solve my problem?

Edit (how i approached the problem):

In Genetic Algorithm, you need to crossover parents(permutations), But if you crossover permutations, you will get the numbers repeated. for eg:- crossing over 1 2 3 4 with 3 2 1 4 may result something like 3 2 3 4. Therefore, to avoid repetition, i thought of indexing each parent to a number and then convert the number to binary form and then crossover the binary indices to get a new binary number then convert it back to decimal and find its specific permutation. But then later on, i discovered i could just use ordered crossover of the permutations itself instead of crossing over their indices.

More details on Ordered Crossover could be found here

• Cecilia: How many of the permutations do you expect to use? Could you just store a list of those you have already used and check against it when you get a new value from randperm? This would be less expensive if the number of permutations you use is small.
• beaker: You can number permutations as you see here, but the problem then becomes how to get a numeric type with the range to express the values 0..1000!.
• Santhan Salai: edited to make it clear why i cant use 'randperm'
• Cecilia: You could right a function to generate permutations in lexographical order, but only return the nth permutation. Wikipedia gives a possible algorithm.

Answer 1

Below are two functions that together will generate permutations in lexographical order and return the nth permutation

For example, I can call

nth_permutation(5, [1 2 3 4])

And the output will be [1 4 2 3]

Intuitively, how long this method takes is linear in n. The size of the set doesn't matter. I benchmarked nth_permutations(n, 1:1000) averaged over 100 iterations and got the following graph

Benchmark graph of n vs time

So timewise it seems okay.

function [permutation] = nth_permutation(n, set)
%%NTH_PERMUTATION Generates n permutations of set in lexographical order and
%%outputs the last one
%% set is a 1 by m matrix
set = sort(set);
permutation = set; %First permutation
for ii=2:n
 permutation = next_permute(permutation); 
end
end
function [p] = next_permute(p)
%Following algorithm from https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
%Find the largest index k such that p[k] < p[k+1]
larger = p(1:end-1) < p(2:end);
k = max(find(larger));
%If no such index exists, the permutation is the last permutation.
if isempty(k)
 display('Last permutation reached');
 return
end
%Find the largest index l greater than k such that p[k] < p[l].
larger = [false(1, k) p(k+1:end) > p(k)];
l = max(find(larger));
%Swap the value of p[k] with that of p[l].
p([k, l]) = p([l, k]);
%Reverse the sequence from p[k + 1] up to and including the final element p[n].
p(k+1:end) = p(end:-1:k+1);
end

• Santhan Salai: Actually i moved on with another way to solve the problem. but this could be a great solution for someone having similar problem. I didn't test this, but this is what i was looking for. thanks and +1
• Cecilia: Glad you found another solution! Best of luck.
• eric: @SanthanSalai you should post what you ended up using as an answer.
• Santhan Salai: Actually what i meant was i avoided this problem itself instead of finding different way to solve this specific problem. In GA, you need to crossover parents, i thought of indexing each parent(permutation) to a number and then convert the number to binary form and then crossover the binary indices to get a new binary number -> convert to decimal -> find their specific permutation. But then, i discovered i could just use ordered crossover of the permutations itself instead of crossing over their indices. @neuronet
• Santhan Salai: Details for ordered crossover can be found here. Did i help you? @neuronet