algorithm - 仅进行一项更改即可迭代所有可能的状态

Question

假设我们有两个变量 L 和 S

L:任意序列的长度(任意序列中的项目数)

S:任何项目的可能状态数

假设我们有一组包含这两个变量的所有可能序列。例如:

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

现在我遇到的问题是:有没有办法通过每一步只进行一个更改来迭代所有可能序列的集合？你可以在我上面写的例子中看到一个示例。 (我是手工计算的)。每一步，我们只有一个变化(一项增加或减少 1)

我需要一个非递归函数或方法(在数学或编程中)来从具有该规则的 L、S 集中获取第 i 个状态(每次索引更改时都会发生一个更改)

Answer 1

您似乎正在寻找 Gray codes

C#代码

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

演示

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

Console.Write(report);

结果:

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

如果您想要展平序列，请添加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);

结果:

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

编辑:如果“每一步仅进行一次更改”不仅意味着“在一个位置”(因此 2 1 0 -> 2 1 2 是允许的)，但在“仅在一个位置和 +1 或 -1”中，您仍然可以使用格雷码。该算法(让我将其命名为“To and Fro”)如下。

1. 从零开始0...000
2. 在可能的情况下开始递增第n位数字:0..00 -> 0..01 -> .. -> 0..00dn
3. 递增第 n-1 位数字并开始递减第 n 位数字:0..00dn -> 0..01dn -> ... 0..011 -> 0..10
4. 递增第 n-1 位数字并开始递增第 n 位数字:0..10 -> 0..20 -> 0..021 -> ...0..2dn
5. 在0..0dn-1dn上递增第n-2索引并开始递减第n索引，依此类推。

演示

# 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# 代码:(请 fiddle )

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;

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

演示:

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

结果:

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