let's say we have two variables L and S

L: length of any sequence (count of items in any sequence)

S: number of possible states for any item

And imagine we have a set of all possible sequences with these two variables. For example:

L=3, S=2

All Possible Sequences : S is 2 so we can have 0 and 1 for any item
0,1,0 0,0,0 1,0,0 1,1,0 1,1,1 0,1,1 0,0,1 1,0,1

Now the problem that I have is: Is there any way to iterate on the set of all possible sequences by having only one change at every step? you can see a sample in the example I wrote above. (I have calculated them by hand). at every step, we have only one change (one item increase or decrease by 1)

I need a none recursive function or method (in math or programming) to get the i'th state from an L, S set with that rule(one change at every index change)

CodePudding user response：

It seems, that you are looking for Gray codes

C# code

public static IEnumerable<int[]> GrayCodes(int length, int radix) {
  if (length < 0)
    throw new ArgumentOutOfRangeException(nameof(length));
  if (radix < 0)
    throw new ArgumentOutOfRangeException(nameof(radix));

  if (0 == length || 0 == radix)
    yield break;

  static int digit(long n, int radix, int i) =>
    (int)(Math.Floor(n / Math.Pow(radix, i)) % radix);

  double count = Math.Pow(radix, length);

  long max = count > long.MaxValue ? long.MaxValue : (long)count;

  for (long i = 0; i < max;   i) {
    int[] result = new int[length];
    int shift = 0;

    for (int j = length - 1; j >= 0; j--) {
      var x = (digit(i, radix, j)   shift) % radix;

      shift  = radix - x;
      result[length - j - 1] = x;
    }

    yield return result;
  }
}

Demo

var report = string.Join(Environment.NewLine, GrayCodes(2, 3)
  .Select(g => string.Join(" ", g)));

Console.Write(report);

Outcome:

0 0
0 1
0 2
1 2
1 0
1 1
2 1
2 2
2 0

If you want to flatten the sequence, add SelectMany:

var report = string.Join(", ", GrayCodes(2, 3).SelectMany(g => g));

Console.WriteLine(report);

Console.WriteLine();

// Your case, length = 3, radix = 2
report = string.Join(", ", GrayCodes(3, 2).SelectMany(g => g));

Console.WriteLine(report);

Outcome:

0, 0, 0, 1, 0, 2, 1, 2, 1, 0, 1, 1, 2, 1, 2, 2, 2, 0

0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0

CodePudding user response：

The Math

There may be multiple answers, I see Gray codes in the other answer, but this is my own solution. Examples are given in decimals (S=10), as I think decimals are easier to understand than binaries. But the method works for any values of S.

For 2 digits decimals (L=2, S=10), I can have:

00, 01, 02, 03, ... 09, 19, 18, 17, 16, ... 10, 20, 21, 22, ...

That is, after 09, instead of 10, we just go to 19 instead, and start counting backwards to 18, 17, ... 10. Then we go to 20, and repeat:

20, ... 29, 39, ... 30, 40, ... 49, 59, ...

Ultimately we will reach 90: 30, 40, ... 50, 60, ... 70, 80, ... 90

But we cannot go to 100, because that involves 2 digits that are changed. But we can use the same trick of counting backwards:

090, 190, 191, ... 199, 189, 188, ... 180, 170, 171, ... 179, 169, ...

The Function

In Python. Explanation as comments in code.

def f(n, l, s):
    # Get all digits of n. 
    # Example for decimals (s=10), if n = 143, digits = [1, 4, 3]
    digits = []
    cur_n = n
    for i in range(l):
        cur_digit = cur_n%s 
        digits.append(cur_digit)
        cur_n = int(cur_n / s)
    digits.reverse() # digits = [1, 4, 3]

    # Continuing the same decimals example if n = 143, the output should be 153.
    # Explanation below. We first copy the digits.
    output_digits = list(digits)

    # First digit is the same.
    output_digits[0] = digits[0]

    # For each digit
    for i in range(len(digits) - 1):
        digit=digits[i]
        next_digit = digits[i 1]

        # If it is an odd number
        if digit%2 == 1:
            # Then the next_output_digit is 9 - next_digit
            next_output_digit = s - 1 - next_digit
        else:
            # Else, the next_output_digit is the same as next_digit
            next_output_digit = next_digit
        output_digits[i 1] = next_output_digit

    # Convert [1, 5, 3] to ["1", "5", "3"]
    output_digits_string = [str(digit) for digit in output_digits]
    # Convert to "153"
    output_string = "".join(output_digits_string)
    # Finally, return output_string
    return int(output_string)

To test the algorithm, run these 2 examples:

for i in range(199): print(f(i,3,10)) # Decimals, 3 digits, first 199 values
for i in range(8): print(f(i,3,2)) # Binaries, 3 digits, all 8 values