生成唯一排序排列

Question

我需要有效生成唯一排序排列的算法。这是一种新型的神经网络。假设我们有N种类型的神经元(例如，3)，它们是连接在一起的。我们需要生成和测试所有可能的，但独特的(为了不花费时间)网络。这是因为重复秩序不会改变网络。我们只对独特的神经元类型指纹感兴趣。

例如，如果我们在133 (第1型、第2型和第3型)后有3个神经元(3种类型)的网络，则331将无效，因为它是多余的，因此我们会有一个1型神经元和2个3d型神经元的现成网络。

因此，具有三种可能类型的3个神经元网络的所有有效变化将为: 111 112 113 221 222 223 331 332 333 123。

如何产生这样的排列？(不要存储序列的所有中间值，而是根据需要生成它们)

Answer 1

您可以使用一个值从1到M的N整数数组来实现这一点，其中N是神经元的数量，M是神经元类型的数目。

1. 将每个数组元素初始化为1
2. 虽然没有终止，但：

2a。增加第一个数组元素-如果新值小于或等于M，则返回数组状态，否则

2b。如果第一个数组元素现在大于M，那么增加第二个数组元素并重新初始化第一个数组元素，使其等于第二个数组元素--如果新值小于或等于M，则返回数组状态，否则

2c。如果第二个数组元素现在大于M，那么增加第三个数组元素并重新初始化第一个和第二个数组元素，使其等于第三个数组元素-如果新值小于或等于M，则返回数组状态，否则

2倍等等。如果Nth数组元素的增量大于M，则该算法终止。

关键是重新初始化(i-1)'th元素，使其等于公正增量的i'th元素--这样就避免了重复。也就是说，保持(i-1)'th元素从不小于i'th元素的不变。

例如，给定3种类型的3个神经元，就会产生排列(1指数在右边，第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;
}