I have been playing around with analysis of circuits and am trying to generate test vectors. In order to exercise the circuit in the manner I require, I need a vector that includes every change in the circuit's inputs where only 1 input toggles, but in order to be efficient, it must include each change only once and must not include any changes where more than one input toggles. Inputs can be only logic high (1) or low (0). If these sequences don't already have a name I would like to call them Majella tuples.

I believe the length of these Majella tuples to be ((2^n) * n) + 1 where n is the width of the input in bits.

for example (with all 0 starting patterns):

n = 1:

0 1 0

n = 2:

00 10 11 01 11 10 00 01 00

n = 3:

000 100 110 010 110 111 011 001 101 001 011 111 101 111 110 100 101 100 000 010 011 010 000 001 000

I have written a bit of code to brute force generate these codes. However, it starts to struggle at n = 5 (I'm assuming this is because of the complexity, but it may well be because there is a bug).

#include <stdio.h>
#include <stdlib.h>

struct mjc_ll {
  const unsigned long int val;
  const struct mjc_ll* next;
};

// prints integer val in binary

void mjc_print_bin(const unsigned long int val, const unsigned char sf)
{
  if (sf != 0) {
    unsigned long int s = (1 << (sf - 1));
    while (s != 0) {
      printf("%c", ((val & s) != 0) ? '1' : '0');
      s >>= 1;
    }
  }
  printf("\n");
}

unsigned long int mjc_power(const unsigned long int base,
                const unsigned long int exponent)
{
  return (exponent == 0) ? 1 : (base * mjc_power(base, exponent - 1));
}

// returns 1 if transition found in ll, 0 otherwise

int mjc_search_ll(const struct mjc_ll* const ll, const unsigned long int val,
          const unsigned long int prev)
{
  if (ll->next == 0) {
    // reached end of list
    return 0;
  } else if ((val == ll->val) && (prev == ll->next->val)) {
    // change found
    return 1;
  }
  return mjc_search_ll(ll->next, val, prev);
}

// prints the solution and returns 1 if a solution found, otherwise returns 0

int mjc_next(const struct mjc_ll* const ll, const unsigned long int val,
         const unsigned char bit_len, const unsigned long int count,
         const unsigned long int limit)
{
  if (count == limit) {
    // reached the end
    mjc_print_bin(0, bit_len);
    return 1;
  } else if ((ll != 0) && (mjc_search_ll(ll, val, ll->val) != 0)) {
    // found duplicate
    return 0;
  }
  const struct mjc_ll new = {val, ll};
  unsigned char i = 0;
  while(i < bit_len) {
    if (mjc_next(&new, val ^ (1 << i), bit_len, count + 1, limit) == 1) {
      mjc_print_bin(val, bit_len);
      return 1;
    }
    ++i;
  }
  return 0;
}

void mjc(const unsigned char bit_len)
{
  (void)mjc_next(0, 0, bit_len, 0, mjc_power(2, bit_len) * bit_len);
}

int main(int argc, char* argv[])
{
  if (argc != 2) {
    printf("mjc takes 1 arg, the bit width of the pattern\n");
  } else {
    mjc(strtol(argv[1], 0, 0));
  }
  return 0;
}

some properties:

I would guess that there are solutions for all every possible n (positive integers). If there is a solution for n, there must be at least n! solutions as swapping the order of the inputs does not invalidate the solution. Reversing the order of a solution also does not invalidate it.

In each solution each input pattern should be present n times (except the starting pattern, that is present n + 1 times). The start and end patterns will always be the same.

Unfortunately this is where my knowledge runs out.

Is there a more efficient way of producing a valid solution given n as an input?

Can it be (easily) proven that there are solutions for all values of n?