检索特定排列而不在 Matlab 中存储所有可能的排列

Question

我正在研究二维矩形包装。为了通过改变零件放置的顺序来最小化无限sheet（宽度不变）的长度。例如，我们可以将 11 个零件放在 11 个零件中！方法。

我可以标记这些部分并使用 perms 函数和运行一个一个地保存所有可能的排列，但即使是 11 个部分我也需要大量内存。我希望能够完成大约 1000 个零件。

幸运的是，我不需要所有可能的序列。我想将每个排列索引到一个数字。测试一个随机序列，然后使用 GA 收敛结果以找到最优序列。

因此，我需要一个函数，它在运行时给出特定的排列值，与 randperm 函数不同。

例如，function(5,6) 应该总是 return 说 [1 4 3 2 5 6] 6 个部分。我不需要特定顺序的序列，但函数应该为相同的索引提供相同的序列。并且对于其他一些索引，序列不应与此相同。

到目前为止，我已经使用 randperm 函数为大约 2000 次迭代生成随机序列，并通过比较长度从中找到最佳序列，但这仅适用于少数部分。此外，使用 randperm 可能会导致重复序列而不是唯一序列。

这是我所做的图片。

我无法保存 randperm 的输出，因为我没有可搜索的函数 space。我不想找到所有序列的 sheet 的长度。我只需要对由遗传算法确定的特定索引识别的特定序列执行此操作。如果我使用 randperm，我不会有所有索引的序列（即使我只需要其中的一些）。

例如，取[0,10]范围内的某个函数'y = f(x)'。对于 x 的每个值，我得到一个 y。这里 y 是我的 sheet 长度。 x 是排列的索引。对于任何 x，我找到它的序列（特定排列），然后找到它对应的 sheet 长度。基于 x 的一些随机值的结果，GA 会为我生成一个新的 x 列表以找到更优化的 y。

我需要一个重复 perms 的函数，（我猜 perms 每次都遵循相同的排列顺序运行因为 perms(1:4) 会产生相同的结果运行任意次数时的结果）而不实际存储值。

有没有写函数的方法？如果没有，那我该如何解决我的问题？

编辑（我是如何解决这个问题的）：

在Genetic Algorithm中，你需要交叉parents(permutations)，但是如果交叉排列，你会得到重复的数字。例如：- 将 1 2 3 4 与 3 2 1 4 交叉可能会产生类似 3 2 3 4 的结果。因此，为了避免重复，我想到了将每个父级索引为一个数字，然后将数字转换为二进制形式，然后交叉二进制索引以获得新的二进制数，然后将其转换回十进制并找到其特定排列。但后来，我发现我可以只使用排列本身的 ordered crossover 而不是跨越它们的索引。

可以找到有关 Ordered Crossover 的更多详细信息 here

Answer 1

下面是两个函数，它们一起将按词法顺序生成排列和return第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

检索特定排列而不在 Matlab 中存储所有可能的排列

Retrieve a specific permutation without storing all possible permutations in Matlab

matlab

optimization

permutation

genetic-algorithm

nested