检索特定排列，而不在Matlab中存储所有可能的排列 [英] Retrieve a specific permutation without storing all possible permutations in Matlab
问题描述
我正在研究2D矩形包装.为了通过改变零件的放置顺序来最小化无限片材的长度(宽度是恒定的).例如，我们可以在11个零件中放置11个零件！方法.
我可以标记这些部分，并使用perms函数保存所有可能的排列，然后逐个运行它，但是即使是11个部分，我也需要大量的内存.我希望能够做到约1000个零件.
幸运的是，我不需要所有可能的顺序.我想将每个排列索引到一个数字.测试随机序列，然后使用GA收敛结果以找到最佳序列.
因此，与randperm函数不同，我需要一个函数在运行任意次数时给出特定的排列值.
例如，function(5,6)应该始终返回6个部分的说[1 4 3 2 5 6].我不需要特定顺序的序列，但是函数应该为相同的索引提供相同的序列.并且对于其他一些索引，其顺序不应与此索引相同.
到目前为止，我已经使用randperm函数生成了大约2000次迭代的随机序列，并通过比较长度找到了最佳序列，但这仅适用于少数零件.另外，使用randperm可能会导致重复序列而不是唯一序列.
这是我所做的事情的图片.
我无法保存randperm的输出，因为我没有可搜索的功能空间.我不想找到所有序列的工作表长度.我只需要对由遗传算法确定的特定索引所确定的特定序列进行处理.如果使用randperm，我将没有所有索引的顺序(即使我只需要其中一些).
例如，假设某个函数'y = f(x)'在[0,10]范围内.对于x的每个值，我得到y. y是我的纸页长度. x是排列索引.对于任何x，我都会找到其序列(特定排列)，然后是其对应的图纸长度.根据x的一些随机值的结果，GA会为我生成一个x的新列表，以找到更理想的y.
我需要一个复制perms的函数(我猜perms每次运行都遵循相同的排列顺序，因为perms(1:4)在运行任意次时会产生相同的结果)，而无需实际存储值.
有没有一种编写函数的方法?如果没有，那我该如何解决我的问题?
编辑(我如何解决此问题):
在Genetic Algorithm中，您需要交叉父代(排列)，但是如果交叉排列，您将得到重复的数字.例如:-将1 2 3 4与3 2 1 4交叉可能会导致类似3 2 3 4的情况.因此，为避免重复，我想到了将每个父级索引为一个数字，然后将数字转换为二进制形式，然后将二进制索引交叉以获得一个新的二进制数，然后将其转换回十进制并找到其特定的排列.但是后来，我发现我可以只使用排列本身的ordered crossover而不是交叉索引.
有关Ordered Crossover的更多详细信息，请参见此处
下面是两个函数，它们一起将按字母顺序生成排列并返回第n个排列
例如，我可以打电话
nth_permutation(5, [1 2 3 4])
输出将是[1 4 2 3]
直观地讲，该方法花费的时间在n中是线性的.集合的大小无关紧要.我对nth_permutations(n, 1:1000)进行了100次迭代的平均测试，得到了下图
所以按时间顺序似乎还可以.
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
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.
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
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
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
这篇关于检索特定排列，而不在Matlab中存储所有可能的排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
