Generate unique sorted permutation

Question

I need algorithm for effective generation unique sorted permutations. It is for new kind of a neural network. Assume that we have N types of neurons (let it be 3 for example), they are connected togother. We need to generate and test all possible, but unique (to not spend time) networks. That is because repetition of order does not change network. We are interested only in unique neurons types fingerprint.

For example if we have network of 3 neurons (with 3 types) after 133 (first neoron of 1st type, second of - 3d, and third of - 3d), then 331 will not be valid because it is superfluous, we are cheked allready network with one neuron of 1st type and two of 3d types.

So all valid variations for network of 3 neorons with 3 possible types will be: 111 112 113 221 222 223 331 332 333 123

How to generate such permutations? (do not store all the intermediate values of the sequence, rather generate them as required)

Zim-Zam O'Pootertoot · Accepted Answer · 2014-11-16T02:17:26.890

You can accomplish this with an array of N integers with values from 1 to M, where N is the number of neurons and M is the number of neuron types.

Initialize each array element to 1
While Not Terminated:

2a. Increment the 1st array element - if the new value is less than or equal to M then return the array state, else

2b. If the 1st array element is now greater than M, then increment the 2nd array element and re-initialize the 1st array element to be equal to the 2nd array element - if the new value is less than or equal to M then return the array state, else

2c. If the 2nd array element is now greater than M, then increment the 3rd array element and re-initialize the 1st and 2nd array elements to be equal to the 3rd array element - if the new value is less than or equal to M then return the array state, else

2X. Et cetera. If the Nth array element is incremented to be greater than M then the algorithm terminates.

The key is re-initializing the (i-1)'th element to be equal to the just-incremented i'th element - this way you avoid duplicates. I.e., maintain the invariant that the (i-1)'th element is never less than the i'th element.

For example, given 3 neurons of 3 types, this will generate the permutation (1st index is on the right, 3rd index is on the left)

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;
}

Generate unique sorted permutation

1 Answers1