我需要算法来有效生成唯一的排序排列。它适用于新型神经网络。假设我们有 N 种神经元(比如 3 种),它们彼此相连。我们需要生成并测试所有可能但独特(不花时间)的网络。那是因为订单的重复不会改变网络。我们只对独特的神经元类型指纹感兴趣。
例如,如果我们有 3 个神经元(3 种类型)的网络
在 133(第一个第一种神经元,第二个 - 3d,第三个 - 3d)之后,331 将无效,因为它是多余的,我们已经用一个第一种类型的神经元和两个 3d 类型的神经元检查了所有现成的网络。
因此,具有 3 种可能类型的 3 个 neoron 网络的所有有效变体将是:
111
112
113
221
222
223
331
332
333
123
如何生成这样的排列? (不存储序列的所有中间值,而是根据需要生成它们)
您可以使用 N
整数数组实现这一点,整数的值从 1 到 M
,其中 N
是神经元的数量,M
是神经元类型的数量。
将每个数组元素初始化为1
未终止时:
2a。增加第一个数组元素 - 如果新值小于或等于 M 则返回数组状态,否则
2b。如果第一个数组元素现在大于 M,则递增第二个数组元素并重新初始化第一个数组元素使其等于第二个数组元素 - 如果新值小于或等于 M,则返回数组状态, 否则
2c。如果第二个数组元素现在大于 M,则递增第三个数组元素并重新初始化第一个和第二个数组元素以等于第三个数组元素 - 如果新值小于或等于 M,则返回数组状态,否则
2 倍。等等。如果第 N 个数组元素递增到大于 M,则算法终止。
关键是将第 (i-1) 元素重新初始化为等于刚增加的 i'th 元素 - 这样可以避免重复.即,保持 (i-1)th 元素永远不会小于 ith</strong> 元素的不变性。
例如,给定 3 种类型的 3 个神经元,这将生成排列(第一个索引在右边,第三个索引在左边)
111
112
113
122
123
133
222
223
233
333
int N = 3;
int M = 3;
int[] state = new int[N];
// initialize state so that incrementing it once generates the first legal value
state[0] = 0;
state[1] = 1;
state[2] = 1;
int[] getState() {
for(int i = 0; i < 3; i++) {
state[i]++;
if(state[i] <= M) {
for(int j = 0; j < i; j++) {
state[j] = state[i];
}
return state;
}
}
// no more legal values
state = null;
return state;
}