Iterate over all possible states with only one change

Question

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)

user_2319407 · Answer

It seems, that you are looking for Gray codes

C# code

public static IEnumerable 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:

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

Edit: If "only one change at every step" means not only "in one position" (so 2 1 0 -> 2 1 2 is allowed) but in "in one position and by +1 or -1 only" you can still use Gray code. The algorithm (let me name it "To and Fro") is below.

Start from all zeroes 0...000
Start incrementing nth digit while it's possible: 0..00 -> 0..01 -> .. -> 0..00dn
Increment n-1th digit and start decrementing nth digit: 0..00dn -> 0..01dn -> ... 0..011 -> 0..10
Increment n-1th digit and start incrementing nth digit: 0..10 -> 0..20 -> 0..021 -> ...0..2dn
On 0..0dn-1dn increment n-2th index and start decrementing nth etc.

Demo

# start from 000
    000 -> 001 -> 002 -> 
# increment n-1 th digit, decrementing n-th
 -> 012 -> 011 -> 010 ->    
# increment n-1 th digit, incrementing n-th
 -> 020 -> 021 -> 022 -> 
# increment n-2 th digit, decrementing n-th
 -> 122 -> 121 -> 120 ->
# decrement n-1 th digit, incrementing n-th
 -> 110 -> 111 -> 112 ->
# decrement n-1 th digit, decrementing n-th
 -> 102 -> 101 -> 100 -> 
# increment n-2 th digit, incrementing n-th
 -> 200 -> 201 -> 202 ->
# increment n-1 th digit, decrementing n-th
 -> 212 -> 211 -> 210 -> 
# increment n-1 th digit, incrementing n-th
 -> 220 -> 221 -> 222

C# Code: (Please, fiddle)

public static IEnumerable 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;

  int[] signs = Enumerable.Repeat(1, length).ToArray();
  int[] current = new int[length];

  for (bool keep = true; keep; ) {
    yield return current.ToArray();

    keep = false;

    for (int i = current.Length - 1; i >= 0; --i) {
      int d = current[i] + signs[i];

      if (d >= 0 && d < radix) {
        current[i] = d;

        for (int j = i + 1; j < signs.Length; ++j)
          signs[j] = -signs[j];
        
        keep = true;

        break;
      }
    }
  }
}

Demo:

Console.Write(string.Join(Environment.NewLine, GrayCodes(3, 3)
  .Select(line => string.Join(" ", line))));

Outcome:

user_8389110 · Answer

The Idea:

Let's say that every digit in a position is changed every(right-to-left) 1, S, S * S, S * S * S ... iteration.

And every of 2 * S change it will be mapped according to (0 ... S - 1, S - 1 ... 0):

0 -> 0
...
S - 1 -> S - 1
S ->     S - 1
S + 1 -> S - 2
...
2 * S - 1 -> 0

Since S - 1 and S produce the same result will guarantee that a digit remains the same when a digit in previous position is changed.

C# implementation:

public static int[] Func(long n, int S, int L)
{
    var num = new int[L];

    for (int i = L - 1; i >= 0; i--)
    {
        var x = (int)(n % (2 * S));
        num[i] = x < S ? x : 2 * S - x - 1;
        n /= S;
    }

    return num;
}

Iterating through a whole sequence:

    int S = 3, L = 3;

    for (int i = 0; i < Math.Pow(S, L); i++)
    {
         Console.WriteLine(String.Join(' ', Func(i, S, L)));
    }

The output:

Can try here: https://dotnetfiddle.net/5AzYWr

user_1115951 · Answer

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

Iterate over all possible states with only one change

3 Answers

The Math

The Function